Reference documentation for deal.II version Git f0ecfd8 2016-12-09 00:16:27 +0100
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
PreconditionChebyshev< MatrixType, VectorType, PreconditionerType > Class Template Reference

#include <deal.II/lac/precondition.h>

Inheritance diagram for PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >:
[legend]

Classes

struct  AdditionalData
 

Public Types

typedef types::global_dof_index size_type
 

Public Member Functions

void initialize (const MatrixType &matrix, const AdditionalData &additional_data=AdditionalData())
 
void vmult (VectorType &dst, const VectorType &src) const
 
void Tvmult (VectorType &dst, const VectorType &src) const
 
void step (VectorType &dst, const VectorType &src) const
 
void Tstep (VectorType &dst, const VectorType &src) const
 
void clear ()
 
size_type m () const
 
size_type n () const
 
- Public Member Functions inherited from Subscriptor
 Subscriptor ()
 
 Subscriptor (const Subscriptor &)
 
 Subscriptor (Subscriptor &&)
 
virtual ~Subscriptor ()
 
Subscriptoroperator= (const Subscriptor &)
 
Subscriptoroperator= (Subscriptor &&)
 
void subscribe (const char *identifier=0) const
 
void unsubscribe (const char *identifier=0) const
 
unsigned int n_subscriptions () const
 
void list_subscribers () const
 
template<class Archive >
void serialize (Archive &ar, const unsigned int version)
 

Private Member Functions

void do_chebyshev_loop (VectorType &dst, const VectorType &src) const
 
void do_transpose_chebyshev_loop (VectorType &dst, const VectorType &src) const
 
void estimate_eigenvalues (const VectorType &src) const
 

Private Attributes

SmartPointer< const MatrixType, PreconditionChebyshev< MatrixType, VectorType, PreconditionerType > > matrix_ptr
 
VectorType update1
 
VectorType update2
 
VectorType update3
 
AdditionalData data
 
double theta
 
double delta
 
bool is_initialized
 
Threads::Mutex mutex
 

Additional Inherited Members

- Static Public Member Functions inherited from Subscriptor
static::ExceptionBase & ExcInUse (int arg1, char *arg2, std::string &arg3)
 
static::ExceptionBase & ExcNoSubscriber (char *arg1, char *arg2)
 

Detailed Description

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
class PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >

Preconditioning with a Chebyshev polynomial for symmetric positive definite matrices. This preconditioner is based on an iteration of an inner preconditioner of type PreconditionerType with coefficients that are adapted to optimally cover an eigenvalue range between the largest eigenvalue down to a given lower eigenvalue specified by the optional parameter smoothing_range. The typical use case for the preconditioner is a Jacobi preconditioner specified through DiagonalMatrix, which is also the default value for the preconditioner. Note that if the degree variable is set to zero, the Chebyshev iteration corresponds to a Jacobi preconditioner (or the underlying preconditioner type) with relaxation parameter according to the specified smoothing range.

Besides the default choice of a pointwise Jacobi preconditioner, this class also allows for more advanced types of preconditioners, for example iterating block-Jacobi preconditioners in DG methods.

Apart from the inner preconditioner object, this iteration does not need access to matrix entries, which makes it an ideal ingredient for matrix-free computations. In that context, this class can be used as a multigrid smoother that is trivially parallel (assuming that matrix-vector products are parallel and the inner preconditioner is parallel). Its use is demonstrated in the step-37 tutorial program.

Algorithm execution

The Chebyshev method relies on an estimate of the eigenvalues of the matrix which are computed during the first invocation of vmult(). The algorithm invokes a conjugate gradient solver so symmetry and positive definiteness of the (preconditioned) matrix system are strong requirements. The computation of eigenvalues needs to be deferred until the first vmult() invocation because temporary vectors of the same layout as the source and destination vectors are necessary for these computations and this information gets only available through vmult().

The estimation of eigenvalues can also be bypassed by setting PreconditionChebyshev::AdditionalData::eig_cg_n_iterations to zero and providing sensible values for the largest eigenvalues in the field PreconditionChebyshev::AdditionalData::max_eigenvalue. If the range [max_eigenvalue/smoothing_range, max_eigenvalue] contains all eigenvalues of the preconditioned matrix system and the degree (i.e., number of iterations) is high enough, this class can also be used as a direct solver. For an error estimation of the Chebyshev iteration that can be used to determine the number of iteration, see Varga (2009).

In order to use Chebyshev as a solver, set the degree to numbers::invalid_unsigned_int to force the automatic computation of the number of iterations needed to reach a given target tolerance. In this case, the target tolerance is read from the variable PreconditionChebyshev::AdditionalData::smoothing_range (it needs to be a number less than one to force any iterations obviously).

For details on the algorithm, see section 5.1 of

1 @Book{Varga2009,
2  Title = {Matrix iterative analysis},
3  Author = {Varga, R. S.},
4  Publisher = {Springer},
5  Address = {Berlin},
6  Edition = {2nd},
7  Year = {2009},
8 }

Requirements on the templated classes

The class MatrixType must be derived from Subscriptor because a SmartPointer to MatrixType is held in the class. In particular, this means that the matrix object needs to persist during the lifetime of PreconditionChebyshev. The preconditioner is held in a shared_ptr that is copied into the AdditionalData member variable of the class, so the variable used for initialization can safely be discarded after calling initialize(). Both the matrix and the preconditioner need to provide vmult functions for the matrix-vector product and m functions for accessing the number of rows in the (square) matrix. Furthermore, the matrix must provide el(i,i) methods for accessing the matrix diagonal in case the preconditioner type is a diagonal matrix. Even though it is highly recommended to pass the inverse diagonal entries inside a separate preconditioner object for implementing the Jacobi method (which is the only possible way to operate this class when computing in parallel with MPI because there is no knowledge about the locally stored range of entries that would be needed from the matrix alone), there is a backward compatibility function that can extract the diagonal in case of a serial computation.

Author
Martin Kronbichler, 2009, 2016; extension for full compatibility with LinearOperator class: Jean-Paul Pelteret, 2015

Definition at line 902 of file precondition.h.

Member Typedef Documentation

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
typedef types::global_dof_index PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::size_type

Declare type for container size.

Definition at line 908 of file precondition.h.

Member Function Documentation

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::initialize ( const MatrixType &  matrix,
const AdditionalData additional_data = AdditionalData() 
)

Initialize function. Takes the matrix which is used to form the preconditioner, and additional flags if there are any. This function works only if the input matrix has an operator el(i,i) for accessing all the elements in the diagonal. Alternatively, the diagonal can be supplied with the help of the AdditionalData field.

This function calculates an estimate of the eigenvalue range of the matrix weighted by its diagonal using a modified CG iteration in case the given number of iterations is positive.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::vmult ( VectorType &  dst,
const VectorType &  src 
) const

Compute the action of the preconditioner on src, storing the result in dst.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::Tvmult ( VectorType &  dst,
const VectorType &  src 
) const

Compute the action of the transposed preconditioner on src, storing the result in dst.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::step ( VectorType &  dst,
const VectorType &  src 
) const

Perform one step of the preconditioned Richardson iteration.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::Tstep ( VectorType &  dst,
const VectorType &  src 
) const

Perform one transposed step of the preconditioned Richardson iteration.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::clear ( )

Resets the preconditioner.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
size_type PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::m ( ) const

Return the dimension of the codomain (or range) space. Note that the matrix is of dimension \(m \times n\).

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
size_type PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::n ( ) const

Return the dimension of the domain space. Note that the matrix is of dimension \(m \times n\).

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::do_chebyshev_loop ( VectorType &  dst,
const VectorType &  src 
) const
private

Runs the inner loop of the Chebyshev preconditioner that is the same for vmult() and step() methods.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::do_transpose_chebyshev_loop ( VectorType &  dst,
const VectorType &  src 
) const
private

Runs the inner loop of the Chebyshev preconditioner that is the same for vmult() and step() methods. Uses a separate function to not force users to provide both vmult() and Tvmult() in case only one variant is requested in subsequent calls.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
void PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::estimate_eigenvalues ( const VectorType &  src) const
private

Initializes the factors theta and delta based on an eigenvalue computation. If the user set provided values for the largest eigenvalue in AdditionalData, no computation is performed and the information given by the user is used.

Member Data Documentation

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
SmartPointer<const MatrixType,PreconditionChebyshev<MatrixType,VectorType,PreconditionerType> > PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::matrix_ptr
private

A pointer to the underlying matrix.

Definition at line 1068 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
VectorType PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::update1
mutableprivate

Internal vector used for the vmult operation.

Definition at line 1073 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
VectorType PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::update2
mutableprivate

Internal vector used for the vmult operation.

Definition at line 1078 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
VectorType PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::update3
mutableprivate

Internal vector used for the vmult operation.

Definition at line 1083 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
AdditionalData PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::data
private

Stores the additional data passed to the initialize function, obtained through a copy operation.

Definition at line 1089 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
double PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::theta
private

Average of the largest and smallest eigenvalue under consideration.

Definition at line 1094 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
double PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::delta
private

Half the interval length between the largest and smallest eigenvalue under consideration.

Definition at line 1100 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
bool PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::is_initialized
private

Stores whether the preconditioner has been set up and eigenvalues have been computed.

Definition at line 1106 of file precondition.h.

template<typename MatrixType = SparseMatrix<double>, typename VectorType = Vector<double>, typename PreconditionerType = DiagonalMatrix<VectorType>>
Threads::Mutex PreconditionChebyshev< MatrixType, VectorType, PreconditionerType >::mutex
mutableprivate

A mutex to avoid that multiple vmult() invocations by different threads overwrite the temporary vectors.

Definition at line 1112 of file precondition.h.


The documentation for this class was generated from the following file: