Лабораторные работы / Лабораторная работа 3 / LU разложение матрицы (Сержанов)
.docxНациональный исследовательский университет
«Московский энергетический институт»
Лабораторная работа №3
«Параллельные системы и параллельное программирование»
тема: «LU разложение матрицы с использованием нитевого распараллеливания»
выполнил студент
группы А-13-08
Сержанов Никита
Проверил
Панков Н.А.
Москва, 2012
Постановка задачи
Дана квадратная матрица. Требуется найти ее LU-разложение, т.е. представление в виде произведения нижнетреугольной матрицы на верхнетреугольную с единицами на главной диагонали. Необходимо составить MPI программу для решения данной задачи.
Последовательный алгоритм решения
Программная реализация:
for (int r = 0; r < n; r++)
{
for (int k = r + 1; k < n; k++)
A[k, r] = A[k, r]/A[r, r];
for (int i = r + 1; i < n; i++)
for (int j = r + 1; j < n; j++)
A[i, j] -= A[i, r]*A[r, j];
}
Параллельный алгоритм решения.
Исходная матрица разбивается по строкам, каждый вычислитель получает по своей группе строк. (см иллюстрацию). На каждом шаге r происходит перераспределение строк заново.
Эксперименты проведены на компьютере с процессором Intel Сore i5 (2 ядра)
Результаты вычислительного эксперимента
Размерность матрицы 5 000 * 1 000
Число вычислителей |
Время решения(с) |
Ускорение |
1 |
182 |
- |
2 |
94 |
1.93 |
3 |
61 |
2.98 |
4 |
49 |
3.71 |
-
Размерность матрицы 10 000 * 10 000
Число вычислителей |
Время решения(с) |
Ускорение |
1 |
1453 |
- |
2 |
719 |
2.02 |
3 |
486 |
2.98 |
4 |
431 |
3.37 |