| 1 |
/*! \namespace Anasazi |
| 2 |
* \brief Namespace %Anasazi contains the classes, structs, enums and utilities used by the %Anasazi package. |
| 3 |
*/ |
| 4 |
|
| 5 |
/*! @defgroup anasazi_opvec_interfaces Anasazi Operator/Vector Interfaces |
| 6 |
|
| 7 |
%Anasazi utilizes abstract interfaces for operators and multivectors |
| 8 |
to enable the leveraging of existing linear algebra libraries. The |
| 9 |
choice in linear algebra is made through templating, and access to |
| 10 |
the functionality of the underlying objects is provided via the |
| 11 |
traits classes Anasazi::MultiVecTraits and Anasazi::OperatorTraits. |
| 12 |
|
| 13 |
Anasazi::MultiVecTraits requires two template arguments: |
| 14 |
|
| 15 |
- a scalar class (\c ScalarType), describing the field over which the multivectors are defined, and |
| 16 |
- a multivector class (\c MV). |
| 17 |
|
| 18 |
Because %Anasazi implements block eigensolvers, the underlying |
| 19 |
primitive is a collection of column vectors (a multivector) instead of |
| 20 |
a single column vector. The purpose of Anasazi::MultiVecTraits is to |
| 21 |
provide an interface for performing multivector operations (e.g., |
| 22 |
multivector \c AXPY). An example illustrating the manipulation of an |
| 23 |
Epetra_MultiVector using Anasazi::MultiVecTraits follows: |
| 24 |
|
| 25 |
\code |
| 26 |
// build some Epetra_MultiVector objects... |
| 27 |
Epetra_MultiVector A(...), B(...), C(...); |
| 28 |
// ...and a Teuchos::SerialDenseMatrix |
| 29 |
Teuchos::SerialDenseMatrix<int,double> D(...); |
| 30 |
|
| 31 |
typedef Anasazi::MultiVecTraits<double, Epetra_MultiVector> MVT; |
| 32 |
|
| 33 |
// perform C <- 1.0*A + 0.5*B; |
| 34 |
MVT::MvAddMv(1.0, A, 0.5, B, C); |
| 35 |
|
| 36 |
// perform C <- -2.0*A*D + 1.0*C |
| 37 |
MVT::MvTimesMatAddMv(-2.0, A, D, 1.0, C); |
| 38 |
\endcode |
| 39 |
|
| 40 |
As is customary among large-scale eigenvalue software, %Anasazi |
| 41 |
assumes matrix-free access to the problem operators, i.e., only |
| 42 |
matrix-vector products are needed. Therefore, Anasazi::OperatorTraits |
| 43 |
requires three template arguments: |
| 44 |
|
| 45 |
- a scalar class (\c ScalarType), describing the field over which the multivectors are defined, |
| 46 |
- a multivector class (\c MV), describing the domain and range of the operator, and |
| 47 |
- an operator class (\c OP). |
| 48 |
|
| 49 |
The Anasazi::OperatorTraits interface provides a single mechanism: the |
| 50 |
ability to apply an operator of type \c OP to a multivector of type |
| 51 |
<tt>MV</tt>, yielding another multivector of type \c MV. This is |
| 52 |
performed as follows: |
| 53 |
|
| 54 |
\code |
| 55 |
// build some Epetra_MultiVector objects... |
| 56 |
Epetra_MultiVector A(...), B(...); |
| 57 |
// ...and an Epetra operator |
| 58 |
Epetra_Operator Op(...); |
| 59 |
|
| 60 |
// apply the operation B <- Op*A |
| 61 |
typedef Anasazi::OperatorTraits<double, Epetra_MultiVector, Epetra_Operator> OPT; |
| 62 |
OPT::Apply(Op,A,B); |
| 63 |
\endcode |
| 64 |
|
| 65 |
These interfaces are used throughout %Anasazi to manipulate |
| 66 |
multivectors and apply operators, so that no low-level access to the |
| 67 |
underlying objects are needed. Hence, %Anasazi is independent of the |
| 68 |
underlying linear algebra data structures (e.g., serial or parallel, |
| 69 |
real or complex). This allows the generic programming of algorithms |
| 70 |
for the solution of eigenvalue problems. |
| 71 |
|
| 72 |
Calling methods of MultiVecTraits<ScalarType,MV> requires that a |
| 73 |
specialization of MultiVecTraits has been implemented for classes |
| 74 |
<tt>ScalarType</tt> and \c MV. In the case of Epetra_MultiVector and |
| 75 |
Epetra_Operator (which are both defined on the field of doubles), this |
| 76 |
specialization is provided by the %Anasazi adapters to |
| 77 |
Epetra. Specializations of these traits classes provided by %Anasazi |
| 78 |
are: |
| 79 |
|
| 80 |
- Epetra_MultiVector and Epetra_Operator (with scalar type \c double) |
| 81 |
- Thyra::MultiVectorBase and Thyra::LinearOpBase (with arbitrary |
| 82 |
scalar type). This allows %Anasazi to be used with any classes |
| 83 |
that implement the abstract interfaces provided by the Thyra |
| 84 |
package. |
| 85 |
- Tpetra::MultiVector and Tpetra::Operator (with arbitrary scalar type). |
| 86 |
- Anasazi::MultiVec and Anasazi::Operator (with arbitrary scalar |
| 87 |
type). This allows %Anasazi to be used with any classes that |
| 88 |
implement the abstract base classes Anasazi::MultiVec and |
| 89 |
Anasazi::Operator. |
| 90 |
|
| 91 |
Additional specializations of Anasazi::MultiVecTraits and |
| 92 |
Anasazi::OperatorTraits may be created by the user for any other |
| 93 |
multivector and operator class. |
| 94 |
|
| 95 |
*/ |
| 96 |
|
| 97 |
/*! @defgroup anasazi_solver_framework Anasazi Eigensolver Framework |
| 98 |
|
| 99 |
%Anasazi is a framework for developing large-scale iterative |
| 100 |
eigensolvers. When developing such a framework, or even a %collection |
| 101 |
of different solvers, one will notice a large amount of overlap among |
| 102 |
different implementations. For example, two separate eigensolvers may |
| 103 |
utilize the same orthogonalization methods, whereas two different |
| 104 |
implementations of a particular eigensolver may utilize different |
| 105 |
orthogonalization routines. Dividing the different tasks associated |
| 106 |
with an iterative eigensolver into multiple routines enables increased |
| 107 |
code reuse and eases code maintenance. The question arises: how does |
| 108 |
one distill the essence of a particular eigensolver, with the end goal |
| 109 |
of separating this code from the supporting code? |
| 110 |
|
| 111 |
To illustrate this dilemma, consider the block Davidson iteration. |
| 112 |
The essence of the algorithm can be distilled as follows: a |
| 113 |
preconditioner is applied to the current residual vectors, and the |
| 114 |
resulting vectors are used to expand a subspace from which the next |
| 115 |
eigenvector approximations (and their residuals) are |
| 116 |
computed. However, a multitude of choices abound in implementing this |
| 117 |
simple iteration: the size of the computed basis, whether and how the |
| 118 |
method is restarted, the convergence criterion for the algorithm, and |
| 119 |
the use of deflation (locking) mechanisms, etc. |
| 120 |
|
| 121 |
Many of these decisions are separate from the actual |
| 122 |
iteration. Extracting the essential nature of an iteration results in |
| 123 |
a simpler piece of code to develop, debug and maintain. The %Anasazi |
| 124 |
iterative eigensolver framework encourages this by providing three |
| 125 |
distinct entities to fulfill the roles needed by an eigensolver: |
| 126 |
Anasazi::Eigensolver, Anasazi::StatusTest and Anasazi::SolverManager: |
| 127 |
|
| 128 |
- Anasazi::Eigensolver implements the features necessary to describe |
| 129 |
an eigensolver iteration. The iteration state accessors (e.g., |
| 130 |
Anasazi::BlockDavidson::getState() and |
| 131 |
Anasazi::BlockDavidson::initialize()) provide access to private |
| 132 |
member data, and the iteration occurs inside the |
| 133 |
Anasazi::Eigensolver::iterate() method. |
| 134 |
- Anasazi::StatusTest determines when an iteration is to be |
| 135 |
terminated. Inside the Anasazi::Eigensolver::iterate() method, |
| 136 |
the eigensolver queries a Anasazi::StatusTest object in order to |
| 137 |
determine when to return from the Anasazi::Eigensolver::iterate() |
| 138 |
method. |
| 139 |
- Anasazi::SolverManager provides a simplified interface to a |
| 140 |
particular eigensolver. A solver manager implements specific |
| 141 |
features that are independent of the iteration, such as locking |
| 142 |
and restarting. Different Anasazi::SolverManager classes may |
| 143 |
provide varying features and techniques, though they may |
| 144 |
encapsulate the same underlying eigensolver iteration. A |
| 145 |
Anasazi::SolverManager is typically driven by a |
| 146 |
Teuchos::ParameterList, providing a powerful eigensolver via a |
| 147 |
very simple interface. |
| 148 |
|
| 149 |
Returning to the block Davidson example, let's examine how these |
| 150 |
different pieces come into play. The Anasazi::BlockDavidson class |
| 151 |
contains both the state and mechanism of the block Davidson |
| 152 |
iteration. The state consists of the current test basis, the |
| 153 |
eigenvector estimates, the residual vectors, and other support |
| 154 |
data. The eigensolver iteration is described above, and is implemented |
| 155 |
inside the Anasazi::BlockDavidson::iterate() method. On a call to |
| 156 |
Anasazi::BlockDavidson::iterate(), the iteration persists until one of |
| 157 |
two things happens: either the basis becomes full or the |
| 158 |
Anasazi::StatusTest provided to the solver indicates that the |
| 159 |
iteration should be terminated. This is summarized in the following |
| 160 |
code snippet: |
| 161 |
|
| 162 |
\code |
| 163 |
void Anasazi::BlockDavidson::iterate() |
| 164 |
{ |
| 165 |
while (statustest.checkStatus (this) != Anasazi::Passed && getCurSubspaceDim () < getMaxSubspaceDim ()) { |
| 166 |
// ... perform block Davidson iterations ... |
| 167 |
} |
| 168 |
} |
| 169 |
\endcode |
| 170 |
|
| 171 |
The Anasazi::StatusTest::checkStatus() routine takes an |
| 172 |
Anasazi::Eigensolver object as an argument. For a status test to |
| 173 |
examine the status of an arbitrary iteration, we must have some |
| 174 |
abstract interface defining the status of the iteration. This |
| 175 |
interface is defined by the Anasazi::Eigensolver abstract base class, |
| 176 |
the class from which all eigensolvers in %Anasazi derive. The |
| 177 |
following are some example of the methods provided by |
| 178 |
Anasazi::Eigensolver for use by Anasazi::StatusTest objects: |
| 179 |
|
| 180 |
\code |
| 181 |
// Get the current residual norms |
| 182 |
std::vector<MagnitudeType> getResNorms (); |
| 183 |
|
| 184 |
// Get the Ritz values from the previous iteration. |
| 185 |
std::vector<Value<ScalarType> > getRitzValues (); |
| 186 |
|
| 187 |
// Get the current iteration count. |
| 188 |
int getNumIters () const; |
| 189 |
|
| 190 |
// and many more!!! |
| 191 |
\endcode |
| 192 |
|
| 193 |
The termination of Anasazi::Eigensolver::iterate() is partially |
| 194 |
controlled by the status test. In one example, a user wishing to limit |
| 195 |
the number of iterations might utilize Anasazi::StatusTestMaxIters. In |
| 196 |
another example, a user wishing to halt |
| 197 |
Anasazi::Eigensolver::iterate() when the residual norms satisfy a |
| 198 |
certain tolerance might utilize Anasazi::StatusTestResNorm. Arbitrary |
| 199 |
combinations of status tests can be created using a |
| 200 |
Anasazi::StatusTestCombo class, so that the stopping criterion can now |
| 201 |
be affected without modifying the iteration. Furthermore, these |
| 202 |
decisions can be made at runtime. See Anasazi::StatusTest for a list |
| 203 |
of status tests provided by Anasazi. |
| 204 |
|
| 205 |
Recalling again the block Davidson example, we know that after filling |
| 206 |
the allocated basis in the iterate() routine, the eigensolver must be |
| 207 |
restarted with a new subspace. A user wishing to perform a particular |
| 208 |
type of restarting needs access to the entire state of the eigensolver |
| 209 |
and must be able to set this state. Each of the %Anasazi eigensolvers |
| 210 |
provides getState() and initialize() methods for retrieving and |
| 211 |
setting the internal state of the eigensolver. In the case of |
| 212 |
Anasazi::BlockDavidson, this method can be used to access the current |
| 213 |
test basis, which can be used for performing a restart. The user may |
| 214 |
produce a new state for the eigensolver and then pass it to the |
| 215 |
eigensolver via the Anasazi::BlockDavidson::initialize() method. In |
| 216 |
this way, the user has great flexibility in dictating the behavior of |
| 217 |
the algorithm. |
| 218 |
|
| 219 |
However, the code for performing restarting and locking and similar |
| 220 |
features is tedious. Furthermore, much research has been conducted |
| 221 |
into robust and efficient methods for performing these operations. The |
| 222 |
Anasazi::SolverManager exists as a way to encapsulate this |
| 223 |
functionality in an accessible package, suitable for use in other |
| 224 |
codes. The goal of a solver manager is to perform all of the |
| 225 |
communication with a particular eigensolver, providing advanced |
| 226 |
functionality, on behalf of the user. Algorithmic parameters of a |
| 227 |
particular solver manager are set via a Teuchos::ParameterList. The |
| 228 |
only other input provided to the solver manager is the |
| 229 |
Anasazi::Eigenproblem to be solved. Consider the following example: |
| 230 |
|
| 231 |
\code |
| 232 |
// create an eigenproblem |
| 233 |
Anasazi::Eigenproblem prob = ... |
| 234 |
|
| 235 |
// create a parameter list for the Anasazi::BlockDavidsonSolMgr solver manager |
| 236 |
Teuchos::ParameterList pl; |
| 237 |
pl.set("Block Size",5); |
| 238 |
pl.set("Num Blocks",10); |
| 239 |
pl.set("Maximum Restarts",20); |
| 240 |
|
| 241 |
// create a Block Davidson solver manager |
| 242 |
Anasazi::BlockDavidsonSolMgr manager(prob,pl); |
| 243 |
|
| 244 |
// solve the eigenproblem |
| 245 |
Anasazi::ReturnType ret = manager.solve(); |
| 246 |
|
| 247 |
// retrieve the answer |
| 248 |
Anasazi::Eigensolution sltn = prob.getSolution(); |
| 249 |
\endcode |
| 250 |
|
| 251 |
The Anasazi::BlockDavidsonSolMgr solver manager is responsible for |
| 252 |
|
| 253 |
- creating an Anasazi::BlockDavidson eigensolver and initializing it; |
| 254 |
- creating status tests and other utility classes needed by the solver; |
| 255 |
- implementing restarting and locking mechanisms; and |
| 256 |
- putting the computed eigenpairs into the eigenproblem. |
| 257 |
|
| 258 |
The division between eigensolver and solver manager enables the |
| 259 |
following functionality in %Anasazi: |
| 260 |
|
| 261 |
- the partitioning of responsibility among the classes, resulting in |
| 262 |
simpler code and easier development, debugging, reuse and |
| 263 |
maintenance. |
| 264 |
- stratified levels of interaction: either custom, powerful |
| 265 |
low-level interaction with the eigensolver or convenient and |
| 266 |
simple interaction with a robust and flexible solver manager. |
| 267 |
- the flexibility to choose many implementation details through the |
| 268 |
choice of support classes provided to the eigensolver: |
| 269 |
|
| 270 |
- Anasazi::StatusTest |
| 271 |
- Anasazi::OutputManager |
| 272 |
- Anasazi::SortManager |
| 273 |
- Anasazi::OrthoManager |
| 274 |
|
| 275 |
*/ |