Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
IDRSTABL.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 Mischa Senders <m.j.senders@student.tue.nl>
6// Copyright (C) 2020 Lex Kuijpers <l.kuijpers@student.tue.nl>
7// Copyright (C) 2020 Jens Wehner <j.wehner@esciencecenter.nl>
8// Copyright (C) 2020 Jan van Dijk <j.v.dijk@tue.nl>
9// Copyright (C) 2020 Adithya Vijaykumar
10//
11// This Source Code Form is subject to the terms of the Mozilla
12// Public License v. 2.0. If a copy of the MPL was not distributed
13// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
14// SPDX-License-Identifier: MPL-2.0
15/*
16
17The IDR(S)Stab(L) method is a combination of IDR(S) and BiCGStab(L)
18
19This implementation of IDRSTABL is based on
201. Aihara, K., Abe, K., & Ishiwata, E. (2014). A variant of IDRstab with
21reliable update strategies for solving sparse linear systems. Journal of
22Computational and Applied Mathematics, 259, 244-258.
23 doi:10.1016/j.cam.2013.08.028
24 2. Aihara, K., Abe, K., & Ishiwata, E. (2015). Preconditioned
25IDRSTABL Algorithms for Solving Nonsymmetric Linear Systems. International
26Journal of Applied Mathematics, 45(3).
27 3. Saad, Y. (2003). Iterative Methods for Sparse Linear Systems:
28Second Edition. Philadelphia, PA: SIAM.
29 4. Sonneveld, P., & Van Gijzen, M. B. (2009). IDR(s): A Family
30of Simple and Fast Algorithms for Solving Large Nonsymmetric Systems of Linear
31Equations. SIAM Journal on Scientific Computing, 31(2), 1035-1062.
32 doi:10.1137/070685804
33 5. Sonneveld, P. (2012). On the convergence behavior of IDR (s)
34and related methods. SIAM Journal on Scientific Computing, 34(5), A2576-A2598.
35
36 Right-preconditioning based on Ref. 3 is implemented here.
37*/
38
39#ifndef EIGEN_IDRSTABL_H
40#define EIGEN_IDRSTABL_H
41
42// IWYU pragma: private
43#include "./InternalHeaderCheck.h"
44
45namespace Eigen {
46
47namespace internal {
48
49template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
50bool idrstabl(const MatrixType &mat, const Rhs &rhs, Dest &x, const Preconditioner &precond, Index &iters,
51 typename Dest::RealScalar &tol_error, Index L, Index S) {
52 /*
53 Setup and type definitions.
54 */
55 using Scalar = typename Dest::Scalar;
56 using RealScalar = typename Dest::RealScalar;
57 using VectorType = Matrix<Scalar, Dynamic, 1>;
58 using DenseMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
59
60 const Index N = x.rows();
61
62 Index k = 0; // Iteration counter
63 const Index maxIters = iters;
64
65 const RealScalar rhs_norm = rhs.stableNorm();
66 const RealScalar tol = tol_error * rhs_norm;
67
68 if (rhs_norm == 0) {
69 /*
70 If b==0, then the exact solution is x=0.
71 rhs_norm is needed for other calculations anyways, this exit is a freebie.
72 */
73 x.setZero();
74 iters = 0;
75 tol_error = 0.0;
76 return true;
77 }
78 // Construct decomposition objects beforehand.
79 FullPivLU<DenseMatrixType> lu_solver;
80
81 if (S >= N || L >= N) {
82 /*
83 The matrix is very small, or the choice of L and S is very poor
84 in that case solving directly will be best.
85 */
86 lu_solver.compute(DenseMatrixType(mat));
87 x = lu_solver.solve(rhs);
88 iters = 0;
89 tol_error = (rhs - mat * x).stableNorm() / rhs_norm;
90 return true;
91 }
92
93 // Define maximum sizes to prevent any reallocation later on.
94 DenseMatrixType u(N, L + 1);
95 DenseMatrixType r(N, L + 1);
96
97 DenseMatrixType V(N * (L + 1), S);
98
99 VectorType alpha(S);
100 VectorType gamma(L);
101 VectorType update(N);
102
103 /*
104 Main IDRSTABL algorithm
105 */
106 // Set up the initial residual
107 VectorType x0 = x;
108 r.col(0).noalias() = rhs - mat * x;
109 x.setZero(); // The final solution will be x0+x
110
111 tol_error = r.col(0).stableNorm();
112
113 // FOM = Full orthogonalisation method
114 DenseMatrixType h_FOM = DenseMatrixType::Zero(S, S - 1);
115
116 // Construct an initial U matrix of size N x S
117 DenseMatrixType U(N * (L + 1), S);
118 for (Index col_index = 0; col_index < S; ++col_index) {
119 // Arnoldi-like process to generate a set of orthogonal vectors spanning
120 // {u,A*u,A*A*u,...,A^(S-1)*u}. This construction can be combined with the
121 // Full Orthogonalization Method (FOM) from Ref.3 to provide a possible
122 // early exit with no additional MV.
123 if (col_index != 0) {
124 /*
125 Modified Gram-Schmidt strategy:
126 */
127 VectorType w = mat * precond.solve(u.col(0));
128 for (Index i = 0; i < col_index; ++i) {
129 auto v = U.col(i).head(N);
130 h_FOM(i, col_index - 1) = v.dot(w);
131 w -= h_FOM(i, col_index - 1) * v;
132 }
133 u.col(0) = w;
134 h_FOM(col_index, col_index - 1) = u.col(0).stableNorm();
135
136 if (numext::abs(h_FOM(col_index, col_index - 1)) != RealScalar(0)) {
137 /*
138 This only happens if u is NOT exactly zero. In case it is exactly zero
139 it would imply that that this u has no component in the direction of the
140 current residual.
141
142 By then setting u to zero it will not contribute any further (as it
143 should). Whereas attempting to normalize results in division by zero.
144
145 Such cases occur if:
146 1. The basis of dimension <S is sufficient to exactly solve the linear
147 system. I.e. the current residual is in span{r,Ar,...A^{m-1}r}, where
148 (m-1)<=S.
149 2. Two vectors generated from r, Ar,... are (numerically)
150 parallel.
151
152 In case 1, the exact solution to the system can be obtained from the
153 "Full Orthogonalization Method" (Algorithm 6.4 in the book of Saad),
154 without any additional MV.
155
156 Contrary to what one would suspect, the comparison with ==0.0 for
157 floating-point types is intended here. Any arbitrary non-zero u is fine
158 to continue, however if u contains either NaN or Inf the algorithm will
159 break down.
160 */
161 u.col(0) /= h_FOM(col_index, col_index - 1);
162 }
163 } else {
164 u.col(0) = r.col(0);
165 u.col(0).normalize();
166 }
167
168 U.col(col_index).head(N) = u.col(0);
169 }
170
171 if (S > 1) {
172 // Check for early FOM exit.
173 Scalar beta = r.col(0).stableNorm();
174 VectorType e1 = VectorType::Zero(S - 1);
175 e1(0) = beta;
176 lu_solver.compute(h_FOM.topLeftCorner(S - 1, S - 1));
177 VectorType y = lu_solver.solve(e1);
178 VectorType x2 = x + U.topLeftCorner(N, S - 1) * y;
179
180 // Using proposition 6.7 in Saad, one MV can be saved to calculate the
181 // residual
182 RealScalar FOM_residual = (h_FOM(S - 1, S - 2) * y(S - 2) * U.col(S - 1).head(N)).stableNorm();
183
184 if (FOM_residual < tol) {
185 // Exit, the FOM algorithm was already accurate enough
186 iters = k;
187 // Convert back to the unpreconditioned solution
188 x = precond.solve(x2);
189 // x contains the updates to x0, add those back to obtain the solution
190 x += x0;
191 tol_error = FOM_residual / rhs_norm;
192 return true;
193 }
194 }
195
196 /*
197 Select an initial (N x S) matrix R0.
198 1. Generate random R0, orthonormalize the result.
199 2. This results in R0, however to save memory and compute we only need the
200 adjoint of R0. This is given by the matrix R_T. Additionally, the matrix
201 (mat.adjoint()*R_tilde).adjoint()=R_tilde.adjoint()*mat by the
202 anti-distributivity property of the adjoint. This results in AR_T, which is
203 constant if R_T does not have to be regenerated and can be precomputed.
204 Based on reference 4, this has zero probability in exact arithmetic.
205 */
206
207 // Original IDRSTABL and Kensuke choose S random vectors:
208 DenseMatrixType R_T = internal::random_orthonormal_basis<DenseMatrixType>(N, S).adjoint();
209 DenseMatrixType AR_T = DenseMatrixType(R_T * mat);
210
211 // Pre-allocate sigma.
212 DenseMatrixType sigma(S, S);
213
214 bool reset_while = false; // Should the while loop be reset?
215
216 while (k < maxIters) {
217 for (Index j = 1; j <= L; ++j) {
218 /*
219 The IDR Step
220 */
221 // Construction of the sigma-matrix, and the decomposition of sigma.
222 for (Index i = 0; i < S; ++i) {
223 sigma.col(i).noalias() = AR_T * precond.solve(U.block(N * (j - 1), i, N, 1));
224 }
225
226 lu_solver.compute(sigma);
227 // Obtain the update coefficients alpha
228 if (j == 1) {
229 // alpha=inverse(sigma)*(R_T*r_0);
230 alpha = lu_solver.solve(R_T * r.col(0));
231 } else {
232 // alpha=inverse(sigma)*(AR_T*r_{j-2})
233 alpha = lu_solver.solve(AR_T * precond.solve(r.col(j - 2)));
234 }
235
236 // Obtain new solution and residual from this update
237 update.noalias() = U.topRows(N) * alpha;
238 r.col(0).noalias() -= mat * precond.solve(update);
239 x += update;
240
241 for (Index i = 1; i <= j - 2; ++i) {
242 // This only affects the case L>2
243 r.col(i).noalias() -= U.block(N * (i + 1), 0, N, S) * alpha;
244 }
245 if (j > 1) {
246 // r=[r;A*r_{j-2}]
247 r.col(j - 1).noalias() = mat * precond.solve(r.col(j - 2));
248 }
249 tol_error = r.col(0).stableNorm();
250
251 if (tol_error < tol) {
252 // If at this point the algorithm has converged, exit.
253 reset_while = true;
254 break;
255 }
256
257 bool break_normalization = false;
258 for (Index q = 1; q <= S; ++q) {
259 if (q == 1) {
260 // u = [r_0, ..., r_{j-1}]; u_j is computed below.
261 u.leftCols(j) = r.leftCols(j);
262 } else {
263 // u=[u_1;u_2;...;u_j]
264 u.leftCols(j) = u.middleCols(1, j);
265 }
266
267 // Obtain the update coefficients beta implicitly
268 // beta=lu_sigma.solve(AR_T * u.block(N * (j - 1), 0, N, 1)
269 u.leftCols(j).reshaped() -= U.topRows(N * j) * lu_solver.solve(AR_T * precond.solve(u.col(j - 1)));
270
271 // u=[u;Au_{j-1}]
272 u.col(j).noalias() = mat * precond.solve(u.col(j - 1));
273
274 // Orthonormalize u_j to the columns of V_j(:,1:q-1)
275 if (q > 1) {
276 /*
277 Modified Gram-Schmidt-like procedure to make u orthogonal to the
278 columns of V from Ref. 1.
279
280 The vector mu from Ref. 1 is obtained implicitly:
281 mu=V.block(N * j, 0, N, q - 1).adjoint() * u.block(N * j, 0, N, 1).
282 */
283 for (Index i = 0; i <= q - 2; ++i) {
284 auto v = V.col(i).segment(N * j, N);
285 Scalar h = v.squaredNorm();
286 h = v.dot(u.col(j)) / h;
287 u.leftCols(j + 1).reshaped() -= h * V.col(i).head(N * (j + 1));
288 }
289 }
290 // Normalize u and assign to a column of V
291 Scalar normalization_constant = u.col(j).stableNorm();
292 // If u is exactly zero, this will lead to a NaN. Small, non-zero u is
293 // fine.
294 if (normalization_constant == RealScalar(0.0)) {
295 break_normalization = true;
296 break;
297 } else {
298 u.leftCols(j + 1) /= normalization_constant;
299 }
300
301 V.col(q - 1).head(N * (j + 1)) = u.leftCols(j + 1).reshaped();
302 }
303
304 if (!break_normalization) {
305 U.topRows(N * (j + 1)) = V.topRows(N * (j + 1));
306 } else {
307 // Zero block row j rather than leaving it uninitialized (k == 0) or keeping a stale
308 // block from the previous cycle (k >= 1), so the next step's sigma and alpha are zero.
309 U.middleRows(N * j, N).setZero();
310 }
311 }
312 if (reset_while) {
313 break;
314 }
315
316 // r=[r;mat*r_{L-1}]
317 r.col(L).noalias() = mat * precond.solve(r.col(L - 1));
318
319 /*
320 The polynomial step
321 */
322 ColPivHouseholderQR<DenseMatrixType> qr_solver(r.rightCols(L));
323 gamma = qr_solver.solve(r.col(0));
324
325 // Update solution and residual using the "minimized residual coefficients"
326 update.noalias() = r.leftCols(L) * gamma;
327 x += update;
328 r.col(0).noalias() -= mat * precond.solve(update);
329
330 // Update iteration info
331 ++k;
332 tol_error = r.col(0).stableNorm();
333
334 if (tol_error < tol) {
335 // Slightly early exit by moving the criterion before the update of U,
336 // after the main while loop the result of that calculation would not be
337 // needed.
338 break;
339 }
340
341 /*
342 U=U0-sum(gamma_j*U_j)
343 Consider the first iteration. Then U only contains U0, so at the start of
344 the while-loop U should be U0. Therefore only the first N rows of U have to
345 be updated.
346 */
347 for (Index i = 1; i <= L; ++i) {
348 U.topRows(N) -= U.block(N * i, 0, N, S) * gamma(i - 1);
349 }
350 }
351
352 /*
353 Exit after the while loop terminated.
354 */
355 iters = k;
356 // Convert back to the unpreconditioned solution
357 x = precond.solve(x);
358 // x contains the updates to x0, add those back to obtain the solution
359 x += x0;
360 tol_error = tol_error / rhs_norm;
361 return true;
362}
363
364} // namespace internal
365
366template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar>>
367class IDRSTABL;
368
369namespace internal {
370
371template <typename MatrixType_, typename Preconditioner_>
372struct traits<IDRSTABL<MatrixType_, Preconditioner_>> {
373 using MatrixType = MatrixType_;
374 using Preconditioner = Preconditioner_;
375};
376
377} // namespace internal
378
417
418template <typename MatrixType_, typename Preconditioner_>
419class IDRSTABL : public IterativeSolverBase<IDRSTABL<MatrixType_, Preconditioner_>> {
420 protected:
422 using Base::m_error;
423 using Base::m_info;
424 using Base::m_isInitialized;
425 using Base::m_iterations;
426 using Base::matrix;
427 Index m_L = 2;
428 Index m_S = 4;
429
430 public:
431 using MatrixType = MatrixType_;
432 using Scalar = typename MatrixType::Scalar;
433 using RealScalar = typename MatrixType::RealScalar;
434 using Preconditioner = Preconditioner_;
435
436 public:
438 IDRSTABL() = default;
439
450 template <typename MatrixDerived>
451 explicit IDRSTABL(const EigenBase<MatrixDerived> &A) : Base(A.derived()) {}
452
459 template <typename Rhs, typename Dest>
460 void _solve_vector_with_guess_impl(const Rhs &b, Dest &x) const {
461 m_iterations = Base::maxIterations();
462 m_error = Base::m_tolerance;
463 bool ret = internal::idrstabl(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, m_L, m_S);
464
465 m_info = (!ret) ? NumericalIssue : m_error <= 10 * Base::m_tolerance ? Success : NoConvergence;
466 }
467
470 void setL(Index L) {
471 eigen_assert(L >= 1 && "L needs to be positive");
472 m_L = L;
473 }
474
476 void setS(Index S) {
477 eigen_assert(S >= 1 && "S needs to be positive");
478 m_S = S;
479 }
480};
481
482} // namespace Eigen
483
484#endif /* EIGEN_IDRSTABL_H */
The IDR(s)STAB(l) is a combination of IDR(s) and BiCGSTAB(l). It is a short-recurrences Krylov method...
Definition IDRSTABL.h:419
void setL(Index L)
Definition IDRSTABL.h:470
void setS(Index S)
Definition IDRSTABL.h:476
IDRSTABL(const EigenBase< MatrixDerived > &A)
Definition IDRSTABL.h:451
void _solve_vector_with_guess_impl(const Rhs &b, Dest &x) const
Definition IDRSTABL.h:460
IDRSTABL()=default
Index maxIterations() const
Definition IterativeSolverBase.h:246
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34