30#ifndef EIGEN_BICGSTABL_H
31#define EIGEN_BICGSTABL_H
34#include "./InternalHeaderCheck.h"
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());
60 const RealScalar tol = tol_error;
61 const Index maxIters = iters;
63 using VectorType = Matrix<Scalar, Dynamic, 1>;
64 using DenseMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
66 DenseMatrixType rHat(N, L + 1);
67 DenseMatrixType uHat(N, L + 1);
72 rHat.col(0).noalias() = rhs - mat * x0;
76 VectorType rShadow = VectorType::Random(N);
78 VectorType x_prime = x;
80 VectorType b_prime = rHat.col(0);
87 uHat.col(0).setZero();
89 bool bicg_convergence =
false;
91 const RealScalar normb = rhs.stableNorm();
92 if (normb == RealScalar(0)) {
98 RealScalar normr = rHat.col(0).stableNorm();
99 RealScalar Mx = normr;
100 RealScalar Mr = normr;
103 RealScalar normr_min = normr;
104 VectorType x_min = x_prime + x;
107 const RealScalar delta = 0.01;
109 bool compute_res =
false;
110 bool update_app =
false;
112 while (normr > tol * normb && k < maxIters) {
115 for (Index j = 0; j < L; ++j) {
116 const Scalar rho1 = rShadow.dot(rHat.col(j));
118 if (!(numext::isfinite)(rho1) || rho0 == RealScalar(0.0)) {
123 normr = (rhs - mat * (precond.solve(x) + x0)).stableNorm();
125 if (normr > normr_min || !(numext::isfinite)(normr)) {
130 tol_error = normr / normb;
133 x = precond.solve(x);
135 return (normr < tol * normb);
138 const Scalar beta = alpha * (rho1 / rho0);
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;
146 rHat.leftCols(j + 1) -= alpha * uHat.middleCols(1, j + 1);
147 rHat.col(j + 1).noalias() = mat * precond.solve(rHat.col(j));
149 x += alpha * uHat.col(0);
150 normr = rHat.col(0).stableNorm();
152 if (normr < tol * normb) {
159 bicg_convergence =
true;
161 }
else if (normr < normr_min) {
167 if (!bicg_convergence) {
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);
183 if (normr < normr_min) {
203 Mx = numext::maxi(Mx, normr);
205 Mr = numext::maxi(Mr, normr);
207 if (normr < delta * normb && normb <= Mx) {
211 if (update_app || (normr < delta * Mr && normb <= Mr)) {
215 if (bicg_convergence) {
218 bicg_convergence =
false;
226 rHat.col(0).noalias() = b_prime - mat * precond.solve(x);
227 normr = rHat.col(0).stableNorm();
235 b_prime = rHat.col(0);
239 if (normr < normr_min) {
252 normr = (rhs - mat * (precond.solve(x) + x0)).stableNorm();
253 if (normr > normr_min || !(numext::isfinite)(normr)) {
258 tol_error = normr / normb;
262 x = precond.solve(x);
269template <
typename MatrixType_,
typename Preconditioner_ = DiagonalPreconditioner<
typename MatrixType_::Scalar>>
274template <
typename MatrixType_,
typename Preconditioner_>
275struct traits<Eigen::BiCGSTABL<MatrixType_, Preconditioner_>> {
276 using MatrixType = MatrixType_;
277 using Preconditioner = Preconditioner_;
282template <
typename MatrixType_,
typename Preconditioner_>
288 using Base::m_isInitialized;
289 using Base::m_iterations;
294 using MatrixType = MatrixType_;
295 using Scalar =
typename MatrixType::Scalar;
296 using RealScalar =
typename MatrixType::RealScalar;
297 using Preconditioner = Preconditioner_;
300 BiCGSTABL() =
default;
313 template <
typename MatrixDerived>
314 explicit BiCGSTABL(
const EigenBase<MatrixDerived> &A) : Base(A.derived()) {}
321 template <
typename Rhs,
typename Dest>
322 void _solve_vector_with_guess_impl(
const Rhs &b, Dest &x)
const {
324 m_iterations = max_iterations;
326 m_error = Base::m_tolerance;
328 bool ret = internal::bicgstabl(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, m_L);
329 Index total_iterations = m_iterations;
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;
339 m_iterations = total_iterations;
346 eigen_assert(L >= 1 &&
"L needs to be positive");
Base class for linear iterative solvers.
Definition IterativeSolverBase.h:118
IterativeSolverBase()
Definition IterativeSolverBase.h:136
Index maxIterations() const
Definition IterativeSolverBase.h:246
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461