To solve a linear system, BiCGSTAB starts with an initial guess and proceeds as follows:
Choose an arbitrary vector such that, e.g., . denotes the dot product of vectors
For
#
#
#
#
#
#
# If is accurate enough, then set and quit
#
#
#
#
# If is accurate enough, then quit
#
Preconditioned BiCGSTAB
s are usually used to accelerate convergence of iterative methods. To solve a linear system with a preconditioner, preconditioned BiCGSTAB starts with an initial guess and proceeds as follows:
Choose an arbitrary vector such that, e.g.,
For
#
#
#
#
#
#
#
# If is accurate enough then and quit
#
#
#
#
#
# If is accurate enough then quit
#
This formulation is equivalent to applying unpreconditioned BiCGSTAB to the explicitly preconditioned system with, and. In other words, both left- and right-preconditioning are possible with this formulation.
Derivation
BiCG in polynomial form
In BiCG, the search directions and and the residuals and are updated using the following recurrence relations: The constants and are chosen to be where so that the residuals and the search directions satisfy biorthogonality and biconjugacy, respectively, i.e., for, It is straightforward to show that where and are th-degree polynomials in. These polynomials satisfy the following recurrence relations:
Derivation of BiCGSTAB from BiCG
It is unnecessary to explicitly keep track of the residuals and search directions of BiCG. In other words, the BiCG iterations can be performed implicitly. In BiCGSTAB, one wishes to have recurrence relations for where with suitable constants instead of in the hope that will enable faster and smoother convergence in than. It follows from the recurrence relations for and and the definition of that which entails the necessity of a recurrence relation for. This can also be derived from the BiCG relations: Similarly to defining, BiCGSTAB defines Written in vector form, the recurrence relations for and are To derive a recurrence relation for, define The recurrence relation for can then be written as which corresponds to
Determination of BiCGSTAB constants
Now it remains to determine the BiCG constants and and choose a suitable. In BiCG, with Since BiCGSTAB does not explicitly keep track of or, is not immediately computable from this formula. However, it can be related to the scalar Due to biorthogonality, is orthogonal to where is any polynomial of degree in. Hence, only the highest-order terms of and matter in the dot products and. The leading coefficients of and are and, respectively. It follows that and thus A simple formula for can be similarly derived. In BiCG, Similarly to the case above, only the highest-order terms of and matter in the dot productsthanks to biorthogonality and biconjugacy. It happens that and have the same leading coefficient. Thus, they can be replaced simultaneously with in the formula, which leads to Finally, BiCGSTAB selects to minimize in -norm as a function of. This is achieved when giving the optimal value
Generalization
BiCGSTAB can be viewed as a combination of BiCG and GMRES where each BiCG step is followed by a GMRES step to repair the irregular convergence behavior of CGS, as an improvement of which BiCGSTAB was developed. However, due to the use of degree-one minimum residual polynomials, such repair may not be effective if the matrix has large complex eigenpairs. In such cases, BiCGSTAB is likely to stagnate, as confirmed by numerical experiments. One may expect that higher-degree minimum residual polynomials may better handle this situation. This gives rise to algorithms including BiCGSTAB2 and the more general BiCGSTAB. In BiCGSTAB, a GMRES step follows every BiCG steps. BiCGSTAB2 is equivalent to BiCGSTAB with.