Методическое пособие

Часть II.

Решение систем линейных алгебраических уравнений
на распределенной памяти.

Содержание

1. Введение.
2. Краткое описание содержания раздела Комплекса для решения систем линейных уравнений.
3. Дескриптор вектора (матрицы) правой части системы уравнений.
4. Разбор примера по использованию программы для решения системы уравнений с плотной матрицей, включая способы реализации распределения матриц на ФОРТРАНе.
5. Блочно-столбцовое разбиение и схема размещения в локальной памяти ленточных матриц.
6. Схема размещения в локальной памяти трехдиагональных матриц.
ЛИТЕРАТУРА
Приложение 2_1. Пример описания целевой подпрограммы для решения системы A*X = B с матрицей общего вида.
Приложение 2_2. Пример составления головной программы для использования целевой подпрограммы из Приложения 2_1.
Приложение 2_3. Пример составления головной программы при чтении исходных матриц из файла и записи результатов в файл

1.Введение.

Настоящее пособие представляет собой вторую часть методических материалов, предназначенных для пользователей Комплекса программ PARALG для решения задач линейной алгебры с использованием распределенной памяти, реализуемого в НИВЦ МГУ (http://www.srcc.msu.su/num_anal/par_prog/).

Указанный Комплекс программ ориентирован на реализацию программ на ФОРТРАН'е - 77 в стиле SPMD (Single Program Multiple Data) с использованием для обмена информацией между параллельными процессами передачи сообщений с помощью примитивов MPI (Massage Passing Interface).

В настоящей второй части пособия рассматривается решение задач из раздела "Решение систем линейных алгебраических уравнений" с помощью программ, включенных к настоящему времени в указанный Комплекс.

Изложение материала в настоящей части пособия предполагает, что пользователь уже ознакомился с основными концепциями и правилами, принятыми при решении задач линейной алгебры с помощью целевых программ Комплекса, которые были описаны в первой части методических материалов (см.).
В дальнейшем при упоминании таких общих положений мы будем ссылаться на номера пунктов первой части, в которых дается их подробное изложение.

Повторим здесь лишь вкратце основные действия, требующиеся от пользователя программ Комплекса PARALG.
Прежде чем обратиться к какой - либо из целевых параллельных программ пользователь должен выбрать для ее выполнения и описать так называемую "решетку процессов", т.е. "выстроить" параллельные процессы в общем случае в двумерное упорядоченное множество, состоящее из NPROW строк, в каждой из которых содержится по NPCOL процессов. Таким образом общее число используемых процессов NP = NPROW * NPCOL.

Поскольку обмен информацией между процессами происходит с помощью передачи сообщений, и для задач линейной алгебры используется специально разработанный для этой цели пакет BLACS, то необходимо в начале вычислений написать операторы инициализации этого пакета и определения контекста, соответствующего выбранной решетке процессов (см. пп.3,4).

По окончании вычислений необходимо также сделать выход из определенного ранее контекста (т.е. освободить использованные процессы решетки).

Кроме выбора решетки процессов, необходимо распределить исходные матрицы (векторы), обрабатываемые целевыми программами по параллельным процессам выбранной решетки.

Процесс распределения состоит из разбиения исходной матрицы (вектора), называемой глобальной, на прямоугольные (квадратные) блоки, содержащие по NB * MB элементов матрицы, с последующим "циклическим" распределением их по процессам решетки (см. пп.6). Это необходимо ввиду использования базовыми подпрограммами высокоэффективных блочных алгоритмов обработки матриц.

Таким образом при вычислениях в локальной памяти каждого из процессов содержится только некоторая (называемая локальной) часть исходной глобальной матрицы (вектора). Поэтому в головной фортранной программе, вызывающей целевую программу Комплекса, для размещения матрицы достаточно заказать память, равную по величине самой большой локальной части глобальной матрицы (т.к. размеры локальных частей на разных процессах могут несколько отличаться по величине) (см. пп.5.1, 6).

В связи с вышесказанным, при вызове целевых программ Комплекса помимо адреса локальной части матрицы (вектора) им необходимо передать в качестве фактического параметра адрес "дескрипторного массива" или "дескриптора". Информация, содержащаяся в дескрипторе, позволяет всегда однозначно определить в локальной памяти, какого процесса и на каком именно месте располагается каждый элемент глобальной матрицы A ( I, J ) (см. п.5.2).

Действия по инициализации решетки процессов и определению контекста выполняются подпрограммами пакета BLACS.

Распределение блоков исходных глобальных матриц (векторов) по параллельным процессам значительно упрощается посредством использования соответствующих служебных подпрограмм (см. п.6.3).

Вопросы обработки ошибок и выдачи диагностических сообщений достаточно подробно рассматриваются в п.7 третьей части пособия.

2. Краткое описание содержания раздела Комплекса для решения систем линейных уравнений.

Одна из задач, решаемых Комплексом, - это линейные системы (системы линейных алгебраических уравнений)

(1)                            A X = B ,
             
где A - невырожденная квадратная матрица,
       B - либо вектор правой части, если решается единственная (одна)
             система, либо матрица, состоящая из столбцов правых частей,
             если решается несколько систем с одной и той же матрицей A, 
       X - вектор неизвестных, если B - вектор, или матрица, состоящая
             из векторов неизвестных, если B - матрица. 
Под векторами понимаются векторы - столбцы.

Для решения системы (1) применяются специальные блочные реализации (блочные алгоритмы) для прямого и обратного исключения Гаусса.

Решение системы разбито на два этапа:

- факторизация матрицы системы;
- непосредственно само решение системы с использованием
   результатов, полученных на первом этапе.

Каждый из этапов осуществляется посредством обращения к специальным базовым подпрограммам комплекса.

1. Виды факторизации, зависящие от свойств матрицы A, представлены ниже.

1.1. Для матриц общего вида применяется LU - факторизация с выбором ведущего элемента по столбцам:

           A  =  P L U ,
где
     P - матрица перестановок;
     L - нижняя треугольная матрица с единичными диагональными
            элементами;
     U - верхняя треугольная матрица.

1.2. Для симметричных или эрмитовых положительно определенных матриц применяется разложение Холецкого:

           A  =  U^T U   или   A  =  L L^T  (для симметричных) ,
           A  =  U^H U   или   A  =  L L^H  (для эрмитовых) ,
где
     U - верхняя треугольная матрица;
     L - нижняя треугольная матрица.

1.3. Для ленточных матриц общего вида применяется LU - факторизация с выбором ведущего элемента по столбцам:

           A  =  P L U Q ,
где
     P  и  Q - матрицы перестановок,
     L  и  U - нижняя треугольная и верхняя треугольная ленточные
                    матрицы соответственно.

1.4. Для ленточных матриц общего вида с диагональным преобладанием, включая трехдиагональные матрицы общего вида, применяется LU - факторизация без выбора ведущего элемента:

            A  =  P L U P^T ,
где
     P        - матрица перестановок,
     L и U - нижняя и верхняя треугольные ленточные матрицы
                  соответственно.

1.5. Для симметричных и эрмитовых положительно определенных ленточных матриц применяется разложение Холецкого:

     A  =  P U^T U P^T  или  A  =  P L L^T P^T (для симметричных) ,
     A  =  P U^H U P^T  или  A  =  P L L^H P^T (для эрмитовых) ,

где
     P        - матрица перестановок,
     U и L - верхняя и нижняя треугольные ленточные матрицы
                  соответственно.

1.6. Для симметричных и эрмитовых положительно определенных трехдиагональных матриц применяется LDL^T - факторизация:

  A  =  P U^T D U P^T  или  A  =  P L D L^T P^T (для симметричных) ,
  A  =  P U^H D U P^T  или  A  =  P L D L^H P^T (для эрмитовых) ,

где
     P        - матрица перестановок,
     U и L - двухдиагональные верхняя и нижняя треугольные матрицы
                 соответственно.

Указанные факторизации выполняются разными базовыми подпрограммами Комплекса:

для плотных (вещественных или комплексных) матриц общего вида и симметричных (или эрмитовых) положительно определенных - PDGETRF (PZGETRF) и PDPOTRF (PZPOTRF);
для ленточных матриц общего вида (вещественных или комплексных) - PDGBTRF (PZGBTRF) (с выбором ведущего элемента по столбцу) и PDDBTRF (PZDBTRF) (без выбора ведущего элемента);
для симметричных/эрмитовых ленточных положительно определенных матриц - PDPBTRF (PZPBTRF);
для трехдиагональных матриц общего вида (вещественных или комплексных) - PDDTTRF (PZDTTRF) (без выбора ведущего элемента);
для симметричных/эрмитовых трехдиагональных положительно определенных матриц - PDPTTRF (PZPTTRF).

2. Второй этап - решение системы с использованием полученной на предыдущем этапе факторизации матрицы A выполняется следующими базовыми подпрограммами Комплекса:

для плотных (вещественных или комплексных) матриц общего вида и симметричных (или эрмитовых) положительно определенных - PDGETRS (PZGETRS) и PDPOTRS (PZPOTRS);
для ленточных матриц общего вида (вещественных или комплексных) - PDGBTRS (PZGBTRS) и PDDBTRS (PZDBTRS);
для симметричных/эрмитовых ленточных положительно определенных матриц - PDPBTRS (PZPBTRS);
для трехдиагональных матриц общего вида (вещественных или комплексных) - PDDTTRS (PZDTTRS);
для симметричных/эрмитовых трехдиагональных положительно определенных матриц - PDPTTRS (PZPTTRS).

Приведем, наконец, список всех целевых программ, включенных в настоящее время в раздел Комплекса "Решение систем линейных алгебраических уравнений".

- подраздел "Решение систем с невырожденными матрицами общего вида":

PDGESV - PZGESV	Решение системы A * X = B с матрицей общего вида методом Гаусса с выбором ведущего элемента по столбцу;
PDGESV1 - PZGESV1	Решение системы A * X = B или A^T * X = B с матрицей общего вида методом Гаусса с выбором ведущего элемента по столбцу;
PDGESV2 - PZGESV2	Решение системы A * X = B или A^T * X = B с матрицей общего вида методом Гаусса с выбором ведущего элемента по столбцу и оценка обратного числа обусловленности;
PDGESV3 - PZGESV3	Решение системы A * X = B или A^T * X = B с матрицей общего вида методом Гаусса с выбором ведущего элемента по столбцу, с итерационным уточнением решения и оценкой границ ошибок;

- подраздел "Решение систем с симметричными или эрмитовыми невырожденными матрицами":

PDPOSV - PZPOSV	Решение системы с симметричной (эрмитовой) положительно определенной матрицей методом квадратного корня (методом Холецкого);
PDPOSV1 - PZPOSV1	Решение системы с симметричной (эрмитовой) положительно определенной матрицей методом Холецкого и оценка обратного числа обусловленности;
PDPOSV2 - PZPOSV2	Решение системы с симметричной (эрмитовой) положительно определенной матрицей методом Холецкого с итерационным уточнением решения и оценкой границ ошибок.

- подраздел "Решение систем с невырожденными матрицами специального вида":

PDDBSV - PZDBSV	Решение системы с ленточной матрицей общего вида без выбора ведущих элементов;
PDDTSV - PZDTSV	Решение системы с трехдиагональной матрицей общего вида без выбора ведущего элемента;
PDGBSV - PZGBSV	Решение системы линейных уравнений с ленточной матрицей общего вида с выбором ведущего элемента;
PDPBSV - PZPBSV	Решение системы с симметричной (эрмитовой) положительно определенной ленточной матрицей методом Холецкого;
PDPTSV - PZPTSV	Решение системы с симметричной (эрмитовой) положительно определенной трехдиагональной матрицей.

Часть II.

Решение систем линейных алгебраических уравнений на распределенной памяти.

Содержание

1.Введение.

2. Краткое описание содержания раздела Комплекса для решения систем линейных уравнений.

Решение систем линейных алгебраических уравнений
на распределенной памяти.