Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
IterativeSolverBase.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2011-2014 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_ITERATIVE_SOLVER_BASE_H
12#define EIGEN_ITERATIVE_SOLVER_BASE_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21template <typename T>
22auto is_ref_compatible_test(T& matrix) -> decltype(Ref<const T>(matrix), std::true_type());
23std::false_type is_ref_compatible_test(...);
24
25template <typename MatrixType>
26using is_ref_compatible = decltype(is_ref_compatible_test(std::declval<remove_all_t<MatrixType>&>()));
27
28// Returns a \a rows x \a cols matrix whose columns are an orthonormal basis of a random subspace,
29// obtained by QR-orthonormalizing a random matrix. The IDR(s)-type solvers use this to build the
30// shadow space; the basis only has to be (almost surely) non-degenerate, so any random seed is fine.
31template <typename MatrixType>
32MatrixType random_orthonormal_basis(Index rows, Index cols) {
33 HouseholderQR<MatrixType> qr(MatrixType::Random(rows, cols));
34 return qr.householderQ() * MatrixType::Identity(rows, cols);
35}
36
37template <typename RealScalar>
38EIGEN_DEVICE_FUNC RealScalar iterative_solver_scaling_factor(RealScalar norm) {
39 // Scale only when forming a quadratic recurrence term from norm may underflow or overflow.
40 const RealScalar sqrtMin = numext::sqrt((std::numeric_limits<RealScalar>::min)());
41 const RealScalar sqrtMax = numext::sqrt((std::numeric_limits<RealScalar>::max)());
42 return norm < sqrtMin || norm > sqrtMax ? norm : RealScalar(1);
43}
44
45template <typename MatrixType, bool MatrixFree = !internal::is_ref_compatible<MatrixType>::value>
46class generic_matrix_wrapper;
47
48// We have an explicit matrix at hand, compatible with Ref<>
49template <typename MatrixType>
50class generic_matrix_wrapper<MatrixType, false> {
51 public:
52 using ActualMatrixType = Ref<const MatrixType>;
53 template <int UpLo>
54 struct ConstSelfAdjointViewReturnType {
55 using Type = typename ActualMatrixType::template ConstSelfAdjointViewReturnType<UpLo>::Type;
56 };
57
58 enum { MatrixFree = false };
59
60 // Default-construct: passing (0,0) trips the size assertion for fixed-size MatrixType (#1704).
61 generic_matrix_wrapper() : m_dummy(), m_matrix(m_dummy) {}
62
63 template <typename InputType>
64 generic_matrix_wrapper(const InputType& mat) : m_matrix(mat) {}
65
66 const ActualMatrixType& matrix() const { return m_matrix; }
67
68 template <typename MatrixDerived>
69 void grab(const EigenBase<MatrixDerived>& mat) {
70 internal::destroy_at(&m_matrix);
71 internal::construct_at(&m_matrix, mat.derived());
72 }
73
74 void grab(const Ref<const MatrixType>& mat) {
75 if (&(mat.derived()) != &m_matrix) {
76 internal::destroy_at(&m_matrix);
77 internal::construct_at(&m_matrix, mat);
78 }
79 }
80
81 protected:
82 MatrixType m_dummy; // used to default initialize the Ref<> object
83 ActualMatrixType m_matrix;
84};
85
86// MatrixType is not compatible with Ref<> -> matrix-free wrapper
87template <typename MatrixType>
88class generic_matrix_wrapper<MatrixType, true> {
89 public:
90 using ActualMatrixType = MatrixType;
91 template <int UpLo>
92 struct ConstSelfAdjointViewReturnType {
93 using Type = ActualMatrixType;
94 };
95
96 enum { MatrixFree = true };
97
98 generic_matrix_wrapper() = default;
99
100 generic_matrix_wrapper(const MatrixType& mat) : mp_matrix(&mat) {}
101
102 const ActualMatrixType& matrix() const { return *mp_matrix; }
103
104 void grab(const MatrixType& mat) { mp_matrix = &mat; }
105
106 protected:
107 const ActualMatrixType* mp_matrix = nullptr;
108};
109
110} // namespace internal
111
117template <typename Derived>
118class IterativeSolverBase : public SparseSolverBase<Derived> {
119 protected:
120 using Base = SparseSolverBase<Derived>;
121 using Base::m_isInitialized;
122
123 public:
124 using MatrixType = typename internal::traits<Derived>::MatrixType;
125 using Preconditioner = typename internal::traits<Derived>::Preconditioner;
126 using Scalar = typename MatrixType::Scalar;
127 using StorageIndex = typename MatrixType::StorageIndex;
128 using RealScalar = typename MatrixType::RealScalar;
129
130 enum { ColsAtCompileTime = MatrixType::ColsAtCompileTime, MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime };
131
132 public:
133 using Base::derived;
134
137
148 template <typename MatrixDerived>
149 explicit IterativeSolverBase(const EigenBase<MatrixDerived>& A) : m_matrixWrapper(A.derived()) {
150 init();
151 compute(matrix());
152 }
153
155
161 template <typename MatrixDerived>
163 grab(A.derived());
164 m_preconditioner.analyzePattern(matrix());
165 m_isInitialized = true;
166 m_analysisIsOk = true;
167 m_info = m_preconditioner.info();
168 return derived();
169 }
170
181 template <typename MatrixDerived>
183 eigen_assert(m_analysisIsOk && "You must first call analyzePattern()");
184 grab(A.derived());
185 m_preconditioner.factorize(matrix());
186 m_factorizationIsOk = true;
187 m_info = m_preconditioner.info();
188 return derived();
189 }
190
201 template <typename MatrixDerived>
203 grab(A.derived());
204 m_preconditioner.compute(matrix());
205 m_isInitialized = true;
206 m_analysisIsOk = true;
207 m_factorizationIsOk = true;
208 m_info = m_preconditioner.info();
209 return derived();
210 }
211
213 constexpr Index rows() const noexcept { return matrix().rows(); }
214
216 constexpr Index cols() const noexcept { return matrix().cols(); }
217
221 RealScalar tolerance() const { return m_tolerance; }
222
231 Derived& setTolerance(const RealScalar& tolerance) {
232 m_tolerance = tolerance;
233 return derived();
234 }
235
237 Preconditioner& preconditioner() { return m_preconditioner; }
238
240 const Preconditioner& preconditioner() const { return m_preconditioner; }
241
246 Index maxIterations() const { return (m_maxIterations < 0) ? 2 * matrix().cols() : m_maxIterations; }
247
251 Derived& setMaxIterations(Index maxIters) {
252 m_maxIterations = maxIters;
253 return derived();
254 }
255
257 Index iterations() const {
258 eigen_assert(m_isInitialized && "IterativeSolverBase is not initialized.");
259 return m_iterations;
260 }
261
267 RealScalar error() const {
268 eigen_assert(m_isInitialized && "IterativeSolverBase is not initialized.");
269 return m_error;
270 }
271
277 template <typename Rhs, typename Guess>
278 inline const SolveWithGuess<Derived, Rhs, Guess> solveWithGuess(const MatrixBase<Rhs>& b, const Guess& x0) const {
279 eigen_assert(m_isInitialized && "Solver is not initialized.");
280 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(derived(), b, false,
281 "solve(): invalid number of rows of the right hand side matrix b");
282 return SolveWithGuess<Derived, Rhs, Guess>(derived(), b.derived(), x0);
283 }
284
295 template <typename Rhs, typename Dest>
296 void solveWithGuessInPlace(const Rhs& b, Dest& x) const {
297 eigen_assert(m_isInitialized && "Solver is not initialized.");
298 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(derived(), b, false,
299 "solveWithGuessInPlace(): invalid number of rows of the right hand side b");
300 derived()._solve_vector_with_guess_impl(b, x);
301 }
302
305 eigen_assert(m_isInitialized && "IterativeSolverBase is not initialized.");
306 return m_info;
307 }
308
310 template <typename Rhs, typename DestDerived>
311 void _solve_with_guess_impl(const Rhs& b, SparseMatrixBase<DestDerived>& aDest) const {
312 EIGEN_INTERNAL_ASSERT_SOLVER_RHS(derived(), b, false);
313
314 Index rhsCols = b.cols();
315 Index size = b.rows();
316 DestDerived& dest(aDest.derived());
317 using DestScalar = typename DestDerived::Scalar;
320 // We do not directly fill dest because sparse expressions have to be free of aliasing issue.
321 // For non square least-square problems, b and dest might not have the same size whereas they might alias
322 // each-other.
323 typename DestDerived::PlainObject tmp(cols(), rhsCols);
324 ComputationInfo global_info = Success;
325 for (Index k = 0; k < rhsCols; ++k) {
326 tb = b.col(k);
327 tx = dest.col(k);
328 derived()._solve_vector_with_guess_impl(tb, tx);
329 tmp.col(k) = tx.sparseView(0);
330
331 // The call to _solve_vector_with_guess_impl updates m_info, so if it failed for a previous column
332 // we need to restore it to the worst value.
333 if (m_info == NumericalIssue)
334 global_info = NumericalIssue;
335 else if (m_info == NoConvergence)
336 global_info = NoConvergence;
337 }
338 m_info = global_info;
339 dest.swap(tmp);
340 }
341
342 template <typename Rhs, typename DestDerived>
343 std::enable_if_t<Rhs::ColsAtCompileTime != 1 && DestDerived::ColsAtCompileTime != 1> _solve_with_guess_impl(
344 const Rhs& b, MatrixBase<DestDerived>& aDest) const {
345 EIGEN_INTERNAL_ASSERT_SOLVER_RHS(derived(), b, false);
346
347 Index rhsCols = b.cols();
348 DestDerived& dest(aDest.derived());
349 ComputationInfo global_info = Success;
350 for (Index k = 0; k < rhsCols; ++k) {
351 typename DestDerived::ColXpr xk(dest, k);
352 typename Rhs::ConstColXpr bk(b, k);
353 derived()._solve_vector_with_guess_impl(bk, xk);
354
355 // The call to _solve_vector_with_guess_impl updates m_info, so if it failed for a previous column
356 // we need to restore it to the worst value.
357 if (m_info == NumericalIssue)
358 global_info = NumericalIssue;
359 else if (m_info == NoConvergence)
360 global_info = NoConvergence;
361 }
362 m_info = global_info;
363 }
364
365 template <typename Rhs, typename DestDerived>
366 std::enable_if_t<Rhs::ColsAtCompileTime == 1 || DestDerived::ColsAtCompileTime == 1> _solve_with_guess_impl(
367 const Rhs& b, MatrixBase<DestDerived>& dest) const {
368 derived()._solve_vector_with_guess_impl(b, dest.derived());
369 }
370
372 template <typename Rhs, typename Dest>
373 void _solve_impl(const Rhs& b, Dest& x) const {
374 x.setZero();
375 derived()._solve_with_guess_impl(b, x);
376 }
377
378 protected:
379 void init() {
380 m_isInitialized = false;
381 m_analysisIsOk = false;
382 m_factorizationIsOk = false;
383 m_maxIterations = -1;
384 m_tolerance = NumTraits<Scalar>::epsilon();
385 }
386
387 using MatrixWrapper = internal::generic_matrix_wrapper<MatrixType>;
388 using ActualMatrixType = typename MatrixWrapper::ActualMatrixType;
389
390 const ActualMatrixType& matrix() const { return m_matrixWrapper.matrix(); }
391
392 template <typename InputType>
393 void grab(const InputType& A) {
394 m_matrixWrapper.grab(A);
395 }
396
397 MatrixWrapper m_matrixWrapper;
398 Preconditioner m_preconditioner;
399
400 Index m_maxIterations;
401 RealScalar m_tolerance;
402
403 mutable RealScalar m_error;
404 mutable Index m_iterations;
405 mutable ComputationInfo m_info;
406 mutable bool m_analysisIsOk, m_factorizationIsOk;
407};
408
409} // end namespace Eigen
410
411#endif // EIGEN_ITERATIVE_SOLVER_BASE_H
Base class for linear iterative solvers.
Definition IterativeSolverBase.h:118
IterativeSolverBase()
Definition IterativeSolverBase.h:136
ComputationInfo info() const
Definition IterativeSolverBase.h:304
RealScalar error() const
Definition IterativeSolverBase.h:267
Index maxIterations() const
Definition IterativeSolverBase.h:246
Derived & setMaxIterations(Index maxIters)
Definition IterativeSolverBase.h:251
Derived & compute(const EigenBase< MatrixDerived > &A)
Definition IterativeSolverBase.h:202
IterativeSolverBase(const EigenBase< MatrixDerived > &A)
Definition IterativeSolverBase.h:149
void solveWithGuessInPlace(const Rhs &b, Dest &x) const
Definition IterativeSolverBase.h:296
const Preconditioner & preconditioner() const
Definition IterativeSolverBase.h:240
Derived & analyzePattern(const EigenBase< MatrixDerived > &A)
Definition IterativeSolverBase.h:162
Derived & factorize(const EigenBase< MatrixDerived > &A)
Definition IterativeSolverBase.h:182
Preconditioner & preconditioner()
Definition IterativeSolverBase.h:237
Derived & setTolerance(const RealScalar &tolerance)
Definition IterativeSolverBase.h:231
RealScalar tolerance() const
Definition IterativeSolverBase.h:221
const SolveWithGuess< Derived, Rhs, Guess > solveWithGuess(const MatrixBase< Rhs > &b, const Guess &x0) const
Definition IterativeSolverBase.h:278
Index iterations() const
Definition IterativeSolverBase.h:257
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Pseudo expression representing a solving operation.
Definition SolveWithGuess.h:44
Base class of any sparse matrices or sparse expressions.
Definition SparseMatrixBase.h:31
ComputationInfo
Definition Constants.h:455
@ NumericalIssue
Definition Constants.h:459
@ Success
Definition Constants.h:457
@ NoConvergence
Definition Constants.h:461
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50