Anasazi Version of the Day
Loading...
Searching...
No Matches
List of all members
Anasazi::Experimental::TraceMin< ScalarType, MV, OP > Class Template Reference

This class implements a TraceMIN iteration, a preconditioned iteration for solving linear symmetric positive definite eigenproblems. More...

#include <AnasaziTraceMin.hpp>

Inheritance diagram for Anasazi::Experimental::TraceMin< ScalarType, MV, OP >:
Anasazi::Experimental::TraceMinBase< ScalarType, MV, OP > Anasazi::Eigensolver< ScalarType, MV, OP >

Constructor/Destructor

 TraceMin (const Teuchos::RCP< Eigenproblem< ScalarType, MV, OP > > &problem, const Teuchos::RCP< SortManager< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > > &sorter, const Teuchos::RCP< OutputManager< ScalarType > > &printer, const Teuchos::RCP< StatusTest< ScalarType, MV, OP > > &tester, const Teuchos::RCP< MatOrthoManager< ScalarType, MV, OP > > &ortho, Teuchos::ParameterList &params)
 TraceMin constructor with eigenproblem, solver utilities, and parameter list of solver options.
 

Additional Inherited Members

- Public Member Functions inherited from Anasazi::Experimental::TraceMinBase< ScalarType, MV, OP >
 TraceMinBase (const RCP< Eigenproblem< ScalarType, MV, OP > > &problem, const RCP< SortManager< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > > &sorter, const RCP< OutputManager< ScalarType > > &printer, const RCP< StatusTest< ScalarType, MV, OP > > &tester, const RCP< MatOrthoManager< ScalarType, MV, OP > > &ortho, Teuchos::ParameterList &params)
 TraceMinBase constructor with eigenproblem, solver utilities, and parameter list of solver options.
 
virtual ~TraceMinBase ()
 Anasazi::TraceMinBase destructor.
 
void iterate ()
 This method performs trace minimization iterations until the status test indicates the need to stop or an error occurs (in which case, an appropriate exception is thrown).
 
void harmonicIterate ()
 
void initialize (TraceMinBaseState< ScalarType, MV > &newstate)
 Initialize the solver to an iterate, optionally providing the other members of the state.
 
void harmonicInitialize (TraceMinBaseState< ScalarType, MV > newstate)
 
void initialize ()
 Initialize the solver with the initial vectors from the eigenproblem or random data.
 
bool isInitialized () const
 Indicates whether the solver has been initialized or not.
 
TraceMinBaseState< ScalarType, MV > getState () const
 Get access to the current state of the eigensolver.
 
int getNumIters () const
 Get the current iteration count.
 
void resetNumIters ()
 Reset the iteration count.
 
RCP< const MV > getRitzVectors ()
 Get access to the current Ritz vectors.
 
std::vector< Value< ScalarType > > getRitzValues ()
 Get the Ritz values for the previous iteration.
 
std::vector< int > getRitzIndex ()
 Get the index used for extracting individual Ritz vectors from getRitzVectors().
 
std::vector< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > getResNorms ()
 Get the current residual norms, computing the norms if they are not up-to-date with the current residual vectors.
 
std::vector< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > getRes2Norms ()
 Get the current residual 2-norms, computing the norms if they are not up-to-date with the current residual vectors.
 
std::vector< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > getRitzRes2Norms ()
 Get the 2-norms of the residuals.
 
int getCurSubspaceDim () const
 Get the dimension of the search subspace used to generate the current eigenvectors and eigenvalues.
 
int getMaxSubspaceDim () const
 Get the maximum dimension allocated for the search subspace. For the trace minimization methods, this always returns numBlocks*blockSize.
 
void setStatusTest (RCP< StatusTest< ScalarType, MV, OP > > test)
 Set a new StatusTest for the solver.
 
RCP< StatusTest< ScalarType, MV, OP > > getStatusTest () const
 Get the current StatusTest used by the solver.
 
const Eigenproblem< ScalarType, MV, OP > & getProblem () const
 Get a constant reference to the eigenvalue problem.
 
void setBlockSize (int blockSize)
 Set the blocksize.
 
int getBlockSize () const
 Get the blocksize used by the iterative solver.
 
void setAuxVecs (const Teuchos::Array< RCP< const MV > > &auxvecs)
 Set the auxiliary vectors for the solver.
 
Teuchos::Array< RCP< const MV > > getAuxVecs () const
 Get the auxiliary vectors for the solver.
 
void setSize (int blockSize, int numBlocks)
 Set the blocksize and number of blocks to be used by the iterative solver in solving this eigenproblem.
 
void currentStatus (std::ostream &os)
 This method requests that the solver print out its current status to the given output stream.
 
- Public Member Functions inherited from Anasazi::Eigensolver< ScalarType, MV, OP >
 Eigensolver ()
 Default Constructor.
 
 Eigensolver (const Teuchos::RCP< Eigenproblem< ScalarType, MV, OP > > &problem, const Teuchos::RCP< SortManager< ScalarType > > &sorter, const Teuchos::RCP< OutputManager< ScalarType > > &printer, const Teuchos::RCP< StatusTest< ScalarType, MV, OP > > &tester, const Teuchos::RCP< OrthoManager< ScalarType, MV > > &ortho, Teuchos::ParameterList &params)
 Basic Constructor.
 
virtual ~Eigensolver ()
 Destructor.
 
virtual void setStatusTest (Teuchos::RCP< StatusTest< ScalarType, MV, OP > > test)=0
 Set a new StatusTest for the solver.
 
virtual void setAuxVecs (const Teuchos::Array< Teuchos::RCP< const MV > > &auxvecs)=0
 Set the auxiliary vectors for the solver.
 
- Protected Types inherited from Anasazi::Experimental::TraceMinBase< ScalarType, MV, OP >
typedef SolverUtils< ScalarType, MV, OP > Utils
 
typedef MultiVecTraits< ScalarType, MV > MVT
 
typedef OperatorTraits< ScalarType, MV, OP > OPT
 
typedef Teuchos::ScalarTraits< ScalarType > SCT
 
typedef SCT::magnitudeType MagnitudeType
 
typedef TraceMinRitzOp< ScalarType, MV, OP > tracemin_ritz_op_type
 
typedef SaddleContainer< ScalarType, MV > saddle_container_type
 
typedef SaddleOperator< ScalarType, MV, tracemin_ritz_op_type > saddle_op_type
 
- Protected Member Functions inherited from Anasazi::Experimental::TraceMinBase< ScalarType, MV, OP >
std::string accuracyCheck (const CheckList &chk, const std::string &where) const
 
ScalarType getTrace () const
 
bool traceLeveled ()
 
std::vector< ScalarType > getClusterResids ()
 
void computeRitzShifts (const std::vector< ScalarType > &clusterResids)
 
std::vector< ScalarType > computeTol ()
 
void solveSaddlePointProblem (RCP< MV > Delta)
 
void solveSaddleProj (RCP< MV > Delta) const
 
void solveSaddleProjPrec (RCP< MV > Delta) const
 
void solveSaddleSchur (RCP< MV > Delta) const
 
void solveSaddleBDPrec (RCP< MV > Delta) const
 
void solveSaddleHSSPrec (RCP< MV > Delta) const
 
void computeKK ()
 
void computeRitzPairs ()
 
void computeX ()
 
void updateKXMX ()
 
void updateResidual ()
 
virtual void addToBasis (const RCP< const MV > Delta)=0
 
virtual void harmonicAddToBasis (const RCP< const MV > Delta)=0
 
- Protected Attributes inherited from Anasazi::Experimental::TraceMinBase< ScalarType, MV, OP >
const MagnitudeType ONE
 
const MagnitudeType ZERO
 
const MagnitudeType NANVAL
 
const RCP< Eigenproblem< ScalarType, MV, OP > > problem_
 
const RCP< SortManager< MagnitudeType > > sm_
 
const RCP< OutputManager< ScalarType > > om_
 
RCP< StatusTest< ScalarType, MV, OP > > tester_
 
const RCP< MatOrthoManager< ScalarType, MV, OP > > orthman_
 
RCP< const OP > Op_
 
RCP< const OP > MOp_
 
RCP< const OP > Prec_
 
bool hasM_
 
RCP< Teuchos::Time > timerOp_
 
RCP< Teuchos::Time > timerMOp_
 
RCP< Teuchos::Time > timerSaddle_
 
RCP< Teuchos::Time > timerSortEval_
 
RCP< Teuchos::Time > timerDS_
 
RCP< Teuchos::Time > timerLocal_
 
RCP< Teuchos::Time > timerCompRes_
 
RCP< Teuchos::Time > timerOrtho_
 
RCP< Teuchos::Time > timerInit_
 
int count_ApplyOp_
 
int count_ApplyM_
 
int blockSize_
 
int numBlocks_
 
bool initialized_
 
int curDim_
 
RCP< MV > X_
 
RCP< MV > KX_
 
RCP< MV > MX_
 
RCP< MV > KV_
 
RCP< MV > MV_
 
RCP< MV > R_
 
RCP< MV > V_
 
RCP< Teuchos::SerialDenseMatrix< int, ScalarType > > KK_
 
RCP< Teuchos::SerialDenseMatrix< int, ScalarType > > ritzVecs_
 
Teuchos::Array< RCP< const MV > > auxVecs_
 
Teuchos::Array< RCP< const MV > > MauxVecs_
 
int numAuxVecs_
 
int iter_
 
std::vector< MagnitudeType > theta_
 
std::vector< MagnitudeType > Rnorms_
 
std::vector< MagnitudeType > R2norms_
 
bool Rnorms_current_
 
bool R2norms_current_
 
RCP< tracemin_ritz_op_type > ritzOp_
 
enum SaddleSolType saddleSolType_
 
bool previouslyLeveled_
 
MagnitudeType previousTrace_
 
bool posSafeToShift_
 
bool negSafeToShift_
 
MagnitudeType largestSafeShift_
 
int NEV_
 
std::vector< ScalarType > ritzShifts_
 
RCP< MV > Z_
 
enum WhenToShiftType whenToShift_
 
enum HowToShiftType howToShift_
 
bool useMultipleShifts_
 
bool considerClusters_
 
bool projectAllVecs_
 
bool projectLockedVecs_
 
bool computeAllRes_
 
bool useRHSR_
 
bool useHarmonic_
 
MagnitudeType traceThresh_
 
MagnitudeType alpha_
 
std::string shiftNorm_
 
MagnitudeType shiftThresh_
 
bool useRelShiftThresh_
 

Detailed Description

template<class ScalarType, class MV, class OP>
class Anasazi::Experimental::TraceMin< ScalarType, MV, OP >

This class implements a TraceMIN iteration, a preconditioned iteration for solving linear symmetric positive definite eigenproblems.

TraceMin works by solving a constrained minimization problem

\[ \textrm{min trace}\left(Y^TKY\right) \textrm{ such that } Y^TMY = I\]

The Y which satisfies this problem is the set of eigenvectors corresponding to the eigenvalues of smallest magnitude. While TraceMin is capable of finding any eigenpairs of $KX = MX \Sigma$ (where K is symmetric and M symmetric positive definite), it converges to the eigenvalues of smallest magnitude of whatever it is given. If a different set of eigenpairs is desired (such as the absolute smallest or the ones closest to a given shift), please perform a spectral transformation before passing the Eigenproblem to the solver.

A TraceMin iteration consists of the following operations:

  1. Solve the saddle point problem

    \[\left[\begin{array}{lr} K & MX \\ X^TM & 0\end{array}\right]
      \left[\begin{array}{l} V \\ \tilde{L}\end{array}\right] =
      \left[\begin{array}{l} 0 \\ I\end{array}\right]\]

  2. Form a section out of the current subspace V such that $X^TKX = \Sigma$ and $X^TMX = I$, where $\Sigma$ is diagonal. $\left(\Sigma,X\right)$ is an approximation of the eigenpairs of smallest magnitude.
  3. Compute the new residual and check for convergence.

The saddle point problem need not be solved to a low relative residual and can be solved either by directly forming the Schur complement or by using a projected Krylov subspace method to solve

\[ \left(PKP\right) \Delta = PMX \textrm{ with } P=I-BX\left(X^TB^2X\right)^{-1}X^TB\]

Then V is constructed as $V=X-\Delta$. If a preconditioner H is used with the projected Krylov method, it is applied as

\[F=\left[I-H^{-1}BX\left(X^TBH^{-1}BX\right)^{-1}X^TB\right]H^{-1}\]

and we solve $FK\Delta = FMX$. (See A Parallel Implementation of the Trace Minimization Eigensolver by Eloy Romero and Jose E. Roman.)

The convergence rate of TraceMin is based on the distribution of eigenvalues. If the eigenvalues are clustered far away from the origin, we have a slow rate of convergence. We can improve our convergence rate by taking advantage of Ritz shifts. Instead of solving $Kx=\lambda Mx$, we solve $\left(K-\sigma M\right) x = \left(\lambda - \sigma\right)Mx$.

This method is described in A Trace Minimization Algorithm for the Generalized Eigenvalue Problem, Ahmed H. Sameh, John A. Wisniewski, SIAM Journal on Numerical Analysis, 19(6), pp. 1243-1259 (1982)

Author
Alicia Klinvex

Definition at line 131 of file AnasaziTraceMin.hpp.

Constructor & Destructor Documentation

◆ TraceMin()

template<class ScalarType , class MV , class OP >
Anasazi::Experimental::TraceMin< ScalarType, MV, OP >::TraceMin ( const Teuchos::RCP< Eigenproblem< ScalarType, MV, OP > > &  problem,
const Teuchos::RCP< SortManager< typename Teuchos::ScalarTraits< ScalarType >::magnitudeType > > &  sorter,
const Teuchos::RCP< OutputManager< ScalarType > > &  printer,
const Teuchos::RCP< StatusTest< ScalarType, MV, OP > > &  tester,
const Teuchos::RCP< MatOrthoManager< ScalarType, MV, OP > > &  ortho,
Teuchos::ParameterList &  params 
)

TraceMin constructor with eigenproblem, solver utilities, and parameter list of solver options.

This constructor takes pointers required by the eigensolver, in addition to a parameter list of options for the eigensolver. These options include the following:

  • "Block Size" - an int specifying the subspace dimension used by the algorithm. This can also be specified using the setBlockSize() method.
  • "Maximum Iterations" - an int specifying the maximum number of TraceMin iterations.
  • "Saddle Solver Type" - a string specifying the algorithm to use in solving the saddle point problem: "Schur Complement" or "Projected Krylov". Default: "Projected Krylov"
    • "Schur Complement": We explicitly form the Schur complement and use it to solve the linear system. This option may be faster, but it is less numerically stable and does not ensure orthogonality between the current iterate and the update.
    • "Projected Krylov": Use a projected iterative method to solve the linear system. If TraceMin was not given a preconditioner, it will use MINRES. Otherwise, it will use GMRES.
  • "Shift Type" - a string specifying how to choose Ritz shifts: "No Shift", "Locked Shift", "Trace Leveled Shift", or "Original Shift". Default: "Trace Leveled Shift"
    • "No Shift": Do not perform Ritz shifts. This option produces guaranteed convergence but converges linearly. Not recommended.
    • "Locked Shift": Do not perform Ritz shifts until an eigenpair is locked. Then, shift based on the largest converged eigenvalue. This option is roughly as safe as "No Shift" but may be faster.
    • "Trace Leveled Shift": Do not perform Ritz shifts until the trace of $X^TKX$ (i.e. the quantity being minimized has stagnated. Then, shift based on the strategy proposed in The trace minimization method for the symmetric generalized eigenvalue problem. Highly recommended.
    • "Original Shift": The original shifting strategy proposed in "The trace minimization method for the symmetric generalized eigenvalue problem." Compute shifts based on the Ritz values, residuals, and clustering of the eigenvalues. May produce incorrect results for indefinite matrices or small subspace dimensions.

Definition at line 215 of file AnasaziTraceMin.hpp.


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