Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
IDRS.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2020 Chris Schoutrop <c.e.m.schoutrop@tue.nl>
5// Copyright (C) 2020 Jens Wehner <j.wehner@esciencecenter.nl>
6// Copyright (C) 2020 Jan van Dijk <j.v.dijk@tue.nl>
7//
8// This Source Code Form is subject to the terms of the Mozilla
9// Public License v. 2.0. If a copy of the MPL was not distributed
10// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
11// SPDX-License-Identifier: MPL-2.0
12
13#ifndef EIGEN_IDRS_H
14#define EIGEN_IDRS_H
15
16// IWYU pragma: private
17#include "./InternalHeaderCheck.h"
18
19namespace Eigen {
20
21namespace internal {
36template <typename Vector, typename RealScalar>
37typename Vector::Scalar omega(const Vector& t, const Vector& s, RealScalar angle) {
38 using Scalar = typename Vector::Scalar;
39 const RealScalar ns = s.stableNorm();
40 const RealScalar nt = t.stableNorm();
41 const Scalar ts = t.dot(s);
42 const RealScalar rho = numext::abs(ts / (nt * ns));
43
44 if (rho < angle) {
45 if (ts == Scalar(0)) {
46 return Scalar(0);
47 }
48 // Original relation for om is given by
49 // om = om * angle / rho;
50 // To alleviate potential (near) division by zero this can be rewritten as
51 // om = angle * (ns / nt) * (ts / abs(ts)) = angle * (ns / nt) * sgn(ts)
52 return angle * (ns / nt) * (ts / numext::abs(ts));
53 }
54 return ts / (nt * nt);
55}
56
57template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
58bool idrs(const MatrixType& A, const Rhs& b, Dest& x, const Preconditioner& precond, Index& iter,
59 typename Dest::RealScalar& relres, Index S, bool smoothing, typename Dest::RealScalar angle,
60 bool replacement) {
61 using RealScalar = typename Dest::RealScalar;
62 using Scalar = typename Dest::Scalar;
63 using VectorType = Matrix<Scalar, Dynamic, 1>;
64 using DenseMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
65 const Index N = b.size();
66 S = numext::mini(S, x.rows());
67 const RealScalar tol = relres;
68 const Index maxit = iter;
69
70 bool trueres = false;
71
72 FullPivLU<DenseMatrixType> lu_solver;
73
74 DenseMatrixType P = internal::random_orthonormal_basis<DenseMatrixType>(N, S);
75
76 const RealScalar normb = b.stableNorm();
77
78 if (normb == RealScalar(0)) {
79 // Solution is the zero vector
80 x.setZero();
81 iter = 0;
82 relres = 0;
83 return true;
84 }
85 // from http://homepage.tudelft.nl/1w5b5/IDRS/manual.pdf
86 // A peak in the residual is considered dangerously high if‖ri‖/‖b‖> C(tol/epsilon).
87 // With epsilon the relative machine precision. The factor tol/epsilon corresponds
88 // to the size of a finite precision number that is so large that the absolute
89 // round-off error in this number, when propagated through the process, makes it
90 // impossible to achieve the required accuracy. The factor C accounts for the
91 // accumulation of round-off errors. This parameter has been set to 10^{-3}.
92 // mp is epsilon/C 10^3 * eps is very conservative, so normally no residual
93 // replacements will take place. It only happens if things go very wrong. Too many
94 // restarts may ruin the convergence.
95 const RealScalar mp = RealScalar(1e3) * NumTraits<Scalar>::epsilon();
96
97 // Compute initial residual
98 const RealScalar tolb = tol * normb; // Relative tolerance
99 VectorType r = b - A * x;
100
101 VectorType x_s, r_s;
102
103 if (smoothing) {
104 x_s = x;
105 r_s = r;
106 }
107
108 RealScalar normr = r.stableNorm();
109
110 if (normr <= tolb) {
111 // Initial guess is a good enough solution
112 iter = 0;
113 relres = normr / normb;
114 return true;
115 }
116
117 DenseMatrixType G = DenseMatrixType::Zero(N, S);
118 DenseMatrixType U = DenseMatrixType::Zero(N, S);
119 DenseMatrixType M = DenseMatrixType::Identity(S, S);
120 VectorType t(N), v(N);
121 Scalar om = 1.;
122
123 const auto restart = [&]() {
124 G.setZero();
125 U.setZero();
126 M.setIdentity();
127 };
128
129 // r and x follow separate recurrences, and A U(:,k) = G(:,k) holds only up to the rounding error of the
130 // bi-orthogonalization, which grows with cond(A) and with the cancellation in G(:,k). The recurrence residual can
131 // then fall below the tolerance while b - A x does not. Accept convergence only when b - A x confirms it, and restart
132 // from the current iterate otherwise. A restart counts as an iteration, which bounds their number. A residual that is
133 // not finite ends the iteration, and the caller reports NoConvergence.
134 const auto done = [&]() {
135 if (!(numext::isfinite)(normr)) {
136 return true;
137 }
138 if (normr > tolb) {
139 return false;
140 }
141 if (smoothing) {
142 x = x_s;
143 }
144 r.noalias() = b - A * x;
145 normr = r.stableNorm();
146 if (normr <= tolb) {
147 return true;
148 }
149 if (smoothing) {
150 r_s = r;
151 }
152 restart();
153 ++iter;
154 return false;
155 };
156
157 // Main iteration loop, build G-spaces:
158 iter = 0;
159
160 while (!done() && iter < maxit) {
161 // New right hand size for small system:
162 VectorType f = (r.adjoint() * P).adjoint();
163
164 for (Index k = 0; k < S; ++k) {
165 // Solve small system and make v orthogonal to P:
166 // c = M(k:s,k:s)\f(k:s);
167 lu_solver.compute(M.block(k, k, S - k, S - k));
168 VectorType c = lu_solver.solve(f.segment(k, S - k));
169 // v = r - G(:,k:s)*c;
170 v.noalias() = r - G.rightCols(S - k) * c;
171 // Preconditioning
172 v = precond.solve(v);
173
174 // Compute new U(:,k) and G(:,k), G(:,k) is in space G_j
175 U.col(k) = U.rightCols(S - k) * c + om * v;
176 G.col(k).noalias() = A * U.col(k);
177
178 // Bi-Orthogonalise the new basis vectors:
179 const RealScalar normg = G.col(k).stableNorm();
180 for (Index i = 0; i < k; ++i) {
181 // alpha = ( P(:,i)'*G(:,k) )/M(i,i);
182 Scalar alpha = P.col(i).dot(G.col(k)) / M(i, i);
183 G.col(k) = G.col(k) - alpha * G.col(i);
184 U.col(k) = U.col(k) - alpha * U.col(i);
185 }
186
187 if (k > 0 && G.col(k).stableNorm() <= mp * normg) {
188 // G(:,k) was in the span of the earlier directions: the Krylov space is exhausted. What is left of G(:,k) is
189 // the rounding error of the loop above, for which A U(:,k) = G(:,k) no longer holds. Restart from the current
190 // iterate with the omega step below.
191 restart();
192 break;
193 }
194
195 // New column of M = P'*G (first k-1 entries are zero)
196 // M(k:s,k) = (G(:,k)'*P(:,k:s))';
197 M.block(k, k, S - k, 1) = (G.col(k).adjoint() * P.rightCols(S - k)).adjoint();
198
199 if (M(k, k) == Scalar(0)) {
200 return false;
201 }
202
203 // Make r orthogonal to q_i, i = 0..k-1
204 Scalar beta = f(k) / M(k, k);
205 r = r - beta * G.col(k);
206 x = x + beta * U.col(k);
207 normr = r.stableNorm();
208
209 if (replacement && normr > tolb / mp) {
210 trueres = true;
211 }
212
213 // Smoothing:
214 if (smoothing) {
215 t = r_s - r;
216 // gamma is a Scalar, but the conversion is not allowed
217 Scalar gamma = t.dot(r_s) / t.squaredNorm();
218 r_s = r_s - gamma * t;
219 x_s = x_s - gamma * (x_s - x);
220 normr = r_s.stableNorm();
221 }
222
223 if (normr < tolb || iter == maxit) {
224 break;
225 }
226
227 // New f = P'*r (first k components are zero)
228 if (k < S - 1) {
229 f.segment(k + 1, S - (k + 1)) = f.segment(k + 1, S - (k + 1)) - beta * M.block(k + 1, k, S - (k + 1), 1);
230 }
231 } // end for
232
233 if (normr < tolb) {
234 continue;
235 }
236
237 // Now we have sufficient vectors in G_j to compute residual in G_j+1
238 // Note: r is already perpendicular to P so v = r
239 // Preconditioning
240 v = r;
241 v = precond.solve(v);
242
243 // Matrix-vector multiplication:
244 t.noalias() = A * v;
245
246 // Computation of a new omega
247 om = internal::omega(t, r, angle);
248
249 if (om == RealScalar(0.0)) {
250 return false;
251 }
252
253 r = r - om * t;
254 x = x + om * v;
255 normr = r.stableNorm();
256
257 if (replacement && normr > tolb / mp) {
258 trueres = true;
259 }
260
261 // Residual replacement?
262 if (trueres && normr < normb) {
263 r.noalias() = b - A * x;
264 trueres = false;
265 }
266
267 // Smoothing:
268 if (smoothing) {
269 t = r_s - r;
270 Scalar gamma = t.dot(r_s) / t.squaredNorm();
271 r_s = r_s - gamma * t;
272 x_s = x_s - gamma * (x_s - x);
273 normr = r_s.stableNorm();
274 }
275
276 iter++;
277
278 } // end while
279
280 if (smoothing) {
281 x = x_s;
282 }
283 relres = normr / normb;
284 return true;
285}
286
287} // namespace internal
288
289template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar> >
290class IDRS;
291
292namespace internal {
293
294template <typename MatrixType_, typename Preconditioner_>
295struct traits<Eigen::IDRS<MatrixType_, Preconditioner_> > {
296 using MatrixType = MatrixType_;
297 using Preconditioner = Preconditioner_;
298};
299
300} // namespace internal
301
344template <typename MatrixType_, typename Preconditioner_>
345class IDRS : public IterativeSolverBase<IDRS<MatrixType_, Preconditioner_> > {
346 public:
347 using MatrixType = MatrixType_;
348 using Scalar = typename MatrixType::Scalar;
349 using RealScalar = typename MatrixType::RealScalar;
350 using Preconditioner = Preconditioner_;
351
352 private:
353 using Base = IterativeSolverBase<IDRS>;
354 using Base::m_error;
355 using Base::m_info;
356 using Base::m_isInitialized;
357 using Base::m_iterations;
358 using Base::matrix;
359 Index m_S = 4;
360 bool m_smoothing = false;
361 RealScalar m_angle = RealScalar(0.7);
362 bool m_residual = false;
363
364 public:
366 IDRS() { Base::m_tolerance = RealScalar(-1); }
367
378 template <typename MatrixDerived>
379 explicit IDRS(const EigenBase<MatrixDerived>& A) : Base(A.derived()) {
380 Base::m_tolerance = RealScalar(-1);
381 }
382
393 RealScalar tolerance() const {
394 return Base::m_tolerance >= RealScalar(0)
395 ? Base::m_tolerance
396 : RealScalar(8) * numext::sqrt(RealScalar(Base::cols())) * NumTraits<RealScalar>::epsilon();
397 }
398
404 template <typename Rhs, typename Dest>
405 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
406 m_iterations = Base::maxIterations();
407 const RealScalar tol = tolerance();
408 m_error = tol;
409
410 bool ret = internal::idrs(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, m_S, m_smoothing, m_angle,
411 m_residual);
412
413 m_info = (!ret) ? NumericalIssue : m_error <= tol ? Success : NoConvergence;
414 }
415
417 void setS(Index S) {
418 if (S < 1) {
419 S = 4;
420 }
421
422 m_S = S;
423 }
424
431 void setSmoothing(bool smoothing) { m_smoothing = smoothing; }
432
443 void setAngle(RealScalar angle) { m_angle = angle; }
444
448 void setResidualUpdate(bool update) { m_residual = update; }
449};
450
451} // namespace Eigen
452
453#endif /* EIGEN_IDRS_H */
The Induced Dimension Reduction method (IDR(s)) is a short-recurrences Krylov method for sparse squar...
Definition IDRS.h:345
void setResidualUpdate(bool update)
Definition IDRS.h:448
IDRS()
Definition IDRS.h:366
RealScalar tolerance() const
Definition IDRS.h:393
IDRS(const EigenBase< MatrixDerived > &A)
Definition IDRS.h:379
void _solve_vector_with_guess_impl(const Rhs &b, Dest &x) const
Definition IDRS.h:405
void setSmoothing(bool smoothing)
Definition IDRS.h:431
void setS(Index S)
Definition IDRS.h:417
void setAngle(RealScalar angle)
Definition IDRS.h:443
Index maxIterations() const
Definition IterativeSolverBase.h:246
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Matrix< Type, Size, 1 > Vector
Size×1 vector of type Type.
Definition Matrix.h:532
Definition EigenBase.h:34