Участник:Анюшева Ирина/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)

GMRES (обобщенный метод минимальных невязок)
Последовательный алгоритм
Последовательная сложность	$O(m^2n^2)$
Объём входных данных	$n^2+2n$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(mn)$
Ширина ярусно-параллельной формы	$O(mn)$

Основные авторы описания: Анюшева Ирина (614 группа, разделы: 1.1-1.2, 1.7-1.8, 2.7, 3), Исхаков Эльдар (614 группа, разделы 1.3-1.6, 1.9-1.10)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространстве Крылова с минимальной невязкой. Метод GMRES разработан Ю. Саадом и Мартин Х. Шульцом и впервые предложен в 1986 году. Метод гарантирует неувеличение нормы невязки в ходе итерационного процесса, который основан на построении базиса в соответствующей системе подпространстве Крылова $K_j(A, r_0)$. Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису. Метод сходится для любого начального приближения.

Входные данные алгоритма: система линейных алгебраических уравнений, которую необходимо решить.

Параметры алгоритма: $m$ - размерность подпространства Крылова, $\varepsilon$ - параметр останова алгоритма.

Выходные данные: решение системы в виде вектора.

Краткое описание алгоритма:

• Задать параметры алгоритма и начальное приближение;
• Пока не выполнен критерий останова повторить:
  • Построить базис подпространства Крылова;
  • Минимизировать невязку.

1.2 Математическое описание алгоритма

Исходные данные: система линейных алгебраических уравнений $Ax=b$, где:

$A=(a_{ij})$ $-$ вещественная матрица размера $n \times n$;

$b$ и $x$ вектора из $n$ элементов;

$x^*$ $-$ точное решение системы.

Вычисляемые данные: $x^{m} -$приближенное решение системы.

В качестве нормы рассматривается евклидова норма.

1.2.1 Ортогонализация Арнольди

Для построения базиса $V$ в подпространстве Крылова в методе GMRES применяется ортогонализация Арнольди.

Формулы метода:

$\begin{align} (h_{i+1,i}v_{i+1}) & = Av_i - \sum_{j = 1}^{i} h_{j,i}v_j, \\ v_1 &= \frac{r_0}{\parallel r_0 \parallel}, \end{align}$

В матрично-векторных обозначениях соотношение может быть записано как

$\begin{align} AV_i &= V_i H_i + h_{i+1,i}v_{i+1} e_i^T &=V_{i+1}\overline{H}_i, \end{align}$

$\begin{align} V_i &= [v_1|v_2|...|v_i], \overline{H}_i - \end{align}$ верхняя матрица Хессенберга размерности $(i+1)\times i$

1.2.2 Минимизация невязки

Невязку уравнения можно определить как $J(y) = \parallel b- A x\parallel = \parallel b- (Ax_0+V_m y)\parallel =\parallel \beta e_1 - \overline{H}_m y \parallel$, где $y -$ вектор размерности $m$.

Вектор $x_m$ может быть получен как $x_m = x_0 + V_m y_m$, вектор $y_m$ может найден как решение линейной задачи наименьших квадратов размера $(m+1)\times m$, где $m\lt \lt n$.

Для решения задачи минимизации приведем матрицу $\overline{H}_m$ к верхнему треугольному виду с помощью вращений Гивенса. На шаге $i$ матрица вращения $\Omega_i$ имеет размеры $(m+1)\times (m+1)$ и имеет следующий вид:

$\Omega_i= \begin{pmatrix} 1 & &&&&&& \\ &\ddots &&&&&&\\ &&1&&&&& \\ &&&c_i&s_i &&& \\ &&&-s_i& c_i &&&\\ &&&&&1&&& \\ &&&&&&\ddots&\\ &&&&&&&1 \\ \end{pmatrix}$

1.3 Вычислительное ядро алгоритма

В алгоритме GMRES присутствуют два ресурсоемких с точки зрения вычислительных мощностей этапа:

• умножение исходной матрицы на вектор при вычислении невязок;

• вычисление скалярных произведений векторов при построении ортонормированного базиса подпространства Крылова.

1.4 Макроструктура алгоритма

Нижеперечисленные шаги алгоритма и входящие в них операции являются наиболее ресурсоемкими. Они выполняются в приведенном порядке. Каждый из них допускает распараллеливание:

• Вычисление нормы невязки для задачи "начальных" условий;

• Вычисление элементов Хессенберговой матрицы - матрично-векторные умножения и скалярные произведения векторов;

• Вычисление произведений разреженных матриц при минимизации невязки.

1.5 Схема реализации последовательного алгоритма

1.5.1 Шаги алгоритма

1. Выбрать произвольное $x_0$; вычислить $r_0=b-Ax_0$ и $v_1=\frac{r_0}{\parallel r_0 \parallel}$

2. Задать матрицу $\overline{H}_m$ размерности $(m+1)\times m$ и всем ее элементам присвоить нулевые значения

3. Для $j=1,\dots,m$ выполнять:

• для $i=1,\dots,j$ выполнять: $h_{i,j}=(Av_j,v_i)$
• $\omega_j=Av_j-\sum_{i=1}^j h_{i,j}v_i$
• $h_{j+1,j}={\parallel \omega_j \parallel}$
• $v_{j+1}=\frac{\omega_j}{h_{j+1,j}}$

4. Вычислить $y_m=\arg\min_{y} \parallel \beta e_1 - \overline{H}_my \parallel,\ y \in \mathbb{R}^m$ и $x_m=x_0+V_my_m$

5. Вычислить $r_m=b-Ax_m$. Если достигнутая точность удовлетворительна, остановиться.

Иначе принять $x_0=x_m$ и $v_1=\frac{r_m}{\parallel r_m \parallel}$ и вернуться к пункту 2.

1.5.2 Решение задачи минимизации невязки

Для нахождения $y_m=\arg\min_{y} \parallel \beta e_1 - \overline{H}_my \parallel$ необходимо выполнить следующие шаги:

1. Найти $m$ матриц вращений Гивенса $\Omega_i(c_i,s_i),\ i=1,\dots,m$ размера $(m+1)\times(m+1)$, где $s_i=\frac{h_{i+1,i}}{\sqrt{h_{i,i}^2+h_{i+1,i}^2}}$, $c_i=\frac{h_{i,i}}{\sqrt{h_{i,i}^2+h_{i+1,i}^2}}$

2. Вычислить $\overline{H}_m^{(m)}=\Omega_1\dots\Omega_m\overline{H}_m$ и $\overline{g}_m=\Omega_1\dots\Omega_m\beta e_1$, удалить последнюю строку и последний элемент соответственно и решить СЛАУ с полученной верхнетреугольной матрицей и правой частью. Полученное решение $y_m$ минимизирует исходный функционал.

1.6 Последовательная сложность алгоритма

Для выполнения одной итерации алгоритма необходимо произвести:

• $3m+1$ делений;

• $2m+1$ вычислений квадратного корня;

• $n^2+\frac{3m+5}{2}n$ умножений;

• $O(\frac{m^2n^2}{2})$ сложений (вычитаний).

1.7 Информационный граф

Метод состоит из двух блоков: ортогонализация и минимизация невязки. При ортогонализации основными операциями являются умножение матрицы на вектор и скалярное умножение векторов, для которых возможен параллелизм, что показано в блоке на темно-синем фоне. В блоке $min$ решается задача минимизации невязки, которая, строго говоря, является отдельной самостоятельной задачей.

Рис.1. Информационная структура алгоритма GMRES

1.8 Ресурс параллелизма алгоритма

Для нахождения матрично-векторных произведений при вычислении невязок матрица СЛАУ должна быть подвергнута декомпозиции на строчные блоки, размеры которых определяются требованиями равномерности загрузки. Соответствующим образом подвергается декомпозиции и вектор правой части. Для наиболее эффективного вычисления скалярных произведений и линейных комбинаций векторов базиса каждый из векторов $v_j$ должен быть разбит на блоки равного размера по числу процессов; каждый из процессов при этом хранит соответствующие блоки всех векторов. Обработка вектора решения дублируется на всех процессах.

1.9 Входные и выходные данные алгоритма

Входные данные:

• матрица $A$ размера $n\times n$;
• вектор-столбец $b$ размера $n$;
• вектор-столбец $x_0$ размера $n$ - начальное приближение;
• натуральное число $m\lt \lt n$, определяющее размерность подпространства Крылова.

Выходные данные:

• вектор-столбец $x$ размера $n$ - решение системы.

1.10 Свойства алгоритма

• Вычислительная мощность: весьма маленькая и равна $m^2$, так как $m\lt \lt n$.

• Устойчивость: GMRES в этом плане является очень хорошим методом. Теоретически можно получить точное решение не более чем за $n$ итераций. Однако, очень приемлемые результаты получаются и за $m\lt \lt n$ итераций. Однако, есть примеры, в которых видно, что первые $m-1$ итераций дают невязку, равную некой константе, а на итерации под номером $m$ получаем точное решение.

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Исследование масштабируемости параллельной реализации итерационного метода решения системы линейных алгебраических уравнений GMRES проводилось в тестовой среде суперкомпьютера "Ломоносов". Алгоритм реализован на языке С с использованием библиотеки IntelMPI версии 4.1.0. Сборка производилась при помощи компилятора, разработанным компанией Intel версии 13.1.0. Набор и границы значений изменяемых параметров запуска:

• число процессов [1 : 128] со значениями, равными степеням двойки;
• размер матрицы [128 : 2048] с шагом 128.

Использованные команды для компиляции и запуска:

   mpicc main3.c -o prog

   #!/bin/bash 
   for a in `seq 0 7`; 
   do 
   let b=2**$a 
   sbatch -p test -n $b impi ./prog
   sleep 600s 
   done

В результате проведенных экспериментов был получен следующий диапазон эффективности реализации алгоритма:

• минимальная эффективность реализации 0.002%;
• максимальная эффективность реализации 4.92%.

На следующих рисунках приведены графики производительности и эффективности выбранной реализации в зависимости от изменяемых параметров запуска. Размерность подпространства Крылова во всех случаях равна 10.

Рис.2 Изменение производительности выполнения в зависимости от числа процессов и размера входной матрицы

Рис.3 Изменение эффективности выполнения в зависимости от числа процессов и размера входной матрицы

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

2.7 Существующие реализации алгоритма

• Реализация алгоритма в библиотеке SciPy [1]
• Реализация алгоритма в библиотеке IML++ [2]
• Библиотека для MATLAB [3]

3 Литература

1. Y. Saad, M.H. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869

2. Е.Е. Тыртышников. Методы численного анализа. – Москва: Академия, 2007

3. М.Ю. Баландин, Э.П. Шурина. Некоторые оценки эффективности параллельных алгоритмов решения СЛАУ на подпространствах Крылова. - Вычислительные технологии, том 3, №1, 1998