Решение треугольных систем. Постановка задачи После выполнения LU-разложения нужно решать треугольные системы.
Ly b, Ux y Процесс их решения назывантся прямой и обратной подстановками. Рассмотрим только решение нижнетреугольной системы решение верхнетреугольной системы организуется аналогичным образом.
В качестве алгоритма решения выберем алгоритм скалярных произведений. Его запись на псевдокоде выглядит следующим образом для i 1 до n для j 1 до i-1 bi bi Lijyj yi biLii Распараллеливание Пусть вычислительная система состоит из p процессоров, а размерность матрицы L равна n. Разобьем матрицу L на блоки в соответствии с рисунком Все блоки кроме, может быть, двух последних состоят из строк.
Также на p блоков разбиваются вектора y и b. Далее, пусть блок S1 расположен в памяти процессора P1, блоки L2 и S2 в памяти процессора P2 и т.д. Перед началом вычислений блок bk пересылается процессору Pk, k 1 p. Рассмотрим первый шаг алгоритма решения системы. 1. Процессор P1 решает систему S1y1b1 2. Найденный вектор y1 пересылается процессорам P2 Pp 3. Процессор Pk k2 p пересчитывает вектор bk по формуле Остальные шаги алгоритма организуются аналогично.
Оценки производительности Будем считать, что матрица L уже распределена по процессорам. В противном случае выгоднее решать систему последовательным способом. На одном процессоре задача размерности n решается за время Оценим время выполнения k-ой итерации в системе из p процессоров Тогда Зафиксируем p4 и построим графики функции Spn при различных значениях отношения TsendTmul. Вычислим оптимальное число процессоров p и построим график функции Spn при n1500. Значение p найдем из уравнения, p 1 Отсюда получаем. Результаты эксперимента К сожалению, для данной задачи не удалось получить приемлимых результатов.
Дело в том, что на момент проведения экспериментов в сети было недостаточное количество компьютеров, поэтому параллельный алгоритм выполнялся даже дольше, чем последовательный. 2.3. QR-разложение Постановка задачи Рассмотрим ортогональное приведение матрицы A A QR где Q ортогональная, а R верхнетреугольная матрицы. В качестве алгоритма решения задачи выберем преобразование Хаусхолдера.
На последовательных компьютерах преобразование Хаусхолдера выполняется примерно в два раза медленне, чем LU-разложение. Поэтому данный метод редко используется для решения СЛУ, однако он широко используется при вычислении собственных значений. Пусть A матрица nn. Рассмотрим запись алгоритма на псевдокоде для k 1 до n-1 , uTk 0 0, akk sk, ak1,k ank akk sk для j k1 до n j kukaj, aj aj - juk Распараллеливание Первый шаг алгоритма выглядит следующим образом 1. Послать первый столбец матрицы А всем процессорам 2. Вычислить s1 в процессоре 1 и переслать его всем процессорам. 3. Пересчитать матрицу А во всех процессорах в соответствии с алгоритмом Хаусхолдера.
Остальные шаги организуются аналогичным образом. Оценки производительности Пусть А матрица размерности nn. И пусть система состоит из p процессоров, причем npm. Распределим матрицу А по процессорам в соответствии со столбцовой циклической схемой хранения. Последовательный алгоритм выполняется за время Пересылка начальных данных выполняется за время n2Tsend, пересылка результата за время n2Tsend. Поэтому Зафиксируем p4 и построим графики функции Spn при различных значениях отношения TsendTmul. Построим график функции Spn при n2000. Результаты эксперимента nt1n, секtpn, p2, секSpn13001787,7801406,5931,27114002242, 2651719,5281,30415002762,6942126,7851,29 916004085,4852969,1021,376 Г Л А В А 3 ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЛИНЕЙНЫХ УРАВНЕНИЙ 3.1. Метод Якоби Постановка задачи Пусть А невырожденная матрица nn и нужно решить систему Ax b, где диагональные элементы aii матрицы А ненулевые.
Тогда метод Якоби в матричной форме имеет вид xk1 Hxk d, k 0, 1 H D-1B, d D-1b, где D diaga11 ann, B D A и указано начальное значение х0. Конечно, метод Якоби сходится не всегда.
Приведем две стандартные теоремы сходимости. Теорема. Если матрица А имеет строгое диагональное преобладание или является неприводимой с диагональным преобладанием, то итерации метода Якоби сходятся при любом начальном приближении х0. Теорема.
Если матрица A D B симметрична и положительно определена, то итерации метода Якоби сходятся при любом начальном приближении х0 тогда и только тогда, когда матрица D B положительно определена. Для проверки сходимости итерационных приближений будем использовать следующий критерий где. Распараллеливание Пусть система состоит из р процессоров и матрицы разбиты на блоки следующим образом Припишем блоки H1, d1, xk1 процессору Р1, блоки H2, d2, xk2 процессору Р2 и т.д. Тогда соответствующие компоненты вектора х можно вычислять параллельно по схеме Шаг 1. Переслать на i-й процессор Hi, di, x0. Шаг 2. На к-й итерации i-й процессор выполняет следующие действия хiк1 Hixik di переслать xik1 остальным процессорам получить недостающие компоненты вектора xk1 проверить условие сходимости и, если условие выполнено, установить флаг Шаг 3. Если хотябы один флаг не установлен, то перейти к следующей итерации Шаг 2. Шаг 4. Передать результат.
Оценки производительности Для простоты будем считать, что n pm. Оценим время выполнения одной итерации метода Якоби. Далее, пусть метод сошелся за k шагов.
Тогда Из последней формулы несложно установить, что если число итераций, то каким бы большим небыло значение n, нам все равно не удастся достичь ускорения Sp 2. Зафиксируем p4, k500 и построим график функции Spn при различных значениях отношения TsendTmul. Кривая, которой соответствует значение TsendTmul1000 никогда не поднимется выше 1, т.к. число итераций k слишком мало. Вычислим оптимальное число процессоров p и построим график функции Spn, k при n5000, k500. Значение p найдем из уравнения, p 1 Отсюда. Как и следовало ожидать, при больших значениях k значение p практически не зависит от k уже при k100 отношение. Результаты эксперимента nt1n, секtpn, p2, секSpn1000489,634333,5351,4681100608,457 404,2321,5051200832,035514,8401,61613008 57,569559,9421,5311400992,017661,8231,49 9