Biconjugate gradient method

The BiCG method is an iterative numerical method for the approximate solution of a linear equation system. It is used if the matrix is too large for the use of direct methods. BiCG stands for bikonjugierte gradient ( in English biconjugate gradients ). The method is based on the unbalanced Dreitermrekursion Lanczos procedure.

The BiCG method was introduced in 1974 by Roger Fletcher.

The algorithm is often used in practice because it is fairly unstable and prone to rounding error. It is undisputed theoretically interesting because it represents the starting point of the development of LTPM, the Lanczos -type product methods ( Lanczos - type product methods) dar. These include the ( even more unstable ) CGS method and an attempt to stabilize the CGS method, the ( also quite unstable ) BiCGStab process by Henk van der Vorst Among the experts, there are two camps. Some believe that a better error analysis of the method would reveal the reasons for the instability and thus would lead to stable methods for special cases at least, the others believe that these methods can never be stable, and therefore more likely to use GMRES with refinements. As a rule of thumb it can be stated: user and commercial software packages use customized direct methods, many researchers and universities work with the LTPM in all sorts of variations.

It helps in understanding the algorithm of two equations to be solved systems of the form and to go out with a (generally non- Hermitian ) square matrix and right-hand sides are given and. Actually, one is usually only interested in the solution of the first -mentioned equation system. Given are also two approximate solutions and.

The method comes in many different versions, named were Biores, Biomin and BiOdir. These variations result from the different approaches to Krylov subspace methods and are related to the variations Ores, Omin and Odir of the CG method. The most common variant is Biomin and used in addition to the right and left residuals and a pair bikonjugierte directions and Residuenminimierung.

Biomin ( BiCG in the Orthomin variant)

In this case, line 6 can be omitted if we are only interested in the solution of the first equation system. The choice of the second equation system, ie, the choice of is not trivial and strongly affects the stability and the convergence behavior of the algorithm.