Debian Codegraph @

packages/anasazi/doc/groups.doc

raw
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 */