Biconjugate gradient stabilized method
Introduction In numerical linear algebra, the '''biconjugate gradient stabilized method''', often abbreviated as '''BiCGSTAB''', is an iterative method developed by H. A. van der Vorst for the numerical solution of nonsymmetric linear systems. It is a variant of the biconjugate gradient method (BiCG) and has faster and smoother convergence than the original BiCG as well as other variants such as the conjugate gradient squared method (CGS). It is a Krylov subspace method. Unlike the original BiCG method, it doesn't require multiplication by the transpose of the system matrix.
Algorithmic steps ===Unpreconditioned BiCGSTAB===In the following sections,  denotes the dot product of vectors. To solve a linear system , BiCGSTAB starts with an initial guess  and proceeds as follows:# # Choose an arbitrary vector  such that , e.g., # # # For ## ## ## ## ## If  is accurate enough, i.e., if '''s''' is small enough, then set  and quit## ## ## ## ## If  is accurate enough, i.e., if  is small enough, then quit## ## ## ===Preconditioned BiCGSTAB===Preconditioners 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 products thanks 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() (i.e., GMRES restarted at each step) 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 .
See also * Biconjugate gradient method* Conjugate gradient squared method* Conjugate gradient method
References * * * *