Debian Codegraph @

include/deal.II/lac/utilities.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2017 - 2024 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_lac_utilities_h
16 #define dealii_lac_utilities_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21 #include <deal.II/base/signaling_nan.h>
22
23 #include <deal.II/lac/lapack_support.h>
24 #include <deal.II/lac/vector_memory.h>
25
26 #include <array>
27 #include <complex>
28 #include <limits>
29
30 DEAL_II_NAMESPACE_OPEN
31
32 namespace Utilities
33 {
34 /**
35 * A collection of linear-algebra utilities.
36 */
37 namespace LinearAlgebra
38 {
39 /**
40 * Return the elements of a continuous Givens rotation matrix and
41 * the norm of the input vector.
42 *
43 * That is for a given
44 * pair @p x and @p y, return $c$ , $s$ and $\sqrt{x^2+y^2}$ such that
45 * \f[
46 * \begin{bmatrix}
47 * c & s \\
48 * -s & c
49 * \end{bmatrix}
50 * \begin{bmatrix}
51 * x \\
52 * y
53 * \end{bmatrix}
54 * =
55 * \begin{bmatrix}
56 * \sqrt{x^2+y^2} \\
57 * 0
58 * \end{bmatrix}
59 * \f]
60 *
61 * @note The function is implemented for real valued numbers only.
62 */
63 template <typename NumberType>
64 std::array<NumberType, 3>
65 givens_rotation(const NumberType &x, const NumberType &y);
66
67 /**
68 * Return the elements of a hyperbolic rotation matrix.
69 *
70 * That is for a given
71 * pair @p x and @p y, return $c$ , $s$ and $r$ such that
72 * \f[
73 * \begin{bmatrix}
74 * c & -s \\
75 * -s & c
76 * \end{bmatrix}
77 * \begin{bmatrix}
78 * x \\
79 * y
80 * \end{bmatrix}
81 * =
82 * \begin{bmatrix}
83 * r \\
84 * 0
85 * \end{bmatrix}
86 * \f]
87 *
88 * Real valued solution only exists if $|x|>|g|$, the function will
89 * throw an error otherwise.
90 *
91 * @note The function is implemented for real valued numbers only.
92 */
93 template <typename NumberType>
94 std::array<NumberType, 3>
95 hyperbolic_rotation(const NumberType &x, const NumberType &y);
96
97 /**
98 * Estimate an upper bound for the largest eigenvalue of @p H by a @p k -step
99 * Lanczos process starting from the initial vector @p v0. Typical
100 * values of @p k are below 10. This estimator computes a k-step Lanczos
101 * decomposition $H V_k=V_k T_k+f_k e_k^T$ where $V_k$ contains k Lanczos
102 * basis, $V_k^TV_k=I_k$, $T_k$ is the tridiagonal Lanczos matrix, $f_k$ is
103 * a residual vector $f_k^TV_k=0$, and $e_k$ is the k-th canonical basis of
104 * $R^k$. The returned value is $ ||T_k||_2 + ||f_k||_2$.
105 * If @p eigenvalues is not <code>nullptr</code>, the eigenvalues of $T_k$ will be written there.
106 *
107 * @p vector_memory is used to allocate memory for temporary vectors.
108 * OperatorType has to provide <code>vmult</code> operation with
109 * VectorType.
110 *
111 * This function implements the algorithm from @cite Zhou2006.
112 *
113 * @note This function uses Lapack routines to compute the largest
114 * eigenvalue of $T_k$.
115 *
116 * @note This function provides an alternate estimate to that obtained from
117 * several steps of SolverCG with
118 * SolverCG<VectorType>::connect_eigenvalues_slot().
119 */
120 template <typename OperatorType, typename VectorType>
121 double
122 lanczos_largest_eigenvalue(const OperatorType &H,
123 const VectorType &v0,
124 const unsigned int k,
125 VectorMemory<VectorType> &vector_memory,
126 std::vector<double> *eigenvalues = nullptr);
127
128 /**
129 * Apply Chebyshev polynomial of the operator @p H to @p x. For a
130 * non-defective operator $H$ with a complete set of eigenpairs
131 * $H \psi_i = \lambda_i \psi_i$, the action of a polynomial filter $p$ is
132 * given by $p(H)x =\sum_i a_i p(\lambda_i) \psi_i$, where $x=: \sum_i a_i
133 * \psi_i$. Thus by appropriately choosing the polynomial filter, one can
134 * alter the eigenmodes contained in $x$.
135 *
136 * This function uses Chebyshev polynomials of first kind. Below is an
137 * example of polynomial $T_n(x)$ of degree $n=8$ normalized to unity at
138 * $-1.2$. <table> <tr> <td align="center">
139 * @image html chebyshev8.png
140 * </td>
141 * </tr>
142 * </table>
143 * By introducing a linear mapping $L$ from @p unwanted_spectrum to
144 * $[-1,1]$, we can dump the corresponding modes in @p x. The higher
145 * the polynomial degree $n$, the more rapid it grows outside of the
146 * $[-1,1]$. In order to avoid numerical overflow, we normalize
147 * polynomial filter to unity at @p tau. Thus, the filtered operator
148 * is $p(H) = T_n(L(H))/T_n(L(\tau))$.
149 *
150 * The action of the Chebyshev filter only requires
151 * evaluation of <code>vmult()</code> of @p H and is based on the
152 * recursion equation for Chebyshev polynomial of degree $n$:
153 * $T_{n}(x) = 2x T_{n-1}(x) - T_{n-2}(x)$ with $T_0(x)=1$ and $T_1(x)=x$.
154 *
155 * @p vector_memory is used to allocate memory for temporary objects.
156 *
157 * This function implements the algorithm (with a minor fix of sign of
158 * $\sigma_1$) from @cite Zhou2014.
159 *
160 * @note If @p tau is equal to
161 * <code>std::numeric_limits<double>::infinity()</code>, no normalization
162 * will be performed.
163 */
164 template <typename OperatorType, typename VectorType>
165 void
166 chebyshev_filter(VectorType &x,
167 const OperatorType &H,
168 const unsigned int n,
169 const std::pair<double, double> unwanted_spectrum,
170 const double tau,
171 VectorMemory<VectorType> &vector_memory);
172
173 } // namespace LinearAlgebra
174
175 } // namespace Utilities
176
177
178 /*------------------------- Implementation ----------------------------*/
179
180 #ifndef DOXYGEN
181
182 namespace internal
183 {
184 namespace UtilitiesImplementation
185 {
186 // We want to avoid including our own LAPACK wrapper header in any external
187 // headers to avoid possible conflicts with other packages that may define
188 // their own such header. At the same time we want to be able to call some
189 // LAPACK functions from the template functions below. To resolve both
190 // problems define some extra wrappers here that can be in the header:
191 template <typename Number>
192 void
193 call_stev(const char jobz,
194 const types::blas_int n,
195 Number *d,
196 Number *e,
197 Number *z,
198 const types::blas_int ldz,
199 Number *work,
200 types::blas_int *info);
201 } // namespace UtilitiesImplementation
202 } // namespace internal
203
204 namespace Utilities
205 {
206 namespace LinearAlgebra
207 {
208 template <typename NumberType>
209 std::array<std::complex<NumberType>, 3>
210 hyperbolic_rotation(const std::complex<NumberType> & /*f*/,
211 const std::complex<NumberType> & /*g*/)
212 {
213 AssertThrow(false, ExcNotImplemented());
214 std::array<NumberType, 3> res;
215 return res;
216 }
217
218
219
220 template <typename NumberType>
221 std::array<NumberType, 3>
222 hyperbolic_rotation(const NumberType &f, const NumberType &g)
223 {
224 Assert(f != 0, ExcDivideByZero());
225 const NumberType tau = g / f;
226 AssertThrow(std::abs(tau) < 1.,
227 ExcMessage(
228 "real-valued Hyperbolic rotation does not exist for (" +
229 std::to_string(f) + "," + std::to_string(g) + ")"));
230 const NumberType u =
231 std::copysign(std::sqrt((1. - tau) * (1. + tau)),
232 f); // <-- more stable than std::sqrt(1.-tau*tau)
233 std::array<NumberType, 3> csr;
234 csr[0] = 1. / u; // c
235 csr[1] = csr[0] * tau; // s
236 csr[2] = f * u; // r
237 return csr;
238 }
239
240
241
242 template <typename NumberType>
243 std::array<std::complex<NumberType>, 3>
244 givens_rotation(const std::complex<NumberType> & /*f*/,
245 const std::complex<NumberType> & /*g*/)
246 {
247 AssertThrow(false, ExcNotImplemented());
248 std::array<NumberType, 3> res;
249 return res;
250 }
251
252
253
254 template <typename NumberType>
255 std::array<NumberType, 3>
256 givens_rotation(const NumberType &f, const NumberType &g)
257 {
258 std::array<NumberType, 3> res;
259 // naive calculation for "r" may overflow or underflow:
260 // c = x / \sqrt{x^2+y^2}
261 // s = -y / \sqrt{x^2+y^2}
262
263 // See Golub 2013, Matrix computations, Chapter 5.1.8
264 // Algorithm 5.1.3
265 // and
266 // Anderson (2000),
267 // Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem.
268 // LAPACK Working Note 150, University of Tennessee, UT-CS-00-454,
269 // December 4, 2000.
270 // Algorithm 4
271 // We implement the latter below:
272 if (g == NumberType())
273 {
274 res[0] = std::copysign(1., f);
275 res[1] = NumberType();
276 res[2] = std::abs(f);
277 }
278 else if (f == NumberType())
279 {
280 res[0] = NumberType();
281 res[1] = std::copysign(1., g);
282 res[2] = std::abs(g);
283 }
284 else if (std::abs(f) > std::abs(g))
285 {
286 const NumberType tau = g / f;
287 const NumberType u = std::copysign(std::sqrt(1. + tau * tau), f);
288 res[0] = 1. / u; // c
289 res[1] = res[0] * tau; // s
290 res[2] = f * u; // r
291 }
292 else
293 {
294 const NumberType tau = f / g;
295 const NumberType u = std::copysign(std::sqrt(1. + tau * tau), g);
296 res[1] = 1. / u; // s
297 res[0] = res[1] * tau; // c
298 res[2] = g * u; // r
299 }
300
301 return res;
302 }
303
304
305
306 template <typename OperatorType, typename VectorType>
307 double
308 lanczos_largest_eigenvalue(const OperatorType &H,
309 const VectorType &v0_,
310 const unsigned int k,
311 VectorMemory<VectorType> &vector_memory,
312 std::vector<double> *eigenvalues)
313 {
314 // Do k-step Lanczos:
315
316 typename VectorMemory<VectorType>::Pointer v(vector_memory);
317 typename VectorMemory<VectorType>::Pointer v0(vector_memory);
318 typename VectorMemory<VectorType>::Pointer f(vector_memory);
319
320 v->reinit(v0_);
321 v0->reinit(v0_);
322 f->reinit(v0_);
323
324 // two vectors to store diagonal and subdiagonal of the Lanczos
325 // matrix
326 std::vector<double> diagonal;
327 std::vector<double> subdiagonal;
328
329 // 1. Normalize input vector
330 (*v) = v0_;
331 double a = v->l2_norm();
332 Assert(a != 0, ExcDivideByZero());
333 (*v) *= 1. / a;
334
335 // 2. Compute f = Hv; a = f*v; f <- f - av; T(0,0)=a;
336 H.vmult(*f, *v);
337 a = (*f) * (*v);
338 f->add(-a, *v);
339 diagonal.push_back(a);
340
341 // 3. Loop over steps
342 for (unsigned int i = 1; i < k; ++i)
343 {
344 // 4. L2 norm of f
345 const double b = f->l2_norm();
346 Assert(b != 0, ExcDivideByZero());
347 // 5. v0 <- v; v <- f/b
348 *v0 = *v;
349 *v = *f;
350 (*v) *= 1. / b;
351 // 6. f = Hv; f <- f - b v0;
352 H.vmult(*f, *v);
353 f->add(-b, *v0);
354 // 7. a = f*v; f <- f - a v;
355 a = (*f) * (*v);
356 f->add(-a, *v);
357 // 8. T(i,i-1) = T(i-1,i) = b; T(i,i) = a;
358 diagonal.push_back(a);
359 subdiagonal.push_back(b);
360 }
361
362 Assert(diagonal.size() == k, ExcInternalError());
363 Assert(subdiagonal.size() == k - 1, ExcInternalError());
364
365 // Use Lapack dstev to get ||T||_2 norm, i.e. the largest eigenvalue
366 // of T
367 const types::blas_int n = k;
368 std::vector<double> Z; // unused for eigenvalues-only ("N") job
369 const types::blas_int ldz = 1; // ^^ (>=1)
370 std::vector<double> work; // ^^
371 types::blas_int info;
372 // call lapack_templates.h wrapper:
373 dealii::internal::UtilitiesImplementation::call_stev('N',
374 n,
375 diagonal.data(),
376 subdiagonal.data(),
377 Z.data(),
378 ldz,
379 work.data(),
380 &info);
381
382 Assert(info == 0, LAPACKSupport::ExcErrorCode("dstev", info));
383
384 if (eigenvalues != nullptr)
385 {
386 eigenvalues->resize(diagonal.size());
387 std::copy(diagonal.begin(), diagonal.end(), eigenvalues->begin());
388 }
389
390 // note that the largest eigenvalue of T is below the largest
391 // eigenvalue of the operator.
392 // return ||T||_2 + ||f||_2, although it is not guaranteed to be an upper
393 // bound.
394 return diagonal[k - 1] + f->l2_norm();
395 }
396
397
398 template <typename OperatorType, typename VectorType>
399 void
400 chebyshev_filter(VectorType &x,
401 const OperatorType &op,
402 const unsigned int degree,
403 const std::pair<double, double> unwanted_spectrum,
404 const double a_L,
405 VectorMemory<VectorType> &vector_memory)
406 {
407 const double a = unwanted_spectrum.first;
408 const double b = unwanted_spectrum.second;
409 Assert(degree > 0, ExcMessage("Only positive degrees make sense."));
410
411 const bool scale = numbers::is_finite(a_L);
412 Assert(
413 a < b,
414 ExcMessage(
415 "Lower bound of the unwanted spectrum should be smaller than the upper bound."));
416
417 Assert(a_L <= a || a_L >= b || !scale,
418 ExcMessage(
419 "Scaling point should be outside of the unwanted spectrum."));
420
421 // Setup auxiliary vectors:
422 typename VectorMemory<VectorType>::Pointer p_y(vector_memory);
423 typename VectorMemory<VectorType>::Pointer p_yn(vector_memory);
424
425 p_y->reinit(x);
426 p_yn->reinit(x);
427
428 // convenience to avoid pointers
429 VectorType &y = *p_y;
430 VectorType &yn = *p_yn;
431
432 // Below is an implementation of
433 // Algorithm 3.2 in Zhou et al, Journal of Computational Physics 274
434 // (2014) 770-782 with **a bugfix for sigma1**. Here is the original
435 // algorithm verbatim:
436 //
437 // [Y]=chebyshev_filter_scaled(X, m, a, b, aL).
438 // e=(b-a)/2; c=(a+b)/2; σ=e/(c-aL); τ=2/σ;
439 // Y=(H∗X-c∗X)∗(σ/e);
440 // for i=2 to m do
441 // σnew =1/(τ - σ);
442 // Yt =(H∗Y - c∗Y)∗(2∗σnew/e)-(σ∗σnew)∗X;
443 // X =Y; Y =Yt; σ =σnew;
444
445 const double e = (b - a) / 2.;
446 const double c = (a + b) / 2.;
447 const double alpha = 1. / e;
448 const double beta = -c / e;
449
450 const double sigma1 =
451 e / (a_L - c); // BUGFIX which is relevant for odd degrees
452 double sigma = scale ? sigma1 : 1.;
453 const double tau = 2. / sigma;
454 op.vmult(y, x);
455 y.sadd(alpha * sigma, beta * sigma, x);
456
457 for (unsigned int i = 2; i <= degree; ++i)
458 {
459 const double sigma_new = scale ? 1. / (tau - sigma) : 1.;
460 op.vmult(yn, y);
461 yn.sadd(2. * alpha * sigma_new, 2. * beta * sigma_new, y);
462 yn.add(-sigma * sigma_new, x);
463 x.swap(y);
464 y.swap(yn);
465 sigma = sigma_new;
466 }
467
468 x.swap(y);
469 }
470
471 } // namespace LinearAlgebra
472 } // namespace Utilities
473
474 #endif
475
476
477
478 DEAL_II_NAMESPACE_CLOSE
479
480
481 #endif