А.В. ПОПОВ Институт кибернетики им. В.М. Глушкова НАН Украины Параллельные алгоритмы решения линейных систем с разреженными симметричными матрицами

Параллельные алгоритмы 2 Во многих случаях при численном решении научно-технических задач разрешающая система уравнений является задачей (несколькими задачами) или сводится к задачам линейной алгебры: линейная система (система линейных алгебраических уравнений, СЛАУ) Ax = b, алгебраическая проблема собственных значений Ax = λBx. Часто задачи линейной алгебры возникают при дискретизации краевых задач или задач на собственные значения проекционно-разностным методом (конечных разностей, конечных элементов). Как правило, решение задач линейной алгебры занимает значительную часть (50 % и более) времени решения всей задачи в целом.

Параллельные алгоритмы 3 Особенности задач линейной алгебры, полученных в результате дискретизации Высокий порядок разрешающих дискретных задач – до десятков миллионов. Матрицы задач имеют разреженную структуру – количество ненулевых элементов матрицы составляет величину kn, где k

Параллельные алгоритмы 4 Примеры разреженных матриц порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 5% порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 1%

Параллельные алгоритмы 5 В LDL T -варианте метода Холецкого выделяются три подзадачи: разложение матрицы системы A = LDL T,O(nm 2 ) операций; решение СЛАУ с нижней треугольной матрицей Ly = b, O(nm) операций; решение СЛАУ с верхней треугольной матрицей L T x = D -1 y, O(nm) операций.

Параллельные алгоритмы 6 Циклические схемы распределения между процессами элементов матриц Строчно-циклическая схема процессу с логическим номером r (r = 0, 1,…, p-1) распределяются элементы строк матрицы с номерами k+1, p+k+1, 2p+k+1,..., где p – количество используемых процессов, а k равно остатку от деления r+l на p при одном и том же 0 l p-1 для всех процессов Одномерная блочная циклическая схема если процесс с логическим номером r оперирует с элементами строк матрицы с номерами sI+1,…,sI+s, то процесс с номером r+1 – с элементами строк с номерами s(I+1)+1,…,s(I+1)+s Численные методы для многопроцессорного вычислительного комплекса ЕС / В.С. Михалевич, Н.А. Бик, …, А.Н. Химич и др. / Под редакцией И.Н. Молчанова. – М.: Изд. ВВИА им. Н.Е. Жуковского, – 401 с.

Параллельные алгоритмы 7 Одномерная блочная циклическая схема распределения и обработки элементов ленточной матрицы

Параллельные алгоритмы 8 Одномерный блочно-циклический алгоритм Для I = 0, 1, 2, …, N, где n = Ns+t, 1ts, выполняются следующие операции: при I > 0 соответствующий процесс вычисляет элементы g i+rs,j (g i,j l i,j d j ; i, j = Is–s+1,…, Is; r = 1,..., p) ; вычисление процессором, содержащим (I+1)-ю строку квадратных блоков (порядка s) матрицы A, элементов l i,i-k (k = 1,..., m i ) и d i, где i = Is+1,…, Is+s ; при I > 0 вычисление ненулевых элементов g i,j (i = Is+ps+1,…, n; j = Is s+1,…, Is) квадратных блоков (порядка s) I-го столбца блоков в соответствии с их распределением между процессами; рассылка всем процессам диагональных элементов di (i = Is+1,…, Is+s) и элементов (I+1)-й строки блоков матрицы L; проверка положительной определенности ( d i > 0 ) или невырожденности ( |d i | > masheps ), i = Is+1,…, Is+s, матрицы A. В случае ленточной матрицы m i = min{ m, i-1 }, а в случае профильной матрицы m i = i-k, где k – второй индекс первого (крайнего левого) элемента i-й строки матрицы. Попов А.В., Химич А.Н. Параллельный алгоритм решения системы линейных алгебраических уравнений с ленточной симметричной матрицей // Компьютерная математика. – – 2. – С. 52–59

Параллельные алгоритмы 9 Эффективность одномерного блочного циклического алгоритма Коэффициент ускорения при n sp 2 и m sp где Коэффициент эффективности Если, то

Параллельные алгоритмы 10 Блочные схемы распределения Блочно-диагональная матрица с окаймлением Узкая ленточная матрица исходная и переупорядоченная в блочно-диагональную матрицу с окаймлением

Параллельные алгоритмы 11 Блочный алгоритм

Параллельные алгоритмы 12 Эффективность блочного алгоритма Коэффициент ускорения при pm

Параллельные алгоритмы 13 Результаты численных экспериментов порядок матрицы полуширина ленты матрицы плотность матрицы 100% полуширина ленты матриц порядок матриц

Параллельные алгоритмы 14 Результаты численных экспериментов порядок матрицы максимальная полуширина ленты матрицы плотность матрицы 21%

Параллельные алгоритмы 15 Результаты численных экспериментов Задача 1Задача 2Задача 3Задача 4 Порядок матрицы Полуширина ленты

Параллельные алгоритмы 16 Результаты численных экспериментов полуширина ленты матриц 151 порядок матриц

17 Анализ прочности строительных конструкций Результаты тестирования

9-этажное здание (10_U) КЭ-сетка: - количество элементов количество узлов Структура матрицы Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 9% - полуширина ленты матрицы

Фундамент здания (Gmot2) КЭ-сетка: - количество элементов количество узлов Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 7% - полуширина ленты матрицы Структура переупорядоченной матрицы Исходная структура матрицы

Промышленное здание (Frs5) Структуры матрицы до переупорядочивания и после КЭ-сетка: - количество элементов количество узлов Параметры разрешающей задачи: - порядок СЛАУ для ленточной структуры - плотность матрицы жесткостей 21% - полушиpина ленты матрицы для профильной структуры - плотность матрицы жесткостей 2% - полушиpина ленты матрицы37 580

21 Анализ прочности строительных конструкций Задача RAZMER КЭ-сетка: - количество элементов количество узлов Параметры задачи: - порядок СЛАУ плотность матрицы жесткостей 1% - полушиpина ленты матрицы размер файла данных задачи 76 Гб Структура переупорядоченной матрицы Решение задачи: - ввод и распределение данных 33 мин. - разложение матрицы 8 час. 53 мин. - решение СЛАУ с нижней и верхней треугольными матрицами 38 мин. Всего10 час. 04 мин. Оценка времени решения на ПК около 115 час.