Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
LSMR.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9
10#ifndef EIGEN_LSMR_H
11#define EIGEN_LSMR_H
12
13// LSMR is an iterative algorithm for least-squares problems min ||A x - b||,
14// based on the Golub-Kahan bidiagonalization process. It is analytically
15// equivalent to applying MINRES to the normal equation A^T A x = A^T b, so the
16// quantity ||A^T r_k|| decreases monotonically (where r_k = b - A x_k). In
17// practice ||r_k|| also decreases monotonically, which makes LSMR safer than
18// LSQR to stop early. With a damping parameter lambda > 0 it instead minimizes
19// || (A; lambda I) x - (b; 0) ||, i.e. it solves the regularized (Tikhonov)
20// least-squares problem.
21//
22// This implementation follows the published algorithm:
23//
24// D. C.-L. Fong and M. A. Saunders, "LSMR: An Iterative Algorithm for Sparse
25// Least-Squares Problems", SIAM J. Sci. Comput. 33(5):2950-2971, 2011.
26// https://web.stanford.edu/group/SOL/software/lsmr/
27//
28// The scalar recurrences, the cheap estimates of ||r||, ||A^T r||, ||A|| and
29// cond(A), and the stopping rules reproduce the reference Fortran 90
30// implementation by the same authors (distributed under the BSD / Common Public
31// License at the URL above). No source code from that implementation is
32// reproduced here; only the mathematical algorithm is implemented, in Eigen's
33// own idiom.
34
35// IWYU pragma: private
36#include "./InternalHeaderCheck.h"
37
38namespace Eigen {
39
40namespace internal {
41
76template <typename MatrixType, typename Rhs, typename Dest, typename Preconditioner>
77EIGEN_DONT_INLINE Index lsmr(const MatrixType& mat, const Rhs& rhs, Dest& x, const Preconditioner& precond,
78 Index& iters, typename Dest::RealScalar& tol_error, const typename Dest::RealScalar& atol,
79 const typename Dest::RealScalar& btol, const typename Dest::RealScalar& lambda,
80 const typename Dest::RealScalar& conlim) {
81 using RealScalar = typename Dest::RealScalar;
82 using Scalar = typename Dest::Scalar;
83 using VectorType = Matrix<Scalar, Dynamic, 1>;
84
85 const RealScalar zero(0);
86 const RealScalar one(1);
87
88 const Index n = mat.cols();
89 const Index maxIters = iters;
90
91 // n-vectors needed before the early-return below. u is the only m-vector.
92 VectorType v(n), Atu(n);
93
94 // Set up the first vectors u and v for the bidiagonalization. These satisfy
95 // beta*u = b - A*x0 and alpha*v = M^{-1} A^T u.
96 VectorType u = rhs - mat * x; // working residual r0 of the initial guess
97 RealScalar alpha = zero;
98 RealScalar beta = u.stableNorm();
99 if (beta > zero) {
100 u /= beta;
101 Atu.noalias() = mat.adjoint() * u;
102 v = precond.solve(Atu);
103 alpha = v.stableNorm();
104 if (alpha > zero) v /= alpha;
105 }
106
107 iters = 0;
108 // If b - A*x0 = 0 or A^T(b - A*x0) = 0 then the current x already solves the
109 // (least-squares) problem: no correction is needed.
110 if (alpha * beta == zero) {
111 tol_error = zero;
112 return 0; // istop = 0
113 }
114
115 // dx accumulates the correction (in z-space when a preconditioner is used).
116 // The remaining n-vectors are only needed once we start iterating.
117 VectorType dx = VectorType::Zero(n);
118 VectorType h = v;
119 VectorType hbar = VectorType::Zero(n);
120 VectorType t(n);
121
122 // Quantities driving the two plane rotations.
123 RealScalar alphabar = alpha;
124 RealScalar zetabar = alpha * beta;
125 RealScalar rho = one;
126 RealScalar rhobar = one;
127 RealScalar cbar = one;
128 RealScalar sbar = zero;
129
130 // Quantities for the running estimate of ||r||.
131 RealScalar betadd = beta;
132 RealScalar betad = zero;
133 RealScalar rhodold = one;
134 RealScalar tautildeold = zero;
135 RealScalar thetatilde = zero;
136 RealScalar zeta = zero;
137 RealScalar d = zero;
138
139 // Quantities for the running estimates of ||A|| and cond(A).
140 RealScalar normA2 = alpha * alpha;
141 RealScalar maxrbar = zero;
142 RealScalar minrbar = NumTraits<RealScalar>::highest();
143
144 const RealScalar normb = beta;
145 const RealScalar ctol = conlim > zero ? one / conlim : zero;
146 RealScalar test2 = zero; // recomputed each iteration; also read after the loop for tol_error
147
148 Index istop = 0;
149 Index itn = 0;
150 while (istop == 0) {
151 ++itn;
152
153 // Perform the next step of the bidiagonalization to obtain the next
154 // beta, u, alpha, v. These satisfy
155 // beta*u = A*(M^{-1} v) - alpha*u,
156 // alpha*v = M^{-1} A^T u - beta*v.
157 t = precond.solve(v);
158 u *= -alpha;
159 u.noalias() += mat * t;
160 beta = u.stableNorm();
161 if (beta > zero) {
162 u /= beta;
163 Atu.noalias() = mat.adjoint() * u;
164 t = precond.solve(Atu);
165 v = t - beta * v;
166 alpha = v.stableNorm();
167 if (alpha > zero) v /= alpha;
168 }
169
170 // Construct rotation Qhat_{k} that folds in the damping.
171 const RealScalar alphahat = numext::hypot(alphabar, lambda);
172 const RealScalar chat = alphabar / alphahat;
173 const RealScalar shat = lambda / alphahat;
174
175 // Use a plane rotation Q_{k} to turn B_{k} into R_{k}.
176 const RealScalar rhoold = rho;
177 rho = numext::hypot(alphahat, beta);
178 const RealScalar c = alphahat / rho;
179 const RealScalar s = beta / rho;
180 const RealScalar thetanew = s * alpha;
181 alphabar = c * alpha;
182
183 // Use a plane rotation Qbar_{k} to turn R_{k}^T into Rbar_{k}.
184 const RealScalar rhobarold = rhobar;
185 const RealScalar zetaold = zeta;
186 const RealScalar thetabar = sbar * rho;
187 const RealScalar rhotemp = cbar * rho;
188 rhobar = numext::hypot(cbar * rho, thetanew);
189 cbar = cbar * rho / rhobar;
190 sbar = thetanew / rhobar;
191 zeta = cbar * zetabar;
192 zetabar = -sbar * zetabar;
193
194 // Update h, hbar and the (correction) solution dx.
195 hbar = h - (thetabar * rho / (rhoold * rhobarold)) * hbar;
196 dx += (zeta / (rho * rhobar)) * hbar;
197 h = v - (thetanew / rho) * h;
198
199 // Estimate ||r||. Apply rotation Qhat_{k}, then Q_{k}, then Qtilde_{k-1}.
200 const RealScalar betaacute = chat * betadd;
201 const RealScalar betacheck = -shat * betadd;
202 const RealScalar betahat = c * betaacute;
203 betadd = -s * betaacute;
204
205 const RealScalar thetatildeold = thetatilde;
206 const RealScalar rhotildeold = numext::hypot(rhodold, thetabar);
207 const RealScalar ctildeold = rhodold / rhotildeold;
208 const RealScalar stildeold = thetabar / rhotildeold;
209 thetatilde = stildeold * rhobar;
210 rhodold = ctildeold * rhobar;
211 betad = -stildeold * betad + ctildeold * betahat;
212
213 tautildeold = (zetaold - thetatildeold * tautildeold) / rhotildeold;
214 const RealScalar taud = (zeta - thetatilde * tautildeold) / rhodold;
215 d += betacheck * betacheck;
216 const RealScalar normr = numext::sqrt<RealScalar>(d + numext::abs2(betad - taud) + numext::abs2(betadd));
217
218 // Estimate ||A||.
219 normA2 += beta * beta;
220 const RealScalar normA = numext::sqrt(normA2);
221 normA2 += alpha * alpha;
222
223 // Estimate cond(A).
224 maxrbar = numext::maxi(maxrbar, rhobarold);
225 if (itn > 1) minrbar = numext::mini(minrbar, rhobarold);
226 const RealScalar condA = numext::maxi(maxrbar, rhotemp) / numext::mini(minrbar, rhotemp);
227
228 // Compute the norms needed for the stopping rules.
229 const RealScalar normAr = numext::abs(zetabar);
230 const RealScalar normx = dx.stableNorm();
231
232 const RealScalar test1 = normr / normb;
233 test2 = (normA * normr > zero) ? normAr / (normA * normr) : zero;
234 const RealScalar test3 = one / condA;
235 const RealScalar t1 = test1 / (one + normA * normx / normb);
236 const RealScalar rtol = btol + atol * normA * normx / normb;
237
238 // The "1 + test <= 1" guards trigger near machine precision and make the
239 // method behave as if atol = btol = eps and conlim = 1/eps even when the
240 // user passed 0 for any of them. The user tolerances are tested first so a
241 // genuine convergence (istop 1/2/3) takes priority over the machine limits.
242 // (istop 4 uses t1 rather than test1, matching the reference algorithm.)
243 if (test1 <= rtol)
244 istop = 1;
245 else if (test2 <= atol)
246 istop = 2;
247 else if (test3 <= ctol)
248 istop = 3;
249 else if (one + t1 <= one)
250 istop = 4;
251 else if (one + test2 <= one)
252 istop = 5;
253 else if (one + test3 <= one)
254 istop = 6;
255 else if (itn >= maxIters)
256 istop = 7;
257 }
258
259 // Recover the solution: x <- x0 + M^{-1} dx.
260 t = precond.solve(dx);
261 x += t;
262
263 iters = itn;
264 tol_error = test2;
265 return istop;
266}
267
268} // namespace internal
269
270template <typename MatrixType_, typename Preconditioner_ = IdentityPreconditioner>
271class LSMR;
272
273namespace internal {
274
275template <typename MatrixType_, typename Preconditioner_>
276struct traits<LSMR<MatrixType_, Preconditioner_> > {
277 using MatrixType = MatrixType_;
278 using Preconditioner = Preconditioner_;
279};
280
281} // namespace internal
282
351template <typename MatrixType_, typename Preconditioner_>
352class LSMR : public IterativeSolverBase<LSMR<MatrixType_, Preconditioner_> > {
353 protected:
354 using Base = IterativeSolverBase<LSMR>;
355 using Base::m_error;
356 using Base::m_info;
357 using Base::m_isInitialized;
358 using Base::m_iterations;
359 using Base::matrix;
360
361 public:
362 using MatrixType = MatrixType_;
363 using Scalar = typename MatrixType::Scalar;
364 using RealScalar = typename MatrixType::RealScalar;
365 using Preconditioner = Preconditioner_;
366
368 LSMR() : Base() {}
369
380 template <typename MatrixDerived>
381 explicit LSMR(const EigenBase<MatrixDerived>& A) : Base(A.derived()) {}
382
392 LSMR& setDamping(const RealScalar& lambda) {
393 m_lambda = lambda;
394 return *this;
395 }
396
398 RealScalar damping() const { return m_lambda; }
399
404 LSMR& setConditionLimit(const RealScalar& conlim) {
405 m_conditionLimit = conlim;
406 return *this;
407 }
408
410 RealScalar conditionLimit() const { return m_conditionLimit; }
411
416 LSMR& setToleranceA(const RealScalar& atol) {
417 m_atol = atol;
418 return *this;
419 }
420
423 RealScalar toleranceA() const { return m_atol >= RealScalar(0) ? m_atol : Base::m_tolerance; }
424
429 LSMR& setToleranceB(const RealScalar& btol) {
430 m_btol = btol;
431 return *this;
432 }
433
436 RealScalar toleranceB() const { return m_btol >= RealScalar(0) ? m_btol : Base::m_tolerance; }
437
439 template <typename Rhs, typename Dest>
440 void _solve_vector_with_guess_impl(const Rhs& b, Dest& x) const {
441 m_iterations = Base::maxIterations();
442
443 Index istop = internal::lsmr(matrix(), b, x, Base::m_preconditioner, m_iterations, m_error, toleranceA(),
444 toleranceB(), m_lambda, m_conditionLimit);
445 // istop in {0,1,2,4,5}: the (least-squares) solution was found, possibly
446 // only to within machine precision (4,5). istop in {3,6,7}: stopped on the
447 // condition-number limit or the iteration limit without meeting the
448 // requested tolerance.
449 m_info = (istop == 3 || istop == 6 || istop == 7) ? NoConvergence : Success;
450 }
451
452 protected:
453 RealScalar m_lambda = RealScalar(0);
454 RealScalar m_conditionLimit = RealScalar(0);
455 // Negative means "unset": toleranceA()/toleranceB() then fall back to tolerance().
456 RealScalar m_atol = RealScalar(-1);
457 RealScalar m_btol = RealScalar(-1);
458};
459
460} // end namespace Eigen
461
462#endif // EIGEN_LSMR_H
Index maxIterations() const
Definition IterativeSolverBase.h:246
An LSMR solver for sparse (or dense) least-squares problems.
Definition LSMR.h:352
LSMR(const EigenBase< MatrixDerived > &A)
Definition LSMR.h:381
LSMR()
Definition LSMR.h:368
LSMR & setConditionLimit(const RealScalar &conlim)
Definition LSMR.h:404
LSMR & setDamping(const RealScalar &lambda)
Definition LSMR.h:392
LSMR & setToleranceB(const RealScalar &btol)
Definition LSMR.h:429
RealScalar conditionLimit() const
Definition LSMR.h:410
RealScalar damping() const
Definition LSMR.h:398
RealScalar toleranceB() const
Definition LSMR.h:436
LSMR & setToleranceA(const RealScalar &atol)
Definition LSMR.h:416
RealScalar toleranceA() const
Definition LSMR.h:423
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34