KSPCG#

The Preconditioned Conjugate Gradient (PCG) iterative method [HS52] and [MalekStrakovs14]

Options Database Keys#

-ksp_cg_type Hermitian - (for complex matrices only) indicates the matrix is Hermitian, see KSPCGSetType()
-ksp_cg_type symmetric - (for complex matrices only) indicates the matrix is symmetric
-ksp_cg_single_reduction - performs both inner products needed in the algorithm with a single MPI_Allreduce() call, see KSPCGUseSingleReduction()

Notes#

The PCG method requires both the matrix and preconditioner to be symmetric positive (or negative) (semi) definite.

Only left preconditioning is supported; there are several ways to motivate preconditioned CG, but they all produce the same algorithm. One can interpret preconditioning A with B to mean any of the following:

   (1) Solve a left-preconditioned system BAx = Bb, using inv(B) to define an inner product in the algorithm.
   (2) Solve a right-preconditioned system ABy = b, x = By, using B to define an inner product in the algorithm.
   (3) Solve a symmetrically-preconditioned system, E^TAEy = E^Tb, x = Ey, where B = EE^T.
   (4) Solve Ax=b with CG, but use the inner product defined by B to define the method [2].
   In all cases, the resulting algorithm only requires application of B to vectors.

For complex numbers there are two different CG methods, one for Hermitian symmetric matrices and one for non-Hermitian symmetric matrices. Use KSPCGSetType() to indicate which type you are using.

One can use KSPSetComputeEigenvalues() and KSPComputeEigenvalues() to compute the eigenvalues of the (preconditioned) operator

Developer Note#

KSPSolve_CG() should actually query the matrix to determine if it is Hermitian symmetric or not and NOT require the user to indicate it to the KSP object.

References#

[HS52]

Magnus R. Hestenes and Eduard Steifel. Methods of conjugate gradients for solving linear systems. J. Research of the National Bureau of Standards, 49:409–436, 1952.

[MalekStrakovs14]

Josef Málek and Zdeněk Strakoš. Preconditioning and the conjugate gradient method in the context of solving PDEs. SIAM, 2014.