39#ifndef EIGEN_IDRSTABL_H
40#define EIGEN_IDRSTABL_H
43#include "./InternalHeaderCheck.h"
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) {
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>;
60 const Index N = x.rows();
63 const Index maxIters = iters;
65 const RealScalar rhs_norm = rhs.stableNorm();
66 const RealScalar tol = tol_error * rhs_norm;
79 FullPivLU<DenseMatrixType> lu_solver;
81 if (S >= N || L >= N) {
86 lu_solver.compute(DenseMatrixType(mat));
87 x = lu_solver.solve(rhs);
89 tol_error = (rhs - mat * x).stableNorm() / rhs_norm;
94 DenseMatrixType u(N, L + 1);
95 DenseMatrixType r(N, L + 1);
97 DenseMatrixType V(N * (L + 1), S);
101 VectorType update(N);
108 r.col(0).noalias() = rhs - mat * x;
111 tol_error = r.col(0).stableNorm();
114 DenseMatrixType h_FOM = DenseMatrixType::Zero(S, S - 1);
117 DenseMatrixType U(N * (L + 1), S);
118 for (Index col_index = 0; col_index < S; ++col_index) {
123 if (col_index != 0) {
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;
134 h_FOM(col_index, col_index - 1) = u.col(0).stableNorm();
136 if (numext::abs(h_FOM(col_index, col_index - 1)) != RealScalar(0)) {
161 u.col(0) /= h_FOM(col_index, col_index - 1);
165 u.col(0).normalize();
168 U.col(col_index).head(N) = u.col(0);
173 Scalar beta = r.col(0).stableNorm();
174 VectorType e1 = VectorType::Zero(S - 1);
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;
182 RealScalar FOM_residual = (h_FOM(S - 1, S - 2) * y(S - 2) * U.col(S - 1).head(N)).stableNorm();
184 if (FOM_residual < tol) {
188 x = precond.solve(x2);
191 tol_error = FOM_residual / rhs_norm;
208 DenseMatrixType R_T = internal::random_orthonormal_basis<DenseMatrixType>(N, S).adjoint();
209 DenseMatrixType AR_T = DenseMatrixType(R_T * mat);
212 DenseMatrixType sigma(S, S);
214 bool reset_while =
false;
216 while (k < maxIters) {
217 for (Index j = 1; j <= L; ++j) {
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));
226 lu_solver.compute(sigma);
230 alpha = lu_solver.solve(R_T * r.col(0));
233 alpha = lu_solver.solve(AR_T * precond.solve(r.col(j - 2)));
237 update.noalias() = U.topRows(N) * alpha;
238 r.col(0).noalias() -= mat * precond.solve(update);
241 for (Index i = 1; i <= j - 2; ++i) {
243 r.col(i).noalias() -= U.block(N * (i + 1), 0, N, S) * alpha;
247 r.col(j - 1).noalias() = mat * precond.solve(r.col(j - 2));
249 tol_error = r.col(0).stableNorm();
251 if (tol_error < tol) {
257 bool break_normalization =
false;
258 for (Index q = 1; q <= S; ++q) {
261 u.leftCols(j) = r.leftCols(j);
264 u.leftCols(j) = u.middleCols(1, j);
269 u.leftCols(j).reshaped() -= U.topRows(N * j) * lu_solver.solve(AR_T * precond.solve(u.col(j - 1)));
272 u.col(j).noalias() = mat * precond.solve(u.col(j - 1));
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));
291 Scalar normalization_constant = u.col(j).stableNorm();
294 if (normalization_constant == RealScalar(0.0)) {
295 break_normalization =
true;
298 u.leftCols(j + 1) /= normalization_constant;
301 V.col(q - 1).head(N * (j + 1)) = u.leftCols(j + 1).reshaped();
304 if (!break_normalization) {
305 U.topRows(N * (j + 1)) = V.topRows(N * (j + 1));
309 U.middleRows(N * j, N).setZero();
317 r.col(L).noalias() = mat * precond.solve(r.col(L - 1));
322 ColPivHouseholderQR<DenseMatrixType> qr_solver(r.rightCols(L));
323 gamma = qr_solver.solve(r.col(0));
326 update.noalias() = r.leftCols(L) * gamma;
328 r.col(0).noalias() -= mat * precond.solve(update);
332 tol_error = r.col(0).stableNorm();
334 if (tol_error < tol) {
347 for (Index i = 1; i <= L; ++i) {
348 U.topRows(N) -= U.block(N * i, 0, N, S) * gamma(i - 1);
357 x = precond.solve(x);
360 tol_error = tol_error / rhs_norm;
366template <
typename MatrixType_,
typename Preconditioner_ = DiagonalPreconditioner<
typename MatrixType_::Scalar>>
371template <
typename MatrixType_,
typename Preconditioner_>
372struct traits<IDRSTABL<MatrixType_, Preconditioner_>> {
373 using MatrixType = MatrixType_;
374 using Preconditioner = Preconditioner_;
418template <
typename MatrixType_,
typename Preconditioner_>
424 using Base::m_isInitialized;
425 using Base::m_iterations;
431 using MatrixType = MatrixType_;
432 using Scalar =
typename MatrixType::Scalar;
433 using RealScalar =
typename MatrixType::RealScalar;
434 using Preconditioner = Preconditioner_;
450 template <
typename MatrixDerived>
459 template <
typename Rhs,
typename Dest>
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);
471 eigen_assert(L >= 1 &&
"L needs to be positive");
477 eigen_assert(S >= 1 &&
"S needs to be positive");
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
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
Definition EigenBase.h:34