5. The Conjugate Gradient Squared Method¶

5.1. The cgs Module¶

class cgs.CGS(op, **kwargs)¶

Bases: pykrylov.generic.generic.KrylovMethod

A pure Python implementation of the conjugate gradient squared (CGS) algorithm. CGS may be used to solve unsymmetric systems of linear equations, i.e., systems of the form

A x = b

where the operator A may be unsymmetric.

CGS requires 2 operator-vector products with A, 3 dot products and 7 daxpys per iteration. It does not require products with the adjoint of A.

If a preconditioner is supplied, CGS needs to solve two preconditioning systems per iteration. The original description appears in [Sonn89], which our implementation roughly follows.

Reference:

[Sonn89]

P. Sonneveld, CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear Systems, SIAM Journal on Scientific and Statistical Computing 10 (1), pp. 36–52, 1989.

solve(rhs, **kwargs)¶

Solve a linear system with rhs as right-hand side by the CGS method. The vector rhs should be a Numpy array.

Keywords:	guess: Initial guess (Numpy array, default: 0) matvec_max: Max. number of matrix-vector produts (2n)

5.2. Example¶

Here is an example using CGS on a linear system. The coefficient matrix is read from file in Matrix Market format:

import numpy as np
from pykrylov.cgs import CGS as KSolver
from pykrylov.linop import PysparseLinearOperator
from pysparse import spmatrix
from pysparse.pysparseMatrix import PysparseMatrix as sp

A = sp(matrix=spmatrix.ll_mat_from_mtx('jpwh_991.mtx'))
n = A.shape[0]
e = np.ones(n)
rhs = A*e

ks = KSolver( PysparseLinearOperator(A),
              matvec_max=2*n,
              verbose=False,
              reltol = 1.0e-5 )
ks.solve(rhs, guess = 1+np.arange(n, dtype=np.float))

print 'Number of matvecs: ', ks.nMatvec
print 'Initial/final res: %8.2e/%8.2e' % (ks.residNorm0, ks.residNorm)
print 'Direct error: %8.2e' % (np.linalg.norm(ks.bestSolution-e)/sqrt(n))

Running this script produces the following output:

Number of matvecs:  64
Initial/final res: 8.64e+03/4.72e-03
Direct error: 1.47e-04