Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
BiCGSTAB.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2011-2014 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_BICGSTAB_H
13#define EIGEN_BICGSTAB_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
32template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
33bool bicgstab(const MatrixType& mat, const Rhs& rhs, Dest& x, const Preconditioner& precond, Index& iters,
34 typename Dest::RealScalar& tol_error) {
35 using RealScalar = typename Dest::RealScalar;
36 using Scalar = typename Dest::Scalar;
37 using VectorType = Matrix<Scalar, Dynamic, 1>;
38 Index maxIters = iters;
39
40 Index n = mat.cols();
41 VectorType r = rhs - mat * x;
42 VectorType r0 = r;
43
44 RealScalar r0_norm = r0.stableNorm();
45 RealScalar r_norm = r0_norm;
46 RealScalar rhs_norm = rhs.stableNorm();
47 if (rhs_norm == 0) {
48 x.setZero();
49 iters = 0;
50 tol_error = 0;
51 return true;
52 }
53
54 RealScalar tol = tol_error * rhs_norm;
55
56 Scalar rho(1);
57 Scalar alpha(0);
58 Scalar w(1);
59
60 VectorType v = VectorType::Zero(n), p = VectorType::Zero(n);
61 VectorType y(n), z(n);
62
63 VectorType s(n), t(n);
64
65 RealScalar eps = NumTraits<Scalar>::epsilon();
66 Index i = 0;
67 Index restarts = 0;
68
69 while (r_norm > tol && i < maxIters) {
70 Scalar rho_old = rho;
71 rho = r0.dot(r);
72 if (Eigen::numext::abs(rho) / Eigen::numext::maxi(r0_norm, r_norm) < eps * Eigen::numext::mini(r0_norm, r_norm)) {
73 // The new residual vector became too orthogonal to the arbitrarily chosen direction r0
74 // Let's restart with a new r0:
75 r.noalias() = rhs - mat * x;
76 r0 = r;
77 rho = r.squaredNorm();
78 r0_norm = r.stableNorm();
79 alpha = Scalar(0);
80 w = Scalar(1);
81 if (restarts++ == 0) i = 0;
82 }
83 Scalar beta = (rho / rho_old) * (alpha / w);
84 p = r + beta * (p - w * v);
85
86 y = precond.solve(p);
87
88 v.noalias() = mat * y;
89 Scalar theta = r0.dot(v);
90 // For small angles ∠(r0, v) < eps, random restart.
91 RealScalar v_norm = v.stableNorm();
92 if (Eigen::numext::abs(theta) / Eigen::numext::maxi(r0_norm, v_norm) < eps * Eigen::numext::mini(r0_norm, v_norm)) {
93 r.noalias() = rhs - mat * x;
94 r0.setRandom();
95 r0_norm = r0.stableNorm();
96 rho = Scalar(1);
97 alpha = Scalar(0);
98 w = Scalar(1);
99 if (restarts++ == 0) i = 0;
100 continue;
101 }
102 alpha = rho / theta;
103 s = r - alpha * v;
104
105 z = precond.solve(s);
106 t.noalias() = mat * z;
107
108 RealScalar tmp = t.squaredNorm();
109 if (tmp > RealScalar(0)) {
110 w = t.dot(s) / tmp;
111 } else {
112 w = Scalar(0);
113 }
114 x += alpha * y + w * z;
115 r = s - w * t;
116 r_norm = r.stableNorm();
117 ++i;
118 }
119
120 tol_error = r_norm / rhs_norm;
121 iters = i;
122 return true;
123}
124
125} // namespace internal
126
127template <typename MatrixType_, typename Preconditioner_ = DiagonalPreconditioner<typename MatrixType_::Scalar> >
128class BiCGSTAB;
129
130namespace internal {
131
132template <typename MatrixType_, typename Preconditioner_>
133struct traits<BiCGSTAB<MatrixType_, Preconditioner_> > {
134 using MatrixType = MatrixType_;
135 using Preconditioner = Preconditioner_;
136};
137
138} // namespace internal
139
171template <typename MatrixType_, typename Preconditioner_>
172class BiCGSTAB : public IterativeSolverBase<BiCGSTAB<MatrixType_, Preconditioner_> > {
173 protected:
175 using Base::m_error;
176 using Base::m_info;
177 using Base::m_isInitialized;
178 using Base::m_iterations;
179 using Base::matrix;
180
181 public:
182 using MatrixType = MatrixType_;
183 using Scalar = typename MatrixType::Scalar;
184 using RealScalar = typename MatrixType::RealScalar;
185 using Preconditioner = Preconditioner_;
186
187 public:
189 BiCGSTAB() : Base() {}
190
201 template <typename MatrixDerived>
202 explicit BiCGSTAB(const EigenBase<MatrixDerived>& A) : Base(A.derived()) {}
203
205 template <typename Rhs, typename Dest>
206 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
207 m_iterations = Base::maxIterations();
208 m_error = Base::m_tolerance;
209
210 bool ret = internal::bicgstab(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error);
211
212 m_info = (!ret) ? NumericalIssue : m_error <= Base::m_tolerance ? Success : NoConvergence;
213 }
214};
215
216} // end namespace Eigen
217
218#endif // EIGEN_BICGSTAB_H
A bi conjugate gradient stabilized solver for sparse square problems.
Definition BiCGSTAB.h:172
BiCGSTAB(const EigenBase< MatrixDerived > &A)
Definition BiCGSTAB.h:202
BiCGSTAB()
Definition BiCGSTAB.h:189
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