Reference documentation for deal.II version 8.1.0
Classes | Macros | Variables
Preconditioners and Relaxation Operators
Collaboration diagram for Preconditioners and Relaxation Operators:

Classes

class  SparseMIC< number >
 
class  TrilinosWrappers::PreconditionBase
 
class  TrilinosWrappers::PreconditionJacobi
 
class  TrilinosWrappers::PreconditionSSOR
 
class  TrilinosWrappers::PreconditionSOR
 
class  TrilinosWrappers::PreconditionIC
 
class  TrilinosWrappers::PreconditionILU
 
class  TrilinosWrappers::PreconditionILUT
 
class  TrilinosWrappers::PreconditionBlockwiseDirect
 
class  TrilinosWrappers::PreconditionChebyshev
 
class  TrilinosWrappers::PreconditionAMG
 
class  TrilinosWrappers::PreconditionIdentity
 
class  SparseVanka< number >
 
class  SparseBlockVanka< number >
 
class  SparseILU< number >
 
class  PreconditionIdentity
 
class  PreconditionRichardson
 
class  PreconditionUseMatrix< MATRIX, VECTOR >
 
class  PreconditionRelaxation< MATRIX >
 
class  PreconditionJacobi< MATRIX >
 
class  PreconditionSOR< MATRIX >
 
class  PreconditionSSOR< MATRIX >
 
class  PreconditionPSOR< MATRIX >
 
class  PreconditionLACSolver< SOLVER, MATRIX, PRECONDITION >
 
class  PreconditionedMatrix< MATRIX, PRECOND, VECTOR >
 
class  PreconditionChebyshev< MATRIX, VECTOR >
 
class  RelaxationBlock< MATRIX, inverse_type >
 
class  RelaxationBlockJacobi< MATRIX, inverse_type >
 
class  RelaxationBlockSOR< MATRIX, inverse_type >
 
class  RelaxationBlockSSOR< MATRIX, inverse_type >
 
class  SparseLUDecomposition< number >
 
class  SparseDirectUMFPACK
 
class  BlockTrianglePrecondition< number >
 
class  PreconditionBlock< MATRIX, inverse_type >
 
class  PreconditionBlockJacobi< MATRIX, inverse_type >
 
class  PreconditionBlockSOR< MATRIX, inverse_type >
 
class  PreconditionBlockSSOR< MATRIX, inverse_type >
 
class  PreconditionSelector< MATRIX, VECTOR >
 
class  PreconditionLU< number >
 

Macros

#define DEAL_II_DEPRECATED   __attribute__((deprecated))
 

Variables

PreconditionLACSolver DEAL_II_DEPRECATED
 

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(). The generic interface is like for matrices

class PRECONDITIONER
{
template <class VECTOR>
void vmult(VECTOR& dst, const VECTOR& src) const;
template <class VECTOR>
void Tvmult(VECTOR& dst, const VECTOR& src) const;
}

It is implemented in all the preconditioner classes in this module.

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 xk to the next iterate in this way relaxation operators. Their generic interface is

class RELAXATION
{
template <class VECTOR>
void step(VECTOR& newstep, const VECTOR& oldstep, const VECTOR& rhs) const;
template <class VECTOR>
void Tstep(VECTOR& newstep, const VECTOR& oldstep, const VECTOR& rhs) const;
}

The classes with names starting with Relaxation in this module implement this interface, as well as the preconditioners PreconditionJacobi, PreconditionSOR, PreconditionSSORP, reconditionBlockJacobi, 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.

Application of the preconditioner

Preconditioners in deal.II are just considered linear operators. Therefore, in order to be used by deal.II solvers, preconditioners must conform to the standard matrix interface, namely the functions

void vmult (VECTOR& dst, const VECTOR& src) const;
void Tvmult (VECTOR& dst, const VECTOR& src) const;

These functions apply the preconditioning operator to the source vector $src$ and return the result in $dst$ as $dst=P^{-1}src$ or $dst=P^{-T}src$. Preconditioned iterative dolvers use these vmult() functions of the preconditioner. Some solvers may also use Tvmult().

Relaxation methods

Additional to the interface described above, some preconditioners like SOR and Jacobi have been known as iterative methods themselves. For them, an additional interface exists, consisting of the functions

void step (VECTOR& dst, const VECTOR& rhs) const;
void Tstep (VECTOR& dst, const VECTOR& rhs) const;

Here, $src$ is a residual vector and $dst$ is the iterate that is supposed to be updated. In other words, the operation performed by these functions is $dst = dst - P^{-1} (A dst - rhs)$ and $dst = dst - P^{-T} (A dst - rhs)$. The functions are called this way because they perform one step of a fixed point (Richardson) iteration. Note that preconditioners store a reference to the original matrix $A$ during initialization.