Лабораторные работы / Лабораторная работа 1 / LU-разложение матрицы (Буренков)

Национальный исследовательский университет

«Московский энергетический институт»

Лабораторная работа №1

по дисциплине «Параллельные системы и параллельное программирование»

выполнил студент

группы А-13-08

Буренков Сергей

проверил Панков

Николай Александрович

Москва, 2012

Постановка задачи

Дана квадратная матрица (вообще говоря, большой размерности). Требуется найти ее LU-разложение, т.е. представление в виде произведения нижнетреугольной матрицы на верхнетреугольную с единицами на главной диагонали. Для нахождения составить последовательно-параллельную программу с применением интерфейса передачи сообщений (Message Passing Interface). Исследовать характеристики разработанной программы в зависимости от числа исполнителей.

Последовательный алгоритм решения

Получить LU-разложение квадратной матрицы последовательным способом можно несколькими способами.

1. Схема единственного деления.

При выполнении первого шага исключения по схеме единственного деления матрица приводится к виду

где

Введем матрицу

Аналогично можно получить и . Тогда

Проведя подобные выкладки, можно получить LU-разложение матрицы (нерациональный способ).

2. Из полученных соотношений можно вывести формулы:

Используя эти формулы можно получить LU – разложение матрицы.

Параллельный алгоритм решения.

Заметим, что изложенные в пункте 2 соотношения обладают неприятным свойством для параллельных алгоритмов: высокая степень зависимости по данным. Иными словами, для вычисления каждого следующего элемента необходимо знать некоторое количество элементов, вычисленных ранее. Наличие зависимости затрудняет составление последовательно-параллельной модификации метода и снижает ускорение, которое может быть получено с ее помощью. Поэтому предлагается несколько изменить вышеизложенный метод. Пусть матрица L на главной диагонали не содержит единицы, но останется нижнетреугольной. А матрица U на главной диагонали содержит единицы и остается верхнетреугольной. Это несущественное изменение, которое никак не повлияет на сложность обратного хода при решении СЛАУ, но облегчит составление последовательно-параллельной модификации.

Еще одно немаловажное замечание: матрицы L и U являются нижне- и верхнедиагональными, причем на местах, где у L могут быть ненулевые элементы, у U гарантировано нули, и наоборот. К тому же, после вычисления некоторых значений искомых матриц часть разлагаемой матрицы становится неиспользуемой. Учитывая это при разложении матрицы, можем не заводить две новые матрицы L и U, а записывать найденные элементы прямо в разлагаемую матрицу. Такой подход втрое сократит расходы на память, что существенно при работе с матрицами большой размерности.

Результаты вычислительного эксперимента

1. Размерность матрицы 1 000 * 1 000

Число исполнителей	Время решения	Ускорение
1	8.48365	-
2	5.48102	1.54
3	4.48196	1.89
4	3.89001	2.18
8	0.854583	9.98
12	0.637715	13.47
16	0.539338	15.71
20	0.501528	17.0
24	0.462152	18.44
28	0.434466	19.73
32	0.365803	22.93
36	0.441958	19.28
40	0.453205	18.85
44	0.463179	18.44

2. Размерность матрицы 5 000 * 5 000

Число исполнителей	Время решения	Ускорение
1	1195.35	-
2	774.229	1.54
3	262.511	4.55
4	195.356	6.12
8	101.912	11.73
12	69.9047	17.1
16	55.2886	21.62
20	46.687	25.6
24	39.6372	30.16
28	35.3385	33.83
32	28.652	41.72
36	26.4382	45.21
40	23.963	49.88
44	22.5345	53.04
48	21.1221	56.6
52	20.1886	59.2
56	19.0952	62.6
60	18.2098	65.68
64	17.4166	68.66

3. Размерность матрицы 10 000 * 10 000

Число исполнителей	Время решения
2	6219.85
3	2078.28
4	1579.27
8	790.765
12	536.824
16	411.68
20	338.538
24	285.093
28	247.671
32	221.638
36	189.973
40	173.143
44	159.807
48	147.936
52	138.732
56	129.683
60	123.003
64	115.858

3. Размерность матрицы 20 000 х 20 000.

Число исполнителей	Время решения
36	4804.52
40	4380.60
44	4028.25
48	3750.81
52	3487.25
56	3289.35
60	3093.44
64	2947.74