Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
MINRES.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 Giacomo Po <gpo@ucla.edu>
5// Copyright (C) 2011-2014 Gael Guennebaud <gael.guennebaud@inria.fr>
6// Copyright (C) 2018 David Hyde <dabh@stanford.edu>
7//
8// This Source Code Form is subject to the terms of the Mozilla
9// Public License v. 2.0. If a copy of the MPL was not distributed
10// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
11// SPDX-License-Identifier: MPL-2.0
12
13#ifndef EIGEN_MINRES_H
14#define EIGEN_MINRES_H
15
16// IWYU pragma: private
17#include "./InternalHeaderCheck.h"
18
19namespace Eigen {
20
21namespace internal {
22
32template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
33EIGEN_DONT_INLINE void minres(const MatrixType& mat, const Rhs& rhs, Dest& x, const Preconditioner& precond,
34 Index& iters, 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
39 // Check for zero rhs
40 const RealScalar rhsNorm(rhs.stableNorm());
41 if (rhsNorm == 0) {
42 x.setZero();
43 iters = 0;
44 tol_error = 0;
45 return;
46 }
47
48 // initialize
49 const Index maxIters(iters); // initialize maxIters to iters
50 const Index N(mat.cols()); // the size of the matrix
51 const RealScalar threshold(tol_error * rhsNorm); // convergence threshold (compared to residualNorm)
52
53 // Initialize preconditioned Lanczos
54 VectorType v_old(N); // will be initialized inside loop
55 VectorType v(VectorType::Zero(N)); // initialize v
56 VectorType v_new(rhs - mat * x); // initialize v_new
57 RealScalar residualNorm(v_new.stableNorm());
58 if (residualNorm == 0 || residualNorm < threshold) {
59 iters = 0;
60 tol_error = residualNorm / rhsNorm;
61 return;
62 }
63
64 // Keep the quadratic Lanczos terms representable for very small or large residuals.
65 const RealScalar residualScale = internal::iterative_solver_scaling_factor(residualNorm);
66 v_new /= residualScale;
67 VectorType w(N); // will be initialized inside loop
68 VectorType w_new(precond.solve(v_new)); // initialize w_new
69 RealScalar beta_new2(v_new.dot(w_new));
70 eigen_assert(beta_new2 >= 0.0 && "PRECONDITIONER IS NOT POSITIVE DEFINITE");
71 RealScalar beta_new(numext::sqrt(beta_new2));
72 const RealScalar beta_one(beta_new);
73 // Initialize other variables
74 RealScalar c(1.0); // the cosine of the Givens rotation
75 RealScalar c_old(1.0);
76 RealScalar s(0.0); // the sine of the Givens rotation
77 RealScalar s_old(0.0); // the sine of the Givens rotation
78 VectorType p_oold(N); // will be initialized in loop
79 VectorType p_old(VectorType::Zero(N)); // initialize p_old=0
80 VectorType p(p_old); // initialize p=0
81 RealScalar eta(1.0);
82
83 iters = 0; // reset iters
84 while (iters < maxIters) {
85 // Preconditioned Lanczos
86 /* Note that there are 4 variants on the Lanczos algorithm. These are
87 * described in Paige, C. C. (1972). Computational variants of
88 * the Lanczos method for the eigenproblem. IMA Journal of Applied
89 * Mathematics, 10(3), 373-381. The current implementation corresponds
90 * to the case A(2,7) in the paper. It also corresponds to
91 * algorithm 6.14 in Y. Saad, Iterative Methods for Sparse Linear
92 * Systems, 2003 p.173. For the preconditioned version see
93 * A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM (1987).
94 */
95 const RealScalar beta(beta_new);
96 v_old = v; // update: at first time step, this makes v_old = 0 so value of beta doesn't matter
97 v_new /= beta_new; // overwrite v_new for next iteration
98 w_new /= beta_new; // overwrite w_new for next iteration
99 v = v_new; // update
100 w = w_new; // update
101 v_new.noalias() = mat * w - beta * v_old; // compute v_new
102 const RealScalar alpha = v_new.dot(w);
103 v_new -= alpha * v; // overwrite v_new
104 w_new = precond.solve(v_new); // overwrite w_new
105 beta_new2 = v_new.dot(w_new); // compute beta_new
106 eigen_assert(beta_new2 >= 0.0 && "PRECONDITIONER IS NOT POSITIVE DEFINITE");
107 beta_new = numext::sqrt(beta_new2); // compute beta_new
108
109 // Givens rotation
110 const RealScalar r2 = s * alpha + c * c_old * beta; // s, s_old, c and c_old are still from previous iteration
111 const RealScalar r3 = s_old * beta; // s, s_old, c and c_old are still from previous iteration
112 const RealScalar r1_hat = c * alpha - c_old * s * beta;
113 const RealScalar r1 = numext::hypot(r1_hat, beta_new);
114 c_old = c; // store for next iteration
115 s_old = s; // store for next iteration
116 c = r1_hat / r1; // new cosine
117 s = beta_new / r1; // new sine
118
119 // Update solution
120 p_oold = p_old;
121 p_old = p;
122 p = (w - r2 * p_old - r3 * p_oold) / r1;
123 x += (residualScale * beta_one * c * eta) * p;
124
125 /* Update the estimated residual norm. Note that this is the estimated
126 residual; the real residual |Ax-b| may be slightly larger. */
127 residualNorm *= numext::abs(s);
128
129 if (residualNorm < threshold) {
130 break;
131 }
132
133 eta = -s * eta; // update eta
134 iters++; // increment iteration number (for output purposes)
135 }
136
137 /* Compute error. Note that this is the estimated error. The real
138 error |Ax-b|/|b| may be slightly larger */
139 tol_error = residualNorm / rhsNorm;
140}
141
142} // namespace internal
143
144template <typename MatrixType_, int UpLo_ = Lower, typename Preconditioner_ = IdentityPreconditioner>
145class MINRES;
146
147namespace internal {
148
149template <typename MatrixType_, int UpLo_, typename Preconditioner_>
150struct traits<MINRES<MatrixType_, UpLo_, Preconditioner_> > {
151 using MatrixType = MatrixType_;
152 using Preconditioner = Preconditioner_;
153};
154
155} // namespace internal
156
195template <typename MatrixType_, int UpLo_, typename Preconditioner_>
196class MINRES : public IterativeSolverBase<MINRES<MatrixType_, UpLo_, Preconditioner_> > {
197 protected:
198 using Base = IterativeSolverBase<MINRES>;
199 using Base::m_error;
200 using Base::m_info;
201 using Base::m_isInitialized;
202 using Base::m_iterations;
203 using Base::matrix;
204
205 public:
206 using Base::_solve_impl;
207 using MatrixType = MatrixType_;
208 using Scalar = typename MatrixType::Scalar;
209 using RealScalar = typename MatrixType::RealScalar;
210 using Preconditioner = Preconditioner_;
211
212 enum { UpLo = UpLo_ };
213
214 public:
216 MINRES() : Base() {}
217
228 template <typename MatrixDerived>
229 explicit MINRES(const EigenBase<MatrixDerived>& A) : Base(A.derived()) {}
230
232 template <typename Rhs, typename Dest>
233 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
234 using MatrixWrapper = typename Base::MatrixWrapper;
235 using ActualMatrixType = typename Base::ActualMatrixType;
236 enum {
237 TransposeInput = (!MatrixWrapper::MatrixFree) && (UpLo == (Lower | Upper)) && (!MatrixType::IsRowMajor) &&
238 (!NumTraits<Scalar>::IsComplex)
239 };
240 using RowMajorWrapper =
241 std::conditional_t<TransposeInput, Transpose<const ActualMatrixType>, ActualMatrixType const&>;
242 EIGEN_STATIC_ASSERT(internal::check_implication(MatrixWrapper::MatrixFree, UpLo == (Lower | Upper)),
243 MATRIX_FREE_CONJUGATE_GRADIENT_IS_COMPATIBLE_WITH_UPPER_UNION_LOWER_MODE_ONLY);
244 using SelfAdjointWrapper =
245 std::conditional_t<UpLo == (Lower | Upper), RowMajorWrapper,
246 typename MatrixWrapper::template ConstSelfAdjointViewReturnType<UpLo>::Type>;
247
248 m_iterations = Base::maxIterations();
249 m_error = Base::m_tolerance;
250 RowMajorWrapper row_mat(matrix());
251 internal::minres(SelfAdjointWrapper(row_mat), b, x, Base::m_preconditioner, m_iterations, m_error);
252 m_info = m_error <= Base::m_tolerance ? Success : NoConvergence;
253 }
254
255 protected:
256};
257
258} // end namespace Eigen
259
260#endif // EIGEN_MINRES_H
Index maxIterations() const
Definition IterativeSolverBase.h:246
A minimal residual solver for sparse symmetric problems.
Definition MINRES.h:196
MINRES()
Definition MINRES.h:216
MINRES(const EigenBase< MatrixDerived > &A)
Definition MINRES.h:229
Expression of an array as a mathematical vector or matrix.
Definition ArrayWrapper.h:120
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34