BiCG process

The biconjugate gradient method is an iterative numerical method for the approximate solution of a linear system of equations , . It is used when the matrix is too large to use direct methods. BiCG stands for bikonjugierte gradient (in English biconjugate gradients ). The method is based on the three-part recursion of the asymmetrical Lanczos method . ${\displaystyle Ax=b}$ ${\displaystyle A\in \mathbb {R} ^{n\times n}}$

The BiCG process was introduced in 1974 by Roger Fletcher .

The algorithm is rarely used in practice because it is quite unstable and prone to rounding errors . It is undoubtedly theoretically interesting because it represents the starting point for the development of the LTPM, the Lanczos-type product methods . These include the (even more unstable) CGS method and as an attempt to stabilize the CGS Method uses the (also rather unstable) BiCGSTAB method by Henk van der Vorst . There are two camps among the experts. Some believe that a better error analysis of the process would reveal reasons for the instabilities and thus lead to stable processes, at least for special cases, others believe that these processes can never be stable, and therefore tend to use GMRES with refinements. As a rule of thumb, users and commercial software packages use adapted direct methods, many researchers and universities work with the LTPM in all kinds of ways.

In understanding the algorithm, it helps to start from two systems of equations to be solved of the form and , where a (generally non- Hermitian ) square matrix and and are given right sides. Usually one is only interested in the solution of the first system of equations mentioned. Two approximate solutions and are also given . ${\displaystyle Ax=b}$ ${\displaystyle A^{H}{\hat {x}}={\hat {b}}}$ ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle b\in \mathbb {C} ^{n}}$ ${\displaystyle {\hat {b}}\in \mathbb {C} ^{n}}$ ${\displaystyle x_{0}\in \mathbb {C} ^{n}}$ ${\displaystyle {\hat {x}}_{0}\in \mathbb {C} ^{n}}$

The process comes in many different variants, including BiOres, BiOmin and BiOdir. These variants result from the different approaches for Krylow subspace procedures and are related to the variants Ores, Omin and Odir of the CG procedure . The best known variant is BiOmin and uses left and right residuals and a pair of biconjugate directions and to minimize residuals. ${\displaystyle r_{j}}$ ${\displaystyle {\hat {r}}_{j}}$ ${\displaystyle p_{j}}$ ${\displaystyle {\hat {p}}_{j}}$

BiOmin (BiCG in the Orthomin variant)

1. Set , ${\displaystyle r_{0}\leftarrow b-Ax_{0}}$ ${\displaystyle p_{0}\leftarrow r_{0}}$
2. Set , ${\displaystyle {\hat {r}}_{0}\leftarrow {\hat {b}}-A^{H}{\hat {x}}_{0}}$ ${\displaystyle {\hat {p}}_{0}\leftarrow {\hat {r}}_{0}}$
3. for do ${\displaystyle k\in \mathbb {N} }$
4. ${\displaystyle \alpha _{k}\leftarrow \langle {\hat {r}}_{k},r_{k}\rangle /\langle {\hat {p}}_{k},Ap_{k}\rangle }$
5. ${\displaystyle x_{k+1}\leftarrow x_{k}+\alpha _{k}p_{k}}$
6. ${\displaystyle {\hat {x}}_{k+1}\leftarrow {\hat {x}}_{k}+{\overline {\alpha _{k}}}{\hat {p}}_{k}}$
7. ${\displaystyle r_{k+1}\leftarrow r_{k}-\alpha _{k}Ap_{k}}$
8. ${\displaystyle {\hat {r}}_{k+1}\leftarrow {\hat {r}}_{k}-{\overline {\alpha _{k}}}A^{H}{\hat {p}}_{k}}$
9. ${\displaystyle \beta _{k}\leftarrow \langle {\hat {r}}_{k+1},r_{k+1}\rangle /\langle {\hat {r}}_{k},r_{k}\rangle }$
10. ${\displaystyle p_{k+1}\leftarrow r_{k+1}+\beta _{k}p_{k}}$
11. ${\displaystyle {\hat {p}}_{k+1}\leftarrow {\hat {r}}_{k+1}+{\overline {\beta _{k}}}{\hat {p}}_{k}}$
12. end for

Line 6 can be omitted if we are only interested in solving the first system of equations. The choice of the second system of equations, i. e., the choice of is not trivial and strongly influences the stability and the convergence behavior of the algorithm. ${\displaystyle {\hat {b}}}$

literature

• Andreas Meister: Numerics of linear systems of equations , 2nd edition, Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7
• Yousef Saad: Iterative Methods for Sparse Linear Systems , 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-89871-534-2