Debian Codegraph @

include/deal.II/lac/eigen.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2000 - 2023 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_eigen_h
16 #define dealii_eigen_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/lac/linear_operator.h>
22 #include <deal.II/lac/precondition.h>
23 #include <deal.II/lac/solver.h>
24 #include <deal.II/lac/solver_cg.h>
25 #include <deal.II/lac/solver_control.h>
26 #include <deal.II/lac/solver_gmres.h>
27 #include <deal.II/lac/solver_minres.h>
28 #include <deal.II/lac/vector_memory.h>
29
30 #include <cmath>
31 #include <limits>
32
33 DEAL_II_NAMESPACE_OPEN
34
35
36 /**
37 * @addtogroup Solvers
38 * @{
39 */
40
41 /**
42 * Power method (von Mises) for eigenvalue computations.
43 *
44 * This method determines the largest eigenvalue of a matrix by applying
45 * increasing powers of this matrix to a vector. If there is an eigenvalue $l$
46 * with dominant absolute value, the iteration vectors will become aligned to
47 * its eigenspace and $Ax = lx$.
48 *
49 * A shift parameter allows to shift the spectrum, so it is possible to
50 * compute the smallest eigenvalue, too.
51 *
52 * Convergence of this method is known to be slow.
53 */
54 template <typename VectorType = Vector<double>>
55 class EigenPower : private SolverBase<VectorType>
56 {
57 public:
58 /**
59 * Declare type of container size.
60 */
61 using size_type = types::global_dof_index;
62
63 /**
64 * Standardized data struct to pipe additional data to the solver.
65 */
66 struct AdditionalData
67 {
68 /**
69 * Shift parameter. This parameter allows to shift the spectrum to compute
70 * a different eigenvalue.
71 */
72 double shift;
73 /**
74 * Constructor. Set the shift parameter.
75 */
76 AdditionalData(const double shift = 0.)
77 : shift(shift)
78 {}
79 };
80
81 /**
82 * Constructor.
83 */
84 EigenPower(SolverControl &cn,
85 VectorMemory<VectorType> &mem,
86 const AdditionalData &data = AdditionalData());
87
88
89 /**
90 * Power method. @p x is the (not necessarily normalized, but nonzero) start
91 * vector for the power method. After the iteration, @p value is the
92 * approximated eigenvalue and @p x is the corresponding eigenvector,
93 * normalized with respect to the l2-norm.
94 */
95 template <typename MatrixType>
96 void
97 solve(double &value, const MatrixType &A, VectorType &x);
98
99 protected:
100 /**
101 * Shift parameter.
102 */
103 AdditionalData additional_data;
104 };
105
106 /**
107 * Inverse iteration (Wieland) for eigenvalue computations.
108 *
109 * This class implements an adaptive version of the inverse iteration by
110 * Wieland.
111 *
112 * There are two choices for the stopping criterion: by default, the norm of
113 * the residual $A x - l x$ is computed. Since this might not converge to zero
114 * for non-symmetric matrices with non-trivial Jordan blocks, it can be
115 * replaced by checking the difference of successive eigenvalues. Use
116 * AdditionalData::use_residual for switching this option.
117 *
118 * Usually, the initial guess entering this method is updated after each step,
119 * replacing it with the new approximation of the eigenvalue. Using a
120 * parameter AdditionalData::relaxation between 0 and 1, this update can be
121 * damped. With relaxation parameter 0, no update is performed. This damping
122 * allows for slower adaption of the shift value to make sure that the method
123 * converges to the eigenvalue closest to the initial guess. This can be aided
124 * by the parameter AdditionalData::start_adaption, which indicates the first
125 * iteration step in which the shift value should be adapted.
126 */
127 template <typename VectorType = Vector<double>>
128 class EigenInverse : private SolverBase<VectorType>
129 {
130 public:
131 /**
132 * Declare type of container size.
133 */
134 using size_type = types::global_dof_index;
135
136 /**
137 * Standardized data struct to pipe additional data to the solver.
138 */
139 struct AdditionalData
140 {
141 /**
142 * Damping of the updated shift value.
143 */
144 double relaxation;
145
146 /**
147 * Start step of adaptive shift parameter.
148 */
149 unsigned int start_adaption;
150 /**
151 * Flag for the stopping criterion.
152 */
153 bool use_residual;
154 /**
155 * Constructor.
156 */
157 AdditionalData(double relaxation = 1.,
158 unsigned int start_adaption = 6,
159 bool use_residual = true)
160 : relaxation(relaxation)
161 , start_adaption(start_adaption)
162 , use_residual(use_residual)
163 {}
164 };
165
166 /**
167 * Constructor.
168 */
169 EigenInverse(SolverControl &cn,
170 VectorMemory<VectorType> &mem,
171 const AdditionalData &data = AdditionalData());
172
173 /**
174 * Inverse method. @p value is the start guess for the eigenvalue and @p x
175 * is the (not necessarily normalized, but nonzero) start vector for the
176 * power method. After the iteration, @p value is the approximated
177 * eigenvalue and @p x is the corresponding eigenvector, normalized with
178 * respect to the l2-norm.
179 */
180 template <typename MatrixType>
181 void
182 solve(double &value, const MatrixType &A, VectorType &x);
183
184 protected:
185 /**
186 * Flags for execution.
187 */
188 AdditionalData additional_data;
189 };
190
191 /** @} */
192 //---------------------------------------------------------------------------
193
194
195 template <typename VectorType>
196 EigenPower<VectorType>::EigenPower(SolverControl &cn,
197 VectorMemory<VectorType> &mem,
198 const AdditionalData &data)
199 : SolverBase<VectorType>(cn, mem)
200 , additional_data(data)
201 {}
202
203
204
205 template <typename VectorType>
206 template <typename MatrixType>
207 void
208 EigenPower<VectorType>::solve(double &value, const MatrixType &A, VectorType &x)
209 {
210 SolverControl::State conv = SolverControl::iterate;
211
212 LogStream::Prefix prefix("Power method");
213
214 typename VectorMemory<VectorType>::Pointer Vy(this->memory);
215 VectorType &y = *Vy;
216 y.reinit(x);
217 typename VectorMemory<VectorType>::Pointer Vr(this->memory);
218 VectorType &r = *Vr;
219 r.reinit(x);
220
221 double length = x.l2_norm();
222 double old_length = 0.;
223 x *= 1. / length;
224
225 A.vmult(y, x);
226
227 // Main loop
228 int iter = 0;
229 for (; conv == SolverControl::iterate; ++iter)
230 {
231 y.add(additional_data.shift, x);
232
233 // Compute absolute value of eigenvalue
234 old_length = length;
235 length = y.l2_norm();
236
237 // do a little trick to compute the sign
238 // with not too much effect of round-off errors.
239 double entry = 0.;
240 size_type i = 0;
241 double thresh = length / x.size();
242 do
243 {
244 Assert(i < x.size(), ExcInternalError());
245 entry = y(i++);
246 }
247 while (std::fabs(entry) < thresh);
248
249 --i;
250
251 // Compute unshifted eigenvalue
252 value = (entry * x(i) < 0.) ? -length : length;
253 value -= additional_data.shift;
254
255 // Update normalized eigenvector
256 x.equ(1 / length, y);
257
258 // Compute residual
259 A.vmult(y, x);
260
261 // Check the change of the eigenvalue
262 // Brrr, this is not really a good criterion
263 conv = this->iteration_status(iter,
264 std::fabs(1. / length - 1. / old_length),
265 x);
266 }
267
268 // in case of failure: throw exception
269 AssertThrow(conv == SolverControl::success,
270 SolverControl::NoConvergence(
271 iter, std::fabs(1. / length - 1. / old_length)));
272
273 // otherwise exit as normal
274 }
275
276 //---------------------------------------------------------------------------
277
278 template <typename VectorType>
279 EigenInverse<VectorType>::EigenInverse(SolverControl &cn,
280 VectorMemory<VectorType> &mem,
281 const AdditionalData &data)
282 : SolverBase<VectorType>(cn, mem)
283 , additional_data(data)
284 {}
285
286
287
288 template <typename VectorType>
289 template <typename MatrixType>
290 void
291 EigenInverse<VectorType>::solve(double &value,
292 const MatrixType &A,
293 VectorType &x)
294 {
295 LogStream::Prefix prefix("Wielandt");
296
297 SolverControl::State conv = SolverControl::iterate;
298
299 // Prepare matrix for solver
300 auto A_op = linear_operator(A);
301 double current_shift = -value;
302 auto A_s = A_op + current_shift * identity_operator(A_op);
303
304 // Define solver
305 ReductionControl inner_control(5000, 1.e-16, 1.e-5, false, false);
306 PreconditionIdentity prec;
307 SolverGMRES<VectorType> solver(inner_control, this->memory);
308
309 // Next step for recomputing the shift
310 unsigned int goal = additional_data.start_adaption;
311
312 // Auxiliary vector
313 typename VectorMemory<VectorType>::Pointer Vy(this->memory);
314 VectorType &y = *Vy;
315 y.reinit(x);
316 typename VectorMemory<VectorType>::Pointer Vr(this->memory);
317 VectorType &r = *Vr;
318 r.reinit(x);
319
320 double length = x.l2_norm();
321 double old_value = value;
322
323 x *= 1. / length;
324
325 // Main loop
326 double res = std::numeric_limits<double>::lowest();
327 size_type iter = 0;
328 for (; conv == SolverControl::iterate; ++iter)
329 {
330 solver.solve(A_s, y, x, prec);
331
332 // Compute absolute value of eigenvalue
333 length = y.l2_norm();
334
335 // do a little trick to compute the sign
336 // with not too much effect of round-off errors.
337 double entry = 0.;
338 size_type i = 0;
339 double thresh = length / x.size();
340 do
341 {
342 Assert(i < x.size(), ExcInternalError());
343 entry = y(i++);
344 }
345 while (std::fabs(entry) < thresh);
346
347 --i;
348
349 // Compute unshifted eigenvalue
350 value = (entry * x(i) < 0. ? -1. : 1.) / length - current_shift;
351
352 if (iter == goal)
353 {
354 const auto &relaxation = additional_data.relaxation;
355 const double new_shift =
356 relaxation * (-value) + (1. - relaxation) * current_shift;
357
358 A_s = A_op + new_shift * identity_operator(A_op);
359 current_shift = new_shift;
360
361 ++goal;
362 }
363
364 // Update normalized eigenvector
365 x.equ(1. / length, y);
366 // Compute residual
367 if (additional_data.use_residual)
368 {
369 y.equ(value, x);
370 A.vmult(r, x);
371 r.sadd(-1., value, x);
372 res = r.l2_norm();
373 // Check the residual
374 conv = this->iteration_status(iter, res, x);
375 }
376 else
377 {
378 res = std::fabs(1. / value - 1. / old_value);
379 conv = this->iteration_status(iter, res, x);
380 }
381 old_value = value;
382 }
383
384 // in case of failure: throw
385 // exception
386 AssertThrow(conv == SolverControl::success,
387 SolverControl::NoConvergence(iter, res));
388 // otherwise exit as normal
389 }
390
391 DEAL_II_NAMESPACE_CLOSE
392
393 #endif