LU-разложение матрицы (Буренков) (Лабораторная работа 1)
Описание файла
Файл "LU-разложение матрицы (Буренков)" внутри архива находится в папке "Лабораторная работа 1". Документ из архива "Лабораторная работа 1", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Онлайн просмотр документа "LU-разложение матрицы (Буренков)"
Текст из документа "LU-разложение матрицы (Буренков)"
Национальный исследовательский университет
«Московский энергетический институт»
Лабораторная работа №1
по дисциплине «Параллельные системы и параллельное программирование»
выполнил студент
группы А-13-08
Буренков Сергей
проверил Панков
Николай Александрович
Москва, 2012
Постановка задачи
Дана квадратная матрица (вообще говоря, большой размерности). Требуется найти ее LU-разложение, т.е. представление в виде произведения нижнетреугольной матрицы на верхнетреугольную с единицами на главной диагонали. Для нахождения составить последовательно-параллельную программу с применением интерфейса передачи сообщений (Message Passing Interface). Исследовать характеристики разработанной программы в зависимости от числа исполнителей.
Последовательный алгоритм решения
Получить LU-разложение квадратной матрицы последовательным способом можно несколькими способами.
-
Схема единственного деления.
При выполнении первого шага исключения по схеме единственного деления матрица приводится к виду
где
Введем матрицу
Аналогично можно получить и . Тогда
Проведя подобные выкладки, можно получить LU-разложение матрицы (нерациональный способ).
-
Из полученных соотношений можно вывести формулы:
Используя эти формулы можно получить LU – разложение матрицы.
Параллельный алгоритм решения.
Заметим, что изложенные в пункте 2 соотношения обладают неприятным свойством для параллельных алгоритмов: высокая степень зависимости по данным. Иными словами, для вычисления каждого следующего элемента необходимо знать некоторое количество элементов, вычисленных ранее. Наличие зависимости затрудняет составление последовательно-параллельной модификации метода и снижает ускорение, которое может быть получено с ее помощью. Поэтому предлагается несколько изменить вышеизложенный метод. Пусть матрица L на главной диагонали не содержит единицы, но останется нижнетреугольной. А матрица U на главной диагонали содержит единицы и остается верхнетреугольной. Это несущественное изменение, которое никак не повлияет на сложность обратного хода при решении СЛАУ, но облегчит составление последовательно-параллельной модификации.
Еще одно немаловажное замечание: матрицы L и U являются нижне- и верхнедиагональными, причем на местах, где у L могут быть ненулевые элементы, у U гарантировано нули, и наоборот. К тому же, после вычисления некоторых значений искомых матриц часть разлагаемой матрицы становится неиспользуемой. Учитывая это при разложении матрицы, можем не заводить две новые матрицы L и U, а записывать найденные элементы прямо в разлагаемую матрицу. Такой подход втрое сократит расходы на память, что существенно при работе с матрицами большой размерности.
Результаты вычислительного эксперимента
-
Размерность матрицы 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 |
-
Размерность матрицы 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 |
-
Размерность матрицы 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 |
-
Размерность матрицы 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 |