Explicitly preconditioned conjugate gradient method for the solution of unsymmetric linear systems

Abstract

For the iterative solution of nonsingular linear system Ay = f of order n the preconditioned system Mx = b is considered, where M = GAF ^T b = Gf y = F ^T x, and the matrices G and F are sparse lower triangular. Their nonzero elements are obtained by alternate minimization of β (M ^T M) with respect to F and G, where β (M ^T M) = n ^{− 1} tr M ^T M/(det M ^T M)^1/n . Such preconditioning makes the matrix M closer to an orthogonal one, which improves the efficiency of the standard CGNE-type algorithms. This conclusion is confirmed by the estimate k ≤ ⌈ n log₂ β (M ^T M) + log₂(ε ⁻¹ )⌉ for the iteration number k needed for the ε times reduction of the error norm ‖ G(f − Ay _k )‖. Numerical examples are given to show the efficiency of the resulting solution algorithms for the indefinite and strongly nonsymmetric linear systems arising from finite difference discretizations of the 2D convection-diffusion equation.

Keywords:

• Nonsymmetric linear systems
• iterative solvers
• conjugate gradients
• explicit preconditioning

C.R. CATERGORIES:

• G.1.0
• G.1.3
• G.1.8