Belos Package Browser (Single Doxygen Collection) Development
Public Types | Public Member Functions | Static Public Member Functions | Private Types | Private Attributes
Belos::CaGmres< Scalar, MV, OP > Class Template Reference

Communication-Avoiding GMRES implementation. More...

#include <BelosCaGmres.hpp>

Inheritance diagram for Belos::CaGmres< Scalar, MV, OP >:
Inheritance graph
[legend]

List of all members.

Public Types

typedef Scalar scalar_type
typedef Teuchos::ScalarTraits
< Scalar >::magnitudeType 
magnitude_type
typedef MV multivector_type
typedef OP operator_type

Public Member Functions

 CaGmres (const Teuchos::RCP< LinearProblem< Scalar, MV, OP > > &lp, const Teuchos::RCP< const OrthoManager< Scalar, MV > > &ortho, const Teuchos::RCP< Akx< Scalar, MV > > &akx, const Teuchos::RCP< OutputManager< Scalar > > &outMan, const int maxIterCount, const bool flexible, const Teuchos::RCP< const Teuchos::ParameterList > &params)
 Constructor.
virtual ~CaGmres ()
 Destructor -- need to have it because class is polymorphic.
int initialCandidateBasisLength (const Teuchos::RCP< Akx< Scalar, MV > > &akx, const int maxIterCount, const Teuchos::RCP< const Teuchos::ParameterList > &akxParams) const
virtual bool canExtendBasis () const
 Whether it's legal to call extendBasis()
int newCandidateBasisLength () const
void extendBasis (Teuchos::RCP< MV > &V_cur, Teuchos::RCP< MV > &Z_cur)
 Extend the basis by 1 (or more) vector(s)
bool acceptedCandidateBasis () const
 Whether the subclass "accepted" the candidate basis.
virtual void acceptCandidateBasis (const int newNumVectors)
 Accept the candidate basis and prepare for the next iteration.
void updateEigenInfo ()
virtual void rejectCandidateBasis (const int newNumVectors)
 Reject the candidate basis.
virtual void updateUpperHessenbergMatrix (const Teuchos::RCP< mat_type > &C_Q, const Teuchos::RCP< mat_type > &B_Q, const Teuchos::RCP< mat_type > &C_Z, const Teuchos::RCP< mat_type > &B_Z)
 Update the upper Hessenberg matrix (H_)

Static Public Member Functions

static Teuchos::RCP< const
Teuchos::ParameterList
akxParameters (AkxFactory< Scalar, MV, OP > &akxFactory, const Teuchos::RCP< const Teuchos::ParameterList > &params)
 Return valid list of matrix powers kernel parameters.
static Teuchos::RCP< Akx
< Scalar, MV > > 
initAkx (const Teuchos::RCP< Akx< Scalar, MV > > &akx, const Teuchos::RCP< const Teuchos::ParameterList > &akxParams)
 Return an initialized matrix powers kernel implementation.

Private Types

typedef GmresBase< Scalar, MV, OP > base_type
 Base class typedef.
typedef Teuchos::ScalarTraits
< Scalar > 
STS
typedef Teuchos::ScalarTraits
< magnitude_type
STM
typedef MultiVecTraits< Scalar,
MV > 
MVT
typedef
Teuchos::SerialDenseMatrix
< int, Scalar > 
mat_type

Private Attributes

RCP< ParameterList > params_
 General parameters for the solve.
RCP< ParameterList > akxParams_
 Sublist of params_ specific to the matrix powers kernel.
Teuchos::RCP< Akx< Scalar, MV > > akx_
 Matrix powers kernel implementation.
int candidateBasisLength_
 Candidate basis length in current outer iteration.
int candidateBasisRank_
 Rank of the most recently generated candidate basis.
int numOuterIters_
 Number of "outer" iterations completed thus far.
int maxNumOuterIters_
 Maximum number of "outer" iterations before restart.
std::vector< int > numInnerIters_
 The number of inner iterations per outer iteration.

Detailed Description

template<class Scalar, class MV, class OP>
class Belos::CaGmres< Scalar, MV, OP >

Communication-Avoiding GMRES implementation.

Author:
Mark Hoemmen
Warning:
This is EXPERIMENTAL CODE. DO NOT RELY ON THIS CODE. The interface or implementation may change at any time.

Communication-Avoiding GMRES (CA-GMRES) (Hoemmen 2010) is an iterative method for solving nonsymmetric linear systems. It is equivalent to GMRES (Saad and Schultz 1986) in exact arithmetic.

References:

Definition at line 146 of file BelosCaGmres.hpp.


Member Typedef Documentation

template<class Scalar , class MV , class OP >
typedef Scalar Belos::CaGmres< Scalar, MV, OP >::scalar_type

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 148 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef Teuchos::ScalarTraits<Scalar>::magnitudeType Belos::CaGmres< Scalar, MV, OP >::magnitude_type

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 149 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef MV Belos::CaGmres< Scalar, MV, OP >::multivector_type

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 150 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef OP Belos::CaGmres< Scalar, MV, OP >::operator_type

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 151 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
Belos::CaGmres< Scalar, MV, OP >::base_type [private]

Base class typedef.

Definition at line 156 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef Teuchos::ScalarTraits<Scalar> Belos::CaGmres< Scalar, MV, OP >::STS [private]

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 157 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef Teuchos::ScalarTraits<magnitude_type> Belos::CaGmres< Scalar, MV, OP >::STM [private]

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 158 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef MultiVecTraits<Scalar, MV> Belos::CaGmres< Scalar, MV, OP >::MVT [private]

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 159 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
typedef Teuchos::SerialDenseMatrix<int, Scalar> Belos::CaGmres< Scalar, MV, OP >::mat_type [private]

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 160 of file BelosCaGmres.hpp.


Constructor & Destructor Documentation

template<class Scalar , class MV , class OP >
Belos::CaGmres< Scalar, MV, OP >::CaGmres ( const Teuchos::RCP< LinearProblem< Scalar, MV, OP > > &  lp,
const Teuchos::RCP< const OrthoManager< Scalar, MV > > &  ortho,
const Teuchos::RCP< Akx< Scalar, MV > > &  akx,
const Teuchos::RCP< OutputManager< Scalar > > &  outMan,
const int  maxIterCount,
const bool  flexible,
const Teuchos::RCP< const Teuchos::ParameterList > &  params 
) [inline]

Constructor.

Parameters:
problem[in/out] Linear problem. On input, we use the starting guess (x0) and the initial residual (r0) to initialize the iteration. The iteration may call updateSolution(). On output, if the solution has been updated, the vector returned by getLHS() will be modified.
ortho[in] Orthogonalization manager
akx[in/out] Matrix powers kernel implementation; may be null, in which case a default implementation will be constructed. Callers have the option to provide a previously initialized matrix powers kernel. We offer this option both because the LinearProblem doesn't have a slot for a matrix powers kernel, and because constructing an optimized matrix powers kernel is possibly expensive but need only be done once if the matrix and preconditioner don't change. The object is nonconst because the iteration itself is used to update eigenvalue approximations, which the matrix powers kernel uses to improve numerical stability.
outMan[in/out] Output manager
maxIterCount[in] Maximum number of iterations before restart. The number of vectors' worth of storage this constructor allocates is proportional to this, so choose carefully.
flexible[in] Whether or not to run the Flexible variant of GMRES (FGMRES). This requires twice as much vector storage, but lets the preconditioner change in every iteration. This only works with right preconditioning, not left or split preconditioning. It also may mean that the matrix powers kernel has to revert to a default implementation, rather than a communication-avoiding implementation.
params[in] Options. May be null, in which case default options are used.
Note:
The Flexible GMRES (FGMRES) option forces the matrix powers kernel to use a conventional implementation, rather than an optimized matrix powers kernel implementation. Besides this, CA-GMRES works as usual. However, if the varying preconditioner tends to produce a numerically rank-deficient candidate basis, this will restrict the candidate basis length.

Definition at line 212 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
virtual Belos::CaGmres< Scalar, MV, OP >::~CaGmres ( ) [inline, virtual]

Destructor -- need to have it because class is polymorphic.

Definition at line 227 of file BelosCaGmres.hpp.


Member Function Documentation

template<class Scalar , class MV , class OP >
static Teuchos::RCP<const Teuchos::ParameterList> Belos::CaGmres< Scalar, MV, OP >::akxParameters ( AkxFactory< Scalar, MV, OP > &  akxFactory,
const Teuchos::RCP< const Teuchos::ParameterList > &  params 
) [inline, static]

Return valid list of matrix powers kernel parameters.

If the params argument is nonnull and contains an "Akx" or "Matrix Powers Kernel" sublist, return a deep copy of that sublist. Else, ask the given matrix powers kernel factory for a default list of matrix powers kernel parameters, and return the result.

Returns:
Valid, nonnull list of matrix powers kernel parameters.

Definition at line 239 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
static Teuchos::RCP<Akx<Scalar, MV> > Belos::CaGmres< Scalar, MV, OP >::initAkx ( const Teuchos::RCP< Akx< Scalar, MV > > &  akx,
const Teuchos::RCP< const Teuchos::ParameterList > &  akxParams 
) [inline, static]

Return an initialized matrix powers kernel implementation.

Parameters:
akx[in] Matrix powers kernel implementation, or null if you want this method to instantiate one for you.
params[in] List of parameters for the matrix powers kernel. Must be nonnull and valid.

Definition at line 289 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::initialCandidateBasisLength ( const Teuchos::RCP< Akx< Scalar, MV > > &  akx,
const int  maxIterCount,
const Teuchos::RCP< const Teuchos::ParameterList > &  akxParams 
) const [inline]

Definition at line 307 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
virtual bool Belos::CaGmres< Scalar, MV, OP >::canExtendBasis ( ) const [inline, virtual]

Whether it's legal to call extendBasis()

Whether the basis (bases, if Flexible GMRES) can be extended by computing candidate basis vectors, i.e., whether it's legal to call extendBasis(). Subclasses' implementations of extendBasis() must throw GmresCantExtendBasis if no more candidate basis vectors can be computed.

Implements Belos::GmresBase< Scalar, MV, OP >.

Definition at line 350 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::newCandidateBasisLength ( ) const [inline]

Definition at line 355 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
void Belos::CaGmres< Scalar, MV, OP >::extendBasis ( Teuchos::RCP< MV > &  V_cur,
Teuchos::RCP< MV > &  Z_cur 
) [inline, virtual]

Extend the basis by 1 (or more) vector(s)

Extend the basis (bases, if Flexible GMRES) by 1 (or more) vector(s), without orthogonalizing it/them. Standard GMRES only adds one basis vector at a time; CA-GMRES may add more than one at a time.

Parameters:
V_cur[out] New basis vector(s). The number of column(s) gives the number of basis vector(s) added. This may be a view of member data, rather than freshly allocated storage.
Z_cur[out] If running Flexible GMRES, the preconditioned basis vector(s); else, Teuchos::null. The number of column(s) gives the number of basis vector(s) added. This may be a view of member data, rather than freshly allocated storage.
Warning:
Don't call this if canExtendBasis() returns false.
Note:
This method is non-const so that implementations may use previously allocated space for the basis vectors. (They are not _required_ to use previously allocated space, so this method may, if it wishes, allocate a new multivector to return.)

Implements Belos::GmresBase< Scalar, MV, OP >.

Definition at line 370 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
bool Belos::CaGmres< Scalar, MV, OP >::acceptedCandidateBasis ( ) const [inline, virtual]

Whether the subclass "accepted" the candidate basis.

Implements Belos::GmresBase< Scalar, MV, OP >.

Definition at line 418 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
virtual void Belos::CaGmres< Scalar, MV, OP >::acceptCandidateBasis ( const int  newNumVectors) [inline, virtual]

Accept the candidate basis and prepare for the next iteration.

Note:
Subclasses may override this implementation if they need to do something unusual with the new candidate basis, like checkpoint it.

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 425 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
void Belos::CaGmres< Scalar, MV, OP >::updateEigenInfo ( )
template<class Scalar , class MV , class OP >
virtual void Belos::CaGmres< Scalar, MV, OP >::rejectCandidateBasis ( const int  newNumVectors) [inline, virtual]

Reject the candidate basis.

Note:
Subclasses that retry rejected iterations should override this implementation appropriately.

Reimplemented from Belos::GmresBase< Scalar, MV, OP >.

Definition at line 453 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
virtual void Belos::CaGmres< Scalar, MV, OP >::updateUpperHessenbergMatrix ( const Teuchos::RCP< mat_type > &  C_V,
const Teuchos::RCP< mat_type > &  B_V,
const Teuchos::RCP< mat_type > &  C_Z,
const Teuchos::RCP< mat_type > &  B_Z 
) [inline, virtual]

Update the upper Hessenberg matrix (H_)

Parameters:
C_V[in] Projection coefficients (V_prv^* V_cur) of candidate V basis vector(s)
B_V[in] Normalization coefficients (after projection) of candidate V basis vector(s)
C_Z[in] Projection coefficients (Z_prv^* Z_cur) of candidate Z basis vector(s), or null if there is no Z basis
B_Z[in] Normalization coefficients (after projection) of candidate Z basis vector(s), or null if there is no Z basis
Note:
For Flexible GMRES, it may be desirable to compute or update a rank-revealing decomposition of the upper square submatrix of H_. This is because FGMRES only promises convergence in exact arithmetic if this submatrix is full rank and the computed residual norm is zero. Any decomposition of H_ should not be done in place; this is because updateProjectedLeastSquaresProblem() depends on H_ being intact. That method does not itself modify H_, so implementations of updateUpperHessenbergMatrix() can also rely on H_ being intact.
For an algorithm for updating a rank-revealing decomposition, see e.g., G. W. Stewart, "Updating a rank-revealing ULV decomposition", SIAM J. Matrix Anal. & Appl., Volume 14, Issue 2, pp. 494-499 (April 1993).

Implements Belos::GmresBase< Scalar, MV, OP >.

Definition at line 513 of file BelosCaGmres.hpp.


Member Data Documentation

template<class Scalar , class MV , class OP >
RCP<ParameterList> Belos::CaGmres< Scalar, MV, OP >::params_ [private]

General parameters for the solve.

Definition at line 653 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
RCP<ParameterList> Belos::CaGmres< Scalar, MV, OP >::akxParams_ [private]

Sublist of params_ specific to the matrix powers kernel.

Definition at line 656 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
Teuchos::RCP<Akx<Scalar, MV> > Belos::CaGmres< Scalar, MV, OP >::akx_ [private]

Matrix powers kernel implementation.

Pointer to the matrix powers kernel implementation. This is nonconst, because the matrix powers kernel may make use of eigenvalue approximations collected during the solve. As the solve progresses, these approximations may get better and better.

Note:
Ask this object for the current change-of-basis matrix.
OrthoManager normalizes "in place," whereas TsqrOrthoManager uses internal scratch space. Thus, we compute the matrix powers kernel in place as well, using the storage V_ inherited from GmresBase.
The Flexible GMRES (FGMRES) option forces the matrix powers kernel to use a conventional implementation, rather than an optimized matrix powers kernel implementation. Besides this, CA-GMRES works as usual. If the varying preconditioner tends to produce a numerically rank-deficient candidate basis, this will restrict the candidate basis length, however.

Definition at line 680 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::candidateBasisLength_ [private]

Candidate basis length in current outer iteration.

Number of "inner" iterations the current outer iteration is attempting to execute; the "s" parameter. CA-GMRES may change (either increase or decrease) this adaptively for numerical stability (decrease) or performance (usually increase, though not necessarily).

Definition at line 689 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::candidateBasisRank_ [private]

Rank of the most recently generated candidate basis.

Definition at line 692 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::numOuterIters_ [private]

Number of "outer" iterations completed thus far.

Inclusive range: [0, maxNumOuterIters_]. Incremented at the end of each successful outer iteration, so a value of maxNumOuterIters means that all maxNumOuterIters_ outer iterations were successful.

Definition at line 700 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
int Belos::CaGmres< Scalar, MV, OP >::maxNumOuterIters_ [private]

Maximum number of "outer" iterations before restart.

Definition at line 703 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >
std::vector<int> Belos::CaGmres< Scalar, MV, OP >::numInnerIters_ [private]

The number of inner iterations per outer iteration.

The number of inner iterations in each completed outer iteration. numInnerIters_[k] more basis vectors were generated by successful outer iteration k. This may differ from candidateBasisLength_, since CA-GMRES is allowed to change (either increase or decrease) the latter adaptively. Does not include the initial basis vector (which is the scaled initial residual vector).

Definition at line 714 of file BelosCaGmres.hpp.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines