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

Материал из Алговики
Перейти к навигации Перейти к поиску

Содержание

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

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

Обобщенный метод минимальных невязок (GMRES) является итерационным методом нахождения решения для системы линейных алгебраических уравнений с произвольной невырожденной матрицей. Метод основан на минимизации квадратичного функционала невязки на подпространствах Крылова. GMRES был предложен Йозефом Саадом и Мартином Шульцем в 1986 году.[1] Наиболее популярные реализации метода основаны на модифицированном алгоритме ортогонализации Грама-Шмидта и на использовании рестартов для управления требуемым объемом памяти.

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

Основная идея метода GMRES основана на минимизации нормы невязки на каждом итерационном шаге. На каждой [math]k[/math]-й итерации точное решение [math]x^* = A^{-1}b[/math] приближается к вектору [math]x_k \in K_k[/math](k-е подпространство Крылова) в том смысле, что

[math] \begin{align} \|r_k{\|}_2 &= \|Ax_k-b{\|}_2 \to \min\limits_{x_k \in K_k} \end{align} [/math]

Приближенное решение [math]x_k[/math] для системы линейных алгебраических уравнений

с произвольной невырожденной матрицей [math]A[/math] ищется в виде:


Исходные данные: Матрица [math]A[/math] (элементы [math]a_{ij}[/math]), начальное приближение [math] x_0 [/math]

Вычисляемые данные: Приближенное решение уравнения [math]x_k[/math].

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

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

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

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

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

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

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

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

In mathematics, the generalized minimal residual method (usually abbreviated GMRES) is an iterative method for the numerical solution of a nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The Arnoldi iteration is used to find this vector.

The GMRES method was developed by Yousef Saad and Martin H. Schultz in 1986.[1] GMRES is a generalization of the MINRES method developed by Chris Paige and Michael Saunders in 1975. GMRES also is a special case of the DIIS method developed by Peter Pulay in 1980. DIIS is also applicable to non-linear systems.

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.4.1 Масштабируемость алгоритма

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. Y.Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Scientific and Stat. Comp. 7: 856-869 (1986).