blob: 8995fe8b12ac1861263a1c3b80b71844d65037ea [file] [edit]
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2012 Giacomo Po <gpo@ucla.edu>
// Copyright (C) 2011 Gael Guennebaud <g.gael@free.fr>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
// SPDX-License-Identifier: MPL-2.0
#include <cmath>
#include "sparse_solver.h"
#include <Eigen/IterativeLinearSolvers>
template <typename T>
void test_minres_T() {
// Identity preconditioner
MINRES<SparseMatrix<T>, Lower, IdentityPreconditioner> minres_colmajor_lower_I;
MINRES<SparseMatrix<T>, Upper, IdentityPreconditioner> minres_colmajor_upper_I;
// Diagonal preconditioner
MINRES<SparseMatrix<T>, Lower, DiagonalPreconditioner<T> > minres_colmajor_lower_diag;
MINRES<SparseMatrix<T>, Upper, DiagonalPreconditioner<T> > minres_colmajor_upper_diag;
MINRES<SparseMatrix<T>, Lower | Upper, DiagonalPreconditioner<T> > minres_colmajor_uplo_diag;
// call tests for SPD matrix
CALL_SUBTEST(check_sparse_spd_solving(minres_colmajor_lower_I));
CALL_SUBTEST(check_sparse_spd_solving(minres_colmajor_upper_I));
CALL_SUBTEST(check_sparse_spd_solving(minres_colmajor_lower_diag));
CALL_SUBTEST(check_sparse_spd_solving(minres_colmajor_upper_diag));
CALL_SUBTEST(check_sparse_spd_solving(minres_colmajor_uplo_diag));
CALL_SUBTEST(check_sparse_zero_tolerance(minres_colmajor_uplo_diag));
CALL_SUBTEST(check_sparse_zero_tolerance(minres_colmajor_lower_I));
CALL_SUBTEST(check_sparse_default_tolerance(minres_colmajor_uplo_diag));
// TO DO: symmetric semi-definite matrix
// TO DO: symmetric indefinite matrix
}
void test_minres_extreme_rhs() {
const Matrix2d mat = Matrix2d::Identity();
const Vector2d direction = (Vector2d() << 1, -1).finished();
MINRES<Matrix2d, Lower | Upper, IdentityPreconditioner> solver(mat);
solver.setTolerance(1e-12);
for (double scale : {1e-200, 1e200}) {
const Vector2d rhs = scale * direction;
const Vector2d guess = 0.5 * rhs;
Vector2d x = solver.solve(rhs);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY(x.allFinite());
VERIFY_IS_APPROX(x / scale, direction);
x = solver.solveWithGuess(rhs, guess);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY(x.allFinite());
VERIFY_IS_APPROX(x / scale, direction);
}
}
// With a preconditioner M, MINRES minimizes the M^{-1}-norm of the residual, and the product of its Givens sines
// reduces that norm, not the 2-norm that error() documents. MINRES used to scale the initial 2-norm by that product, so
// on a symmetrically scaled system with a diagonal preconditioner it reported Success and an error() of 3e-9 for a
// tolerance of 1e-8 while |b - A x| / |b| was 2e-6. Success now implies that b - A x meets the tolerance, and error()
// is its norm.
template <typename = void>
void test_minres_true_residual() {
using SpMat = SparseMatrix<double>;
const Index n = 120;
const double eps = NumTraits<double>::epsilon();
const double tol = 1e-8;
for (double spread : {1e2, 1e4}) {
// D T D for the tridiagonal T = tridiag(-1, 4, -1) and a diagonal D with entries in [spread^-1/2, spread^1/2].
VectorXd d(n);
for (Index i = 0; i < n; ++i) d(i) = std::pow(spread, double((i * 7) % 9) / 8.0 - 0.5);
std::vector<Triplet<double>> triplets;
for (Index i = 0; i < n; ++i) {
triplets.emplace_back(i, i, d(i) * d(i) * 4);
if (i + 1 < n) {
triplets.emplace_back(i, i + 1, -d(i) * d(i + 1));
triplets.emplace_back(i + 1, i, -d(i) * d(i + 1));
}
}
SpMat A(n, n);
A.setFromTriplets(triplets.begin(), triplets.end());
const MatrixXd Aabs = A.toDense().cwiseAbs();
for (int trial = 0; trial < 5; ++trial) {
const VectorXd b = VectorXd::Random(n);
MINRES<SpMat, Lower | Upper, DiagonalPreconditioner<double>> solver;
solver.setTolerance(tol);
solver.setMaxIterations(2000);
solver.compute(A);
const VectorXd x = solver.solve(b);
VERIFY(x.allFinite());
VERIFY_LE(solver.iterations(), Index(2000));
const double res = (b - A * x).norm() / b.norm();
// Evaluating b - A x in another order can change each component by about eps (|b| + |A| |x|).
const double rounding = 10 * eps * (b.norm() + (Aabs * x.cwiseAbs()).norm()) / b.norm();
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY_LE(res, tol + rounding);
VERIFY_LE(numext::abs(solver.error() - res), res / 2 + rounding);
}
}
}
// The 5-point Laplacian on an m x m grid, for which the CG and MINRES iteration counts are about 4.5 m.
template <typename SpMat>
SpMat minres_poisson2d(Index m) {
std::vector<Triplet<double>> triplets;
for (Index i = 0; i < m; ++i) {
for (Index j = 0; j < m; ++j) {
const Index k = i * m + j;
triplets.emplace_back(k, k, 4.0);
if (j + 1 < m) triplets.emplace_back(k, k + 1, -1.0);
if (j > 0) triplets.emplace_back(k, k - 1, -1.0);
if (i + 1 < m) triplets.emplace_back(k, k + m, -1.0);
if (i > 0) triplets.emplace_back(k, k - m, -1.0);
}
}
SpMat A(m * m, m * m);
A.setFromTriplets(triplets.begin(), triplets.end());
return A;
}
// A tolerance of eps is below the rounding error of b - A x, which MINRES evaluates to confirm convergence. It used to
// keep iterating until maxIterations() = 2 n, 1800 iterations for m = 30 instead of the 136 that stop on the recurrence
// residual. It now stops when a failed confirmation comes 5 iterations after |b - A x| last halved. The residual of the
// computed x stagnates above eps (28 eps for m = 30), so with the default tolerance, eps, MINRES reports Success when
// the stagnated residual is at most 8 sqrt(n) eps, and with a tolerance set by the caller only when it meets it.
template <typename Preconditioner>
void test_minres_poisson() {
using SpMat = SparseMatrix<double>;
const double eps = NumTraits<double>::epsilon();
for (Index m : {25, 30}) {
const SpMat A = minres_poisson2d<SpMat>(m);
const Index n = A.rows();
const VectorXd b = VectorXd::Random(n);
MINRES<SpMat, Lower | Upper, Preconditioner> solver(A);
// The default tolerance is eps. The residual stagnates above it, and MINRES returns Success there as it is at most
// 8 sqrt(n) eps.
const double confirmable = 8 * numext::sqrt(double(n)) * eps;
VectorXd x = solver.solve(b);
VERIFY_IS_EQUAL(solver.tolerance(), eps);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY(solver.error() > eps);
VERIFY_LE(solver.iterations(), 5 * m + 10);
VERIFY_LE((b - A * x).norm(), 2 * confirmable * b.norm());
const Index defaultIterations = solver.iterations();
// A tolerance set by the caller is not relaxed, but 8 sqrt(n) eps can be confirmed after about 4.5 m iterations.
solver.setTolerance(confirmable);
x = solver.solve(b);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY_LE(solver.error(), confirmable);
VERIFY_LE(solver.iterations(), defaultIterations);
solver.setTolerance(eps);
x = solver.solve(b);
VERIFY(x.allFinite());
// A tolerance set by the caller is never relaxed to the confirmable bound: Success exactly when it is met.
VERIFY_IS_EQUAL(solver.info(), solver.error() <= eps ? Success : NoConvergence);
// The recurrence reaches eps after about 4.5 m iterations (136 for m = 30), and stagnation is detected within 5
// more iterations plus the spacing of the confirmations.
VERIFY_LE(solver.iterations(), 5 * m + 10);
VERIFY_LE(solver.iterations(), 2 * defaultIterations);
const double res = (b - A * x).norm() / b.norm();
VERIFY_LE(res, double(n) * eps);
VERIFY_LE(numext::abs(solver.error() - res), res / 2 + eps);
// A negative tolerance selects the default, see MINRES::tolerance().
solver.setTolerance(-1.0);
VERIFY_IS_EQUAL(solver.tolerance(), eps);
}
}
// The default tolerance is eps, so that a well-conditioned system is solved to the accuracy of the arithmetic: for
// tridiag(-1, 4, -1) and x = 1 in float, a default of 8 sqrt(n) eps stopped at a forward error of 4e-5 for n = 10000,
// and eps gives 2e-7.
template <typename = void>
void test_minres_default_accuracy() {
using SpMat = SparseMatrix<float>;
const float eps = NumTraits<float>::epsilon();
for (Index n : {40, 10000}) {
std::vector<Triplet<float>> triplets;
for (Index i = 0; i < n; ++i) {
triplets.emplace_back(i, i, 4.0f);
if (i + 1 < n) {
triplets.emplace_back(i, i + 1, -1.0f);
triplets.emplace_back(i + 1, i, -1.0f);
}
}
SpMat A(n, n);
A.setFromTriplets(triplets.begin(), triplets.end());
const VectorXf ones = VectorXf::Ones(n);
const VectorXf b = A * ones;
MINRES<SpMat, Lower | Upper, IdentityPreconditioner> solver(A);
VERIFY_IS_EQUAL(solver.tolerance(), eps);
const VectorXf x = solver.solve(b);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY_LE((x - ones).norm() / ones.norm(), 10 * eps);
}
}
// See check_sparse_small_rhs: the solvers returned NoConvergence or an inaccurate x for small |b|.
template <typename = void>
void test_minres_small_rhs() {
MINRES<SparseMatrix<double>, Lower | Upper, DiagonalPreconditioner<double>> solver_double;
MINRES<SparseMatrix<float>, Lower | Upper, DiagonalPreconditioner<float>> solver_float;
check_sparse_small_rhs(solver_double);
check_sparse_small_rhs(solver_float);
}
EIGEN_DECLARE_TEST(minres) {
CALL_SUBTEST_1(test_minres_T<double>());
CALL_SUBTEST_3(test_minres_extreme_rhs());
CALL_SUBTEST_4(test_minres_true_residual<>());
CALL_SUBTEST_4(test_minres_poisson<IdentityPreconditioner>());
CALL_SUBTEST_4(test_minres_poisson<DiagonalPreconditioner<double>>());
CALL_SUBTEST_4(test_minres_small_rhs<>());
CALL_SUBTEST_4(test_minres_default_accuracy<>());
CALL_SUBTEST_4((check_matrix_free_accessors<MINRES<MatrixFreeOperator, Lower | Upper, IdentityPreconditioner>>()));
}