17#include "./InternalHeaderCheck.h"
36template <
typename Vector,
typename RealScalar>
37typename Vector::Scalar omega(
const Vector& t,
const Vector& s, RealScalar angle) {
38 using Scalar =
typename Vector::Scalar;
39 const RealScalar ns = s.stableNorm();
40 const RealScalar nt = t.stableNorm();
41 const Scalar ts = t.dot(s);
42 const RealScalar rho = numext::abs(ts / (nt * ns));
45 if (ts == Scalar(0)) {
52 return angle * (ns / nt) * (ts / numext::abs(ts));
54 return ts / (nt * nt);
57template <
typename MatrixType,
typename Rhs,
typename Dest,
typename Preconditioner>
58bool idrs(
const MatrixType& A,
const Rhs& b, Dest& x,
const Preconditioner& precond, Index& iter,
59 typename Dest::RealScalar& relres, Index S,
bool smoothing,
typename Dest::RealScalar angle,
61 using RealScalar =
typename Dest::RealScalar;
62 using Scalar =
typename Dest::Scalar;
63 using VectorType = Matrix<Scalar, Dynamic, 1>;
64 using DenseMatrixType = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
65 const Index N = b.size();
66 S = numext::mini(S, x.rows());
67 const RealScalar tol = relres;
68 const Index maxit = iter;
72 FullPivLU<DenseMatrixType> lu_solver;
74 DenseMatrixType P = internal::random_orthonormal_basis<DenseMatrixType>(N, S);
76 const RealScalar normb = b.stableNorm();
78 if (normb == RealScalar(0)) {
95 const RealScalar mp = RealScalar(1e3) * NumTraits<Scalar>::epsilon();
98 const RealScalar tolb = tol * normb;
99 VectorType r = b - A * x;
108 RealScalar normr = r.stableNorm();
113 relres = normr / normb;
117 DenseMatrixType G = DenseMatrixType::Zero(N, S);
118 DenseMatrixType U = DenseMatrixType::Zero(N, S);
119 DenseMatrixType M = DenseMatrixType::Identity(S, S);
120 VectorType t(N), v(N);
123 const auto restart = [&]() {
134 const auto done = [&]() {
135 if (!(numext::isfinite)(normr)) {
144 r.noalias() = b - A * x;
145 normr = r.stableNorm();
160 while (!done() && iter < maxit) {
162 VectorType f = (r.adjoint() * P).adjoint();
164 for (Index k = 0; k < S; ++k) {
167 lu_solver.compute(M.block(k, k, S - k, S - k));
168 VectorType c = lu_solver.solve(f.segment(k, S - k));
170 v.noalias() = r - G.rightCols(S - k) * c;
172 v = precond.solve(v);
175 U.col(k) = U.rightCols(S - k) * c + om * v;
176 G.col(k).noalias() = A * U.col(k);
179 const RealScalar normg = G.col(k).stableNorm();
180 for (Index i = 0; i < k; ++i) {
182 Scalar alpha = P.col(i).dot(G.col(k)) / M(i, i);
183 G.col(k) = G.col(k) - alpha * G.col(i);
184 U.col(k) = U.col(k) - alpha * U.col(i);
187 if (k > 0 && G.col(k).stableNorm() <= mp * normg) {
197 M.block(k, k, S - k, 1) = (G.col(k).adjoint() * P.rightCols(S - k)).adjoint();
199 if (M(k, k) == Scalar(0)) {
204 Scalar beta = f(k) / M(k, k);
205 r = r - beta * G.col(k);
206 x = x + beta * U.col(k);
207 normr = r.stableNorm();
209 if (replacement && normr > tolb / mp) {
217 Scalar gamma = t.dot(r_s) / t.squaredNorm();
218 r_s = r_s - gamma * t;
219 x_s = x_s - gamma * (x_s - x);
220 normr = r_s.stableNorm();
223 if (normr < tolb || iter == maxit) {
229 f.segment(k + 1, S - (k + 1)) = f.segment(k + 1, S - (k + 1)) - beta * M.block(k + 1, k, S - (k + 1), 1);
241 v = precond.solve(v);
247 om = internal::omega(t, r, angle);
249 if (om == RealScalar(0.0)) {
255 normr = r.stableNorm();
257 if (replacement && normr > tolb / mp) {
262 if (trueres && normr < normb) {
263 r.noalias() = b - A * x;
270 Scalar gamma = t.dot(r_s) / t.squaredNorm();
271 r_s = r_s - gamma * t;
272 x_s = x_s - gamma * (x_s - x);
273 normr = r_s.stableNorm();
283 relres = normr / normb;
289template <
typename MatrixType_,
typename Preconditioner_ = DiagonalPreconditioner<
typename MatrixType_::Scalar> >
294template <
typename MatrixType_,
typename Preconditioner_>
295struct traits<Eigen::IDRS<MatrixType_, Preconditioner_> > {
296 using MatrixType = MatrixType_;
297 using Preconditioner = Preconditioner_;
344template <
typename MatrixType_,
typename Preconditioner_>
347 using MatrixType = MatrixType_;
348 using Scalar =
typename MatrixType::Scalar;
349 using RealScalar =
typename MatrixType::RealScalar;
350 using Preconditioner = Preconditioner_;
356 using Base::m_isInitialized;
357 using Base::m_iterations;
360 bool m_smoothing =
false;
361 RealScalar m_angle = RealScalar(0.7);
362 bool m_residual =
false;
366 IDRS() { Base::m_tolerance = RealScalar(-1); }
378 template <
typename MatrixDerived>
380 Base::m_tolerance = RealScalar(-1);
394 return Base::m_tolerance >= RealScalar(0)
396 : RealScalar(8) * numext::sqrt(RealScalar(Base::cols())) * NumTraits<RealScalar>::epsilon();
404 template <
typename Rhs,
typename Dest>
410 bool ret = internal::idrs(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, m_S, m_smoothing, m_angle,
443 void setAngle(RealScalar angle) { m_angle = angle; }
The Induced Dimension Reduction method (IDR(s)) is a short-recurrences Krylov method for sparse squar...
Definition IDRS.h:345
void setResidualUpdate(bool update)
Definition IDRS.h:448
IDRS()
Definition IDRS.h:366
RealScalar tolerance() const
Definition IDRS.h:393
IDRS(const EigenBase< MatrixDerived > &A)
Definition IDRS.h:379
void _solve_vector_with_guess_impl(const Rhs &b, Dest &x) const
Definition IDRS.h:405
void setSmoothing(bool smoothing)
Definition IDRS.h:431
void setS(Index S)
Definition IDRS.h:417
void setAngle(RealScalar angle)
Definition IDRS.h:443
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
Matrix< Type, Size, 1 > Vector
Size×1 vector of type Type.
Definition Matrix.h:532
Definition EigenBase.h:34