| 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 |