Preconditioners and Relaxation Operators

Collaboration diagram for Preconditioners and Relaxation Operators:

Classes
class	BlockTrianglePrecondition< number, BlockVectorType >
class	PreconditionLU< number >
class	PreconditionIdentity
class	PreconditionRichardson
class	PreconditionUseMatrix< MatrixType, VectorType >
class	PreconditionRelaxation< MatrixType >
class	PreconditionJacobi< MatrixType >
class	PreconditionSOR< MatrixType >
class	PreconditionSSOR< MatrixType >
class	PreconditionPSOR< MatrixType >
class	PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >
class	PreconditionBlock< MatrixType, inverse_type >
class	PreconditionBlockJacobi< MatrixType, inverse_type >
class	PreconditionBlockSOR< MatrixType, inverse_type >
class	PreconditionBlockSSOR< MatrixType, inverse_type >
class	PreconditionSelector< MatrixType, VectorType >
class	RelaxationBlock< MatrixType, InverseNumberType, VectorType >
class	RelaxationBlockJacobi< MatrixType, InverseNumberType, VectorType >
class	RelaxationBlockSOR< MatrixType, InverseNumberType, VectorType >
class	RelaxationBlockSSOR< MatrixType, InverseNumberType, VectorType >
class	SparseLUDecomposition< number >
class	SparseDirectUMFPACK
class	SparseILU< number >
class	SparseMIC< number >
class	SparseVanka< number >
class	SparseBlockVanka< number >
class	TrilinosWrappers::PreconditionBase
class	TrilinosWrappers::PreconditionJacobi
class	TrilinosWrappers::PreconditionSSOR
class	TrilinosWrappers::PreconditionSOR
class	TrilinosWrappers::PreconditionBlockJacobi
class	TrilinosWrappers::PreconditionBlockSSOR
class	TrilinosWrappers::PreconditionBlockSOR
class	TrilinosWrappers::PreconditionIC
class	TrilinosWrappers::PreconditionILU
class	TrilinosWrappers::PreconditionILUT
class	TrilinosWrappers::PreconditionBlockwiseDirect
class	TrilinosWrappers::PreconditionChebyshev
class	TrilinosWrappers::PreconditionAMG
class	TrilinosWrappers::PreconditionAMGMueLu
class	TrilinosWrappers::PreconditionIdentity

Detailed Description

Preconditioners

Preconditioners are used to accelerate the iterative solution of linear systems. Typical preconditioners are Jacobi, Gauss-Seidel, or SSOR, but the library also supports more complex ones such as Vanka or incomplete LU decompositions (ILU). In addition, sparse direct solvers can be used as preconditioners when available.

Broadly speaking, preconditioners are operators, which are multiplied with a matrix to improve conditioning. The idea is, that the preconditioned system P^-1Ax = P^-1b is much easier to solve than the original system Ax = b. What this means exactly depends on the structure of the matrix and cannot be discussed here in generality. For symmetric, positive definite matrices A and P, it means that the spectral condition number (the quotient of greatest and smallest eigenvalue) of P^-1A is much smaller than the one of A.

At hand of the simplest example, Richardson iteration, implemented in SolverRichardson, the preconditioned iteration looks like

\[ x^{k+1} = x^k - P^{-1} \bigl(A x^k - b\bigr). \]

Accordingly, preconditioning amounts to applying a linear operator to the residual, and consequently, the action of the preconditioner P^-1 is implemented as vmult(). Templates in deal.II that require a preconditioner indicate the requirement with the PreconditionerType concept. In practice, one can usually treat any matrix-like object which defines vmult() and Tvmult() as a preconditioner. All preconditioner classes in this module implement this interface.

When used in Krylov space methods, it is up to the method, whether it simply replaces multiplications with A by those with P^-1A (for instance SolverBicgstab), or does more sophisticated things. SolverCG for instance uses P^-1 to define an inner product, which is the reason why it requires a symmetric, positive definite operator P.

Relaxation methods

Many preconditioners rely on an additive splitting A = P - N into two matrices. In this case, the iteration step of the Richardson method above can be simplified to

\[ x^{k+1} = P^{-1} \bigl(N x^k + b\bigr), \]

thus avoiding multiplication with A completely. We call operators mapping the previous iterate x^k to the next iterate in this way relaxation operators. Their generic interface is given by the RelaxationType concept. The classes with names starting with Relaxation in this module implement this interface, as well as the preconditioners PreconditionJacobi, PreconditionSOR, PreconditionBlockJacobi, PreconditionBlockSOR, and PreconditionBlockSSOR.

The interface

In this section, we discuss the interface preconditioners usually have to provide to work inside the deal.II library.

Initialization

In order to be able to be stored in containers, all preconditioners have a constructor with no arguments. Since this will typically produce a useless object, all preconditioners have a function

void initialize (...)

This function receives the matrix to be preconditioned as well as additional required parameters and sets up the internal structures of the preconditioner.

Relaxation methods

Some preconditioners, like SOR and Jacobi, were used as iterative solvers long before they were used as preconditioners. Thus, they satisfy both MatrixType and RelaxationType concepts.