Метод бисопряженных и устойчивых бисопряженных градиентов

Алгоритм блочного BCG. Алгоритм блочно-бисопряженных градиентов (Bl-BCG) был впервые предложен О'Лири [15] для решения линейных систем. Этот алгоритм является обобщением известного алгоритма BCG [6]. Bl-BCG вычисляет два набора матриц направлений { ,… } и { ,… } которые охватывают блочное крыловское подпространство и , где = B -A и - произвольная матрица размерности N * s. Алгоритм можно представить следующим образом

Алгоритм 4: Блок BCG

1. предполагаемая матрица размерности N×s, = B -A

2. произвольная матрица размерности N×s

3.

4. Для k=0,1,… вычислить

5.

6.

7.

8.

9.

10.

11.

12.

13.

14. end

Алгоритм прерывается, если матрицы единичные. Отметим также, что коэффициенты матрицы, вычисленные в алгоритме, являются решениями линейных систем размерности sxs. Матрицы этих систем могут быть очень плохо обусловлены, и это повлияет на итерации, вычисленные методом Bl-BCG.

Bl-BCG также может демонстрировать неравномерное поведение норм невязки. Чтобы решить эту проблему, можно использовать метод блочного сглаживания [11] или процедуру блочной квази-минимизации (см. [7] и [9]).

Невязки матрицы и направления матрицы, генерируемые Алгоритмом 4, удовлетворяют нижеследующим свойствам.

Теорема 1. Если не происходит разбивки, матрицы, вычисленные по алгоритму Bl-BCG, удовлетворяют следующим свойствам:

1)

2)

3)

4) и все столбцы ортогональны

С этого момента мы предполагаем, что в алгоритме Bl-BCG не происходит сбоев. В следующем подразделе мы используем матричные многочлены, чтобы дать новое выражение для итераций, вычисленных Bl-BCG. Это позволит нам определить блочный устойчивый алгоритм бисопряженных градиентов BiCGSTAB (Biconjugate Gradient Stabilized).

Собрав все эти соотношения, алгоритм Bl-BiCGSTAB можно обобщить следующим образом

Алгоритм 5: Bl-BiCGSTAB

начальное приближение;

произвольная матрица Nxs

Для k=0,1,2… вычислить

end

Обратите внимание, что когда решается одна линейная система, Алгоритм 5 сводится к BiCGSTAB. Однако коэффициент Bk, вычисленный по алгоритму 3 с s = 1, определяется как Bk = - [R0, Tk] 2 / [R0, Vk] 2. Это выражение для Bk проще, чем приведенное в ALGORITHM 2, но требует дополнительного внутреннего произведения.

Алгоритм Bl-BiCGSTAB также будет прерван, если R0Vk является единичной матрицей. В ситуациях, когда матрица R0Vk неединичная, но очень плохо обусловлена, вычисление итераций также будет затронуто. Чтобы преодолеть эти проблемы, можно перезапустить с другим R0.

Благодаря локальным этапам минимизации нормы Фробениуса, Bl-BiCGSTAB имеет более плавную сходимость, чем Bl-BCG. Тем не менее, нормы невязки, полученных BlBiCGSTAB, могут колебаться в некоторых случаях. В этом случае мы можем использовать метод блочного сглаживания, чтобы получить нерастущие Фробениусовские нормы невязок.

Для решения линейной системы (1.1) Bl-BiCGSTAB требует для каждой итерации вычисления 2s матрично-векторных произведений A и общим произведением 6Ns ^ 2 + 4Ns + O (s ^ 3). Это нужно сравнить с s матрично-векторным произведением A, s матрично-векторным произведением At и в общей сложности 8Ns ^ 2 + O (s ^ 3) умножений, необходимых на каждой итерации для Bl-BCG.

Требования к памяти (исключая требования A, X и B) и основные вычислительные затраты (умножения) на итерацию для алгоритмов Bl-BCG и Bl-BiCGSTAB перечислены в таблице 4.1

Таблица 4.1 Требования к памяти и вычислительные затраты (умножения) для Bl-BCG и Bl-BiCGSTAB

Затраты	Bl-BCG	Bl-BCGSTAB
Вектор вида A	s	2s
Вектор вида	s	-
Умножение
Затраты памяти

Затраты Bl-BCG и Bl-BiCGSTAB быстро увеличивается с увеличением числа правых сторон. Однако эти блочные методы решения сходятся за меньшее число итераций, чем их аналоги по единичного решения правых частей, поскольку размерность пространств поиска увеличиваются на Kk (A, R0) и K2k (A, R0) и равны с и 2с соответственно на каждом шаге.

Как показано в таблице 2, Bl-BiCGSTAB находит решение СЛАУ точнее, чем Bl-GMRES или BiCGSTAB, применяемый для отдельной каждой правойчасти линейной системы.

Относительная плотность матриц и использование предобуславливания делают блочные методы менее затратными, а потому они более эффективны, что видно по таблице 4.2

Таблица 4.2 Эффективность Bl-BiCGSTAB по сравнению с Bl-GMRES и BiCGSTAB с использованием предобуславливания ILUT

Matrix	s=5	s=10	s=5	s=10
Utm 1700a (N=1700) (nnz(A)=21313	(10)=0,38	(10)=0,38	=0,62	(10)=0,36
SAYLR4(N=3564) (nnz(A)=22316)	0,77	(10)=0,89	=0,06	(10)=0,12
SHERMAN5(3312) (nnz(A)=20793)	0,93	(10)=0,94	=0,26	(10)=0,16
SHERMAN3(N=5005) (nnz(A)=20033)	0,82	(10)=1,10	=0,27	(10)=0,25

Заключение

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

Список использованных источников

1. Саад Ю. Итерационные методы для разряженных линейных систем. Ю.Саад. 2013. – 171с.

2. Куксенко С.П. Электромагнитная совместимость: вычислительные методы / С.П.Куксенко – Томск, 2018. – 215 с.

3. Куксенко С.П. Итерационные методы решения СЛАУ с плотной матрицей / С.П.Куксенко, Т.Р.Газизов. 2007. – 208с.

4. Jbilou K. Smoothing iterative block methods for linear systems with multiple right-hand sides / J. Comput, 1999. – 97с.

5. D. O’leary, The block conjugate gradient algorithm and related methods /O’leary, 1980. – 293с.

6. Fletcher R. Conjugate gradient methods for indefinite systems, /G.A.Watson, 1974. – 73с.

7. Nillson M. Iterative Solution of Maxwell's Equations in Frequency BlockQMR_iterative maxwell solution / Martin Nillson. – New York, 2004. – 123с.

8. Баландин М.Ю. Методы решения СЛАУ большой размерности /М.Ю.Баландин. Э.П.Шурина. 2000 г. – 15с.

9. Guennouni A. A block version of BICGSTAB for linear systems with multiple right-hand sides / A. El Guennouni, K. Jbilou, H. Sadok. 2003. – 14с.

10. Baker A. H. An efficient block variant of GMRES / A. H. Baker, J.M. Dennis, E. R. Jessup. 2003. – 30с.