Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
BiCGSTABL.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// Copyright (C) 2020 Adithya Vijaykumar
8//
9// This Source Code Form is subject to the terms of the Mozilla
10// Public License v. 2.0. If a copy of the MPL was not distributed
11// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
12// SPDX-License-Identifier: MPL-2.0
13
14/*
15
16 This implementation of BiCGStab(L) is based on the papers
17 General algorithm:
18 1. G.L.G. Sleijpen, D.R. Fokkema. (1993). BiCGstab(l) for linear equations
19 involving unsymmetric matrices with complex spectrum. Electronic Transactions
20 on Numerical Analysis. Polynomial step update:
21 2. G.L.G. Sleijpen, M.B. Van Gijzen. (2010) Exploiting BiCGstab(l)
22 strategies to induce dimension reduction SIAM Journal on Scientific Computing.
23 3. Fokkema, Diederik R. Enhanced implementation of BiCGstab (l) for
24 solving linear systems of equations. Universiteit Utrecht. Mathematisch
25 Instituut, 1996
26 4. Sleijpen, G. L., & van der Vorst, H. A. (1996). Reliable updated
27 residuals in hybrid Bi-CG methods. Computing, 56(2), 141-163.
28*/
29
30#ifndef EIGEN_BICGSTABL_H
31#define EIGEN_BICGSTABL_H
32
33// IWYU pragma: private
34#include "./InternalHeaderCheck.h"
35
36namespace Eigen {
37
38namespace internal {
50template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
51bool bicgstabl(const MatrixType &mat, const Rhs &rhs, Dest &x, const Preconditioner &precond, Index &iters,
52 typename Dest::RealScalar &tol_error, Index L) {
53 using RealScalar = typename Dest::RealScalar;
54 using Scalar = typename Dest::Scalar;
55 const Index N = rhs.size();
56 L = numext::mini(L, x.rows());
57
58 Index k = 0;
59
60 const RealScalar tol = tol_error;
61 const Index maxIters = iters;
62
63 using VectorType = Matrix<Scalar, Dynamic, 1>;
64 using DenseMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
65
66 DenseMatrixType rHat(N, L + 1);
67 DenseMatrixType uHat(N, L + 1);
68
69 // We start with an initial guess x_0 and let us set r_0 as (residual
70 // calculated from x_0)
71 VectorType x0 = x;
72 rHat.col(0).noalias() = rhs - mat * x0; // r_0
73
74 x.setZero(); // This will contain the updates to the solution.
75 // rShadow is arbitrary, but must never be orthogonal to any residual.
76 VectorType rShadow = VectorType::Random(N);
77
78 VectorType x_prime = x;
79
80 VectorType b_prime = rHat.col(0);
81
82 // Other vectors and scalars initialization
83 Scalar rho0 = 1.0;
84 Scalar alpha = 0.0;
85 Scalar omega = 1.0;
86
87 uHat.col(0).setZero();
88
89 bool bicg_convergence = false;
90
91 const RealScalar normb = rhs.stableNorm();
92 if (normb == RealScalar(0)) {
93 x.setZero();
94 iters = 0;
95 tol_error = 0;
96 return true;
97 }
98 RealScalar normr = rHat.col(0).stableNorm();
99 RealScalar Mx = normr;
100 RealScalar Mr = normr;
101
102 // Keep track of the solution with the lowest residual
103 RealScalar normr_min = normr;
104 VectorType x_min = x_prime + x;
105
106 // Criterion for when to apply the group-wise update, conform ref 3.
107 const RealScalar delta = 0.01;
108
109 bool compute_res = false;
110 bool update_app = false;
111
112 while (normr > tol * normb && k < maxIters) {
113 rho0 *= -omega;
114
115 for (Index j = 0; j < L; ++j) {
116 const Scalar rho1 = rShadow.dot(rHat.col(j));
117
118 if (!(numext::isfinite)(rho1) || rho0 == RealScalar(0.0)) {
119 // We cannot continue computing, return the best solution found.
120 x += x_prime;
121
122 // Check if x is better than the best stored solution thus far.
123 normr = (rhs - mat * (precond.solve(x) + x0)).stableNorm();
124
125 if (normr > normr_min || !(numext::isfinite)(normr)) {
126 // x_min is a better solution than x, return x_min
127 x = x_min;
128 normr = normr_min;
129 }
130 tol_error = normr / normb;
131 iters = k;
132 // x contains the updates to x0, add those back to obtain the solution
133 x = precond.solve(x);
134 x += x0;
135 return (normr < tol * normb);
136 }
137
138 const Scalar beta = alpha * (rho1 / rho0);
139 rho0 = rho1;
140 // Update search directions
141 uHat.leftCols(j + 1) = rHat.leftCols(j + 1) - beta * uHat.leftCols(j + 1);
142 uHat.col(j + 1).noalias() = mat * precond.solve(uHat.col(j));
143 const Scalar sigma = rShadow.dot(uHat.col(j + 1));
144 alpha = rho1 / sigma;
145 // Update residuals
146 rHat.leftCols(j + 1) -= alpha * uHat.middleCols(1, j + 1);
147 rHat.col(j + 1).noalias() = mat * precond.solve(rHat.col(j));
148 // Complete BiCG iteration by updating x
149 x += alpha * uHat.col(0);
150 normr = rHat.col(0).stableNorm();
151 // Check for early exit
152 if (normr < tol * normb) {
153 /*
154 Convergence was achieved during BiCG step.
155 Without this check BiCGStab(L) fails for trivial matrices, such as
156 when the preconditioner already is the inverse, or the input matrix is
157 identity.
158 */
159 bicg_convergence = true;
160 break;
161 } else if (normr < normr_min) {
162 // We found an x with lower residual, keep this one.
163 x_min = x + x_prime;
164 normr_min = normr;
165 }
166 }
167 if (!bicg_convergence) {
168 /*
169 The polynomial/minimize residual step.
170
171 QR Householder method for argmin is more stable than (modified)
172 Gram-Schmidt, in the sense that there is less loss of orthogonality. It
173 is more accurate than solving the normal equations, since the normal
174 equations scale with condition number squared.
175 */
176 const VectorType gamma = rHat.rightCols(L).householderQr().solve(rHat.col(0));
177 x.noalias() += rHat.leftCols(L) * gamma;
178 rHat.col(0).noalias() -= rHat.rightCols(L) * gamma;
179 uHat.col(0).noalias() -= uHat.rightCols(L) * gamma;
180 normr = rHat.col(0).stableNorm();
181 omega = gamma(L - 1);
182 }
183 if (normr < normr_min) {
184 // We found an x with lower residual, keep this one.
185 x_min = x + x_prime;
186 normr_min = normr;
187 }
188
189 k++;
190
191 /*
192 Reliable update part
193
194 The recursively computed residual can deviate from the actual residual
195 after several iterations. However, computing the residual from the
196 definition costs extra MVs and should not be done at each iteration. The
197 reliable update strategy computes the true residual from the definition:
198 r=b-A*x at strategic intervals. Furthermore a "group wise update" strategy
199 is used to combine updates, which improves accuracy.
200 */
201
202 // Maximum norm of residuals since last update of x.
203 Mx = numext::maxi(Mx, normr);
204 // Maximum norm of residuals since last computation of the true residual.
205 Mr = numext::maxi(Mr, normr);
206
207 if (normr < delta * normb && normb <= Mx) {
208 update_app = true;
209 }
210
211 if (update_app || (normr < delta * Mr && normb <= Mr)) {
212 compute_res = true;
213 }
214
215 if (bicg_convergence) {
216 update_app = true;
217 compute_res = true;
218 bicg_convergence = false;
219 }
220
221 if (compute_res) {
222 // Explicitly compute residual from the definition
223
224 // This is equivalent to the shifted version of rhs - mat *
225 // (precond.solve(x)+x0)
226 rHat.col(0).noalias() = b_prime - mat * precond.solve(x);
227 normr = rHat.col(0).stableNorm();
228 Mr = normr;
229
230 if (update_app) {
231 // After the group wise update, the original problem is translated to a
232 // shifted one.
233 x_prime += x;
234 x.setZero();
235 b_prime = rHat.col(0);
236 Mx = normr;
237 }
238 }
239 if (normr < normr_min) {
240 // We found an x with lower residual, keep this one.
241 x_min = x + x_prime;
242 normr_min = normr;
243 }
244
245 compute_res = false;
246 update_app = false;
247 }
248
249 // Convert internal variable to the true solution vector x
250 x += x_prime;
251
252 normr = (rhs - mat * (precond.solve(x) + x0)).stableNorm();
253 if (normr > normr_min || !(numext::isfinite)(normr)) {
254 // x_min is a better solution than x, return x_min
255 x = x_min;
256 normr = normr_min;
257 }
258 tol_error = normr / normb;
259 iters = k;
260
261 // x contains the updates to x0, add those back to obtain the solution
262 x = precond.solve(x);
263 x += x0;
264 return true;
265}
266
267} // namespace internal
268
269template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar>>
270class BiCGSTABL;
271
272namespace internal {
273
274template <typename MatrixType_, typename Preconditioner_>
275struct traits<Eigen::BiCGSTABL<MatrixType_, Preconditioner_>> {
276 using MatrixType = MatrixType_;
277 using Preconditioner = Preconditioner_;
278};
279
280} // namespace internal
281
282template <typename MatrixType_, typename Preconditioner_>
283class BiCGSTABL : public IterativeSolverBase<BiCGSTABL<MatrixType_, Preconditioner_>> {
284 protected:
286 using Base::m_error;
287 using Base::m_info;
288 using Base::m_isInitialized;
289 using Base::m_iterations;
290 using Base::matrix;
291 Index m_L = 2;
292
293 public:
294 using MatrixType = MatrixType_;
295 using Scalar = typename MatrixType::Scalar;
296 using RealScalar = typename MatrixType::RealScalar;
297 using Preconditioner = Preconditioner_;
298
300 BiCGSTABL() = default;
301
313 template <typename MatrixDerived>
314 explicit BiCGSTABL(const EigenBase<MatrixDerived> &A) : Base(A.derived()) {}
315
321 template <typename Rhs, typename Dest>
322 void _solve_vector_with_guess_impl(const Rhs &b, Dest &x) const {
323 const Index max_iterations = Base::maxIterations();
324 m_iterations = max_iterations;
325
326 m_error = Base::m_tolerance;
327
328 bool ret = internal::bicgstabl(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, m_L);
329 Index total_iterations = m_iterations;
330 // The recursively updated residual may stop just above the requested tolerance.
331 // Restart from the current best iterate while there is still iteration budget.
332 while (ret && m_error > Base::m_tolerance && total_iterations < max_iterations) {
333 Index restart_iterations = max_iterations - total_iterations;
334 m_error = Base::m_tolerance;
335 ret = internal::bicgstabl(matrix(), b, x, Base::m_preconditioner, restart_iterations, m_error, m_L);
336 if (restart_iterations == 0) break;
337 total_iterations += restart_iterations;
338 }
339 m_iterations = total_iterations;
340 m_info = (!ret) ? NumericalIssue : m_error <= Base::m_tolerance ? Success : NoConvergence;
341 }
342
345 void setL(Index L) {
346 eigen_assert(L >= 1 && "L needs to be positive");
347 m_L = L;
348 }
349};
350
351} // namespace Eigen
352
353#endif /* EIGEN_BICGSTABL_H */
Base class for linear iterative solvers.
Definition IterativeSolverBase.h:118
Index maxIterations() const
Definition IterativeSolverBase.h:246
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461