Прямые методы решения линейных систем. Рассмотрим систему линейных уравнений Ax b с невырожденной матрицей А размера nn . 2.1. LU-разложение Постановка задачи Построим разложение мтрицы A LU, где L нижнетреугольная матрица с единицами на главной диагонали, а U верхнетреугольная матрица.
В качестве алгоритма LU-разложения выберем kij-форму с выбором главного элемента по строке столбцу.
Упрощенно алгоритм можно записать следующим образом для k 1 до n-1 для i k1 до n lik aikakk для j k1 до n aij aij - likakj Распараллеливание и оценки производительности Предположим вначале, что система состоит из p n процессоров. Тогда один из возможных вариантов организации LU-разложения выглядит так. Пусть i-ая строка матрицы А хранится в процессоре i. На первом шаге первая строка рассылается всем процессорам, после чего вычисления могут выполняться параллельно процессорами Р2 Pn. На втором шаге вторая строка приведенной матрицы рассылается из процессора P2 процессорам P3, ,Pn, и т. д. На k-ом шаге процессоры P1, ,Pk-1 простаивают, Pk выполняет нормировку и рассылку строки, Pk1 Pn вычисляют по формуле. Рассылка строки выполняется за время n-kn-kTsend, нормировка за время n-kTmul. Параллельная модификация строк выполняется за время n-kTmul. Таким образом Т.е. при больших значениях n параллельная версия может работать медленнее последовательной версии.
Это объясняется значительным объемом обмена данными между каждыми двумя шагами и уменьшением числа активных процессоров на 1 на каждом шаге. В ситуации, когда p n, проблема балансировки нагрузки в определенной степени смягчается.
Будем считать, что n mp, и строки 1, p1, 2p1, хранятся в процессоре 1, строки 2, p2, 2p2, в процессоре 2, и т.д. Такой способ хранения называется циклической слоистой схемой.
Для уменьшения простоя процессоров будем использовать опережающую рассылку на k-м шаге k1-я строка рассылается сразу после того, как окончится ее модификация. Для обеспечения численной устойчивости алгоритма применим схему выбора главного элемента по строке. В этом случае получим При достаточно больших значениях n Альтернативой для хранения элементов по строкам является столбцовая циклическая схема хранения.
В этом случае по процессорам распределяются не строки, а столбцы, что позволяет уменьшить объем передаваемых данных. Главный элемент будем выбирать в активном столбце. На k-м шаге процессор, хранящий k-й столбец, выбирает главный элемент, вычисляет значения i k и пересылает их на остальные процессоры. Далее каждый процессор вычисляет по формуле Передача данных происходит за время pn-kTsend, вычисления за время. Тогда При достаточно больших значениях n Зафиксируем p4 и построим графики функции Spn при различных значениях отношения TsendTmul. Вычислим оптимальное число процессоров p и построим график функции Spn при n5000. Значение p найдем из уравнения, p 1 Отсюда получаем. Результаты эксперимента nt1n, секtpn, p2, секSpn1000450,975309,9481,4551100600,691 408,0781,4721200780,679554,9601,40813009 93,420689,3961,441 2.2.