Communication-Avoiding GMRES implementation. More...

#include <BelosCaGmres.hpp>

Inheritance diagram for Belos::CaGmres< Scalar, MV, OP >:

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.
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.

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:

M. Hoemmen, "Communication-avoiding Krylov subspace methods," PhD dissertation, University of California Berkeley EECS Department, 2010.
Saad and Schultz, "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems", SISSC, vol. 7, pp. 856-869, 1986.
Saad, "A flexible inner-outer preconditioned GMRES algorithm", SISC, vol. 14, pp. 461-469, 1993.

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.

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.

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 236 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 286 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 304 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 347 of file BelosCaGmres.hpp.

template<class Scalar , class MV , class OP >

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

Definition at line 352 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 367 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 415 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 422 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 450 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 510 of file BelosCaGmres.hpp.

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

BelosCaGmres.hpp

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

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