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

Посмотреть архив целиком

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

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

















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

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















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

группы А-13-08

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





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

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







Москва, 2012



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

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

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

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

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

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

где

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

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

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

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

Используя эти формулы можно получить 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



  1. Размерность матрицы 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



  1. Размерность матрицы 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

  1. Размерность матрицы 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




Случайные файлы

Файл
170126.rtf
49346.rtf
10999.rtf
4148.rtf
100036.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.