blob: e34aaac7427d21425dac17269093a4bd381d4fd0 [file] [edit]
// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud@inria.fr>
// Copyright (C) 2010 Jitse Niesen <jitse@maths.leeds.ac.uk>
//
// 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 "main.h"
#include <limits>
#include <Eigen/Eigenvalues>
#include <Eigen/LU>
#include "CustomComplex.h"
template <typename MatrixType>
bool find_pivot(typename MatrixType::Scalar tol, MatrixType& diffs, Index col = 0) {
bool match = diffs.diagonal().sum() <= tol;
if (match || col == diffs.cols()) {
return match;
} else {
Index n = diffs.cols();
std::vector<std::pair<Index, Index> > transpositions;
for (Index i = col; i < n; ++i) {
Index best_index(0);
if (diffs.col(col).segment(col, n - i).minCoeff(&best_index) > tol) break;
best_index += col;
diffs.row(col).swap(diffs.row(best_index));
if (find_pivot(tol, diffs, col + 1)) return true;
diffs.row(col).swap(diffs.row(best_index));
// move current pivot to the end
diffs.row(n - (i - col) - 1).swap(diffs.row(best_index));
transpositions.push_back(std::pair<Index, Index>(n - (i - col) - 1, best_index));
}
// restore
for (Index k = transpositions.size() - 1; k >= 0; --k)
diffs.row(transpositions[k].first).swap(diffs.row(transpositions[k].second));
}
return false;
}
/* Check that two column vectors are approximately equal up to permutations.
* Initially, this method checked that the k-th power sums are equal for all k = 1, ..., vec1.rows(),
* however this strategy is numerically inaccurate because of numerical cancellation issues.
*/
template <typename VectorType>
void verify_is_approx_upto_permutation(const VectorType& vec1, const VectorType& vec2) {
using Scalar = typename VectorType::Scalar;
using RealScalar = typename NumTraits<Scalar>::Real;
VERIFY(vec1.cols() == 1);
VERIFY(vec2.cols() == 1);
VERIFY(vec1.rows() == vec2.rows());
Index n = vec1.rows();
RealScalar tol = test_precision<RealScalar>() * test_precision<RealScalar>() *
numext::maxi(vec1.squaredNorm(), vec2.squaredNorm());
Matrix<RealScalar, Dynamic, Dynamic> diffs =
(vec1.rowwise().replicate(n) - vec2.rowwise().replicate(n).transpose()).cwiseAbs2();
VERIFY(find_pivot(tol, diffs));
}
template <typename MatrixType>
void eigensolver(const MatrixType& m) {
/* this test covers the following files:
ComplexEigenSolver.h, and indirectly ComplexSchur.h
*/
Index rows = m.rows();
Index cols = m.cols();
using Scalar = typename MatrixType::Scalar;
using RealScalar = typename NumTraits<Scalar>::Real;
MatrixType a = MatrixType::Random(rows, cols);
MatrixType symmA = a.adjoint() * a;
ComplexEigenSolver<MatrixType> ei0(symmA);
VERIFY_IS_EQUAL(ei0.info(), Success);
VERIFY_IS_APPROX(symmA * ei0.eigenvectors(), ei0.eigenvectors() * ei0.eigenvalues().asDiagonal());
ComplexEigenSolver<MatrixType> ei1(a);
VERIFY_IS_EQUAL(ei1.info(), Success);
VERIFY_IS_APPROX(a * ei1.eigenvectors(), ei1.eigenvectors() * ei1.eigenvalues().asDiagonal());
// Note: If MatrixType is real then a.eigenvalues() uses EigenSolver and thus
// another algorithm so results may differ slightly
verify_is_approx_upto_permutation(a.eigenvalues(), ei1.eigenvalues());
ComplexEigenSolver<MatrixType> ei2;
ei2.setMaxIterations(ComplexSchur<MatrixType>::m_maxIterationsPerRow * rows).compute(a);
VERIFY_IS_EQUAL(ei2.info(), Success);
VERIFY_IS_EQUAL(ei2.eigenvectors(), ei1.eigenvectors());
VERIFY_IS_EQUAL(ei2.eigenvalues(), ei1.eigenvalues());
if (rows > 2) {
ei2.setMaxIterations(1).compute(a);
VERIFY_IS_EQUAL(ei2.info(), NoConvergence);
VERIFY_IS_EQUAL(ei2.getMaxIterations(), 1);
}
ComplexEigenSolver<MatrixType> eiNoEivecs(a, false);
VERIFY_IS_EQUAL(eiNoEivecs.info(), Success);
VERIFY_IS_APPROX(ei1.eigenvalues(), eiNoEivecs.eigenvalues());
// Regression test for issue #66
MatrixType z = MatrixType::Zero(rows, cols);
ComplexEigenSolver<MatrixType> eiz(z);
VERIFY((eiz.eigenvalues().cwiseEqual(0)).all());
MatrixType id = MatrixType::Identity(rows, cols);
VERIFY_IS_APPROX(id.operatorNorm(), RealScalar(1));
if (rows > 1 && rows < 20) {
// Test matrix with NaN
a(0, 0) = std::numeric_limits<typename MatrixType::RealScalar>::quiet_NaN();
ComplexEigenSolver<MatrixType> eiNaN(a);
VERIFY_IS_EQUAL(eiNaN.info(), NoConvergence);
}
// regression test for bug 1098
{
ComplexEigenSolver<MatrixType> eig(a.adjoint() * a);
eig.compute(a.adjoint() * a);
}
// regression test for bug 478
{
a.setZero();
ComplexEigenSolver<MatrixType> ei3(a);
VERIFY_IS_EQUAL(ei3.info(), Success);
RealScalar tol = 2 * a.cols() * NumTraits<RealScalar>::epsilon();
VERIFY((ei3.eigenvectors().adjoint() * ei3.eigenvectors()).eval().isIdentity(tol));
}
}
template <typename MatrixType>
void eigensolver_verify_assert(const MatrixType& m) {
ComplexEigenSolver<MatrixType> eig;
VERIFY_RAISES_ASSERT(eig.eigenvectors());
VERIFY_RAISES_ASSERT(eig.eigenvalues());
MatrixType a = MatrixType::Random(m.rows(), m.cols());
eig.compute(a, false);
VERIFY_RAISES_ASSERT(eig.eigenvectors());
}
void custom_complex_stable_normalization() {
using Scalar = CustomComplex<double>;
using Vector2 = Matrix<Scalar, 2, 1>;
Vector2 input;
input << Scalar(3.0, 4.0), Scalar(0.0, 0.0);
const Vector2 normalized = input.stableNormalized();
VERIFY_IS_APPROX(normalized(0).re, 0.6);
VERIFY_IS_APPROX(normalized(0).im, 0.8);
VERIFY_IS_EQUAL(normalized(1), Scalar(0.0, 0.0));
input.stableNormalize();
VERIFY_IS_APPROX(input(0).re, 0.6);
VERIFY_IS_APPROX(input(0).im, 0.8);
VERIFY_IS_EQUAL(input(1), Scalar(0.0, 0.0));
}
// A Jordan block has equal eigenvalues, so each back-substitution step divides by eps * |T| and the unit
// triangular factor X grows like eps^-k along the chain: it overflows for n >= 30 (double) and n >= 8 (float)
// unless the columns are rescaled. The eigenvectors are then not finite with info() == Success. The block is also
// multiplied by 2^exponent, so that |T|_F overflows (2^510 in double, 2^64 in float, for these sizes) or underflows
// (2^-1000, 2^-80) in the perturbation eps |T|_F that replaces the zero denominators.
template <typename Scalar>
void complex_eigensolver_jordan_block(int n, int exponent = 0) {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<std::complex<RealScalar>, Dynamic, Dynamic>;
const RealScalar eps = NumTraits<RealScalar>::epsilon();
const RealScalar scale = std::ldexp(RealScalar(1), exponent);
MatrixType unit = MatrixType::Identity(n, n);
unit.template diagonal<1>().setOnes();
const MatrixType A = unit * scale;
ComplexEigenSolver<MatrixType> eig(A);
VERIFY_IS_EQUAL(eig.info(), Success);
const MatrixType& V = eig.eigenvectors();
VERIFY(V.allFinite());
VERIFY(eig.eigenvalues().allFinite());
const MatrixType scaledEigenvalues = (eig.eigenvalues() / scale).matrix();
const RealScalar residual = (unit * V - V * scaledEigenvalues.col(0).asDiagonal()).cwiseAbs().maxCoeff() /
(unit.cwiseAbs().maxCoeff() * V.cwiseAbs().maxCoeff());
VERIFY(residual <= RealScalar(100 * n) * eps);
}
// The bound B = max / (4 n |T|_F) on the entries of X overflows in the denominator for |T|_F > max / (4 n), and |T|_F
// itself overflows for a finite T with |T|_F > max; neither may zero the columns of V. T = s (U + diag(1, ..., n)) with
// U the strictly upper triangular ones and s = 2^exponent.
template <typename RealScalar>
void complex_eigensolver_large_triangular(int n, int exponent) {
using MatrixType = Matrix<std::complex<RealScalar>, Dynamic, Dynamic>;
const RealScalar eps = NumTraits<RealScalar>::epsilon();
const RealScalar scale = std::ldexp(RealScalar(1), exponent);
MatrixType unit = MatrixType::Zero(n, n);
unit.template triangularView<StrictlyUpper>().setOnes();
for (Index i = 0; i < n; ++i) unit(i, i) = RealScalar(i + 1);
const MatrixType A = unit * scale;
VERIFY(A.allFinite());
ComplexEigenSolver<MatrixType> eig(A);
VERIFY_IS_EQUAL(eig.info(), Success);
const MatrixType& V = eig.eigenvectors();
VERIFY(V.allFinite());
for (Index k = 0; k < n; ++k) VERIFY(numext::abs(V.col(k).stableNorm() - RealScalar(1)) <= RealScalar(10 * n) * eps);
const MatrixType scaledEigenvalues = (eig.eigenvalues() / scale).matrix();
const RealScalar residual =
(unit * V - V * scaledEigenvalues.col(0).asDiagonal()).cwiseAbs().maxCoeff() / unit.cwiseAbs().maxCoeff();
VERIFY(residual <= RealScalar(100 * n) * eps);
}
// A fixed sequence of coefficients near highest() / 1024, so the products in the back substitution leave the range
// while the eigenvectors of T itself do not. The scaled problem is the reference: V must still solve a V = V D.
template <typename MatrixType>
void eigensolver_large_coefficients() {
using Scalar = typename MatrixType::Scalar;
using RealScalar = typename MatrixType::RealScalar;
const RealScalar highest = NumTraits<RealScalar>::highest();
const RealScalar eps = NumTraits<RealScalar>::epsilon();
unsigned state = 12345u + 7919u * 182u;
const auto next = [&state]() {
state = state * 1103515245u + 12345u;
return RealScalar(int((state >> 16) & 0x7fff) - 16384) / RealScalar(16384);
};
MatrixType a(8, 8);
for (Index i = 0; i < 8; ++i)
for (Index j = 0; j < 8; ++j) a(i, j) = Scalar(next(), next()) * (highest / RealScalar(1024));
a(3, 5) = Scalar(RealScalar(0.45) * highest, RealScalar(0.45) * highest);
ComplexEigenSolver<MatrixType> solver(a);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY(solver.eigenvalues().allFinite());
VERIFY(solver.eigenvectors().allFinite());
const MatrixType& V = solver.eigenvectors();
for (Index k = 0; k < a.cols(); ++k) {
const RealScalar norm = V.col(k).stableNorm();
VERIFY(norm > RealScalar(0.5) && norm < RealScalar(2));
}
const MatrixType b = a / highest;
const MatrixType residual = b * V - V * (solver.eigenvalues() / highest).asDiagonal();
VERIFY(residual.norm() <= RealScalar(1000 * a.cols()) * eps * b.norm());
}
// The eigenvalue difference is at rounding level while the coupling is near highest(), so the correction factor that
// keeps a column of X bounded underflows and has to be applied in two steps.
template <typename RealScalar>
void eigensolver_underflowing_correction(int n) {
using MatrixType = Matrix<std::complex<RealScalar>, Dynamic, Dynamic>;
using ComplexScalar = std::complex<RealScalar>;
const RealScalar highest = NumTraits<RealScalar>::highest();
const RealScalar eps = NumTraits<RealScalar>::epsilon();
MatrixType a = MatrixType::Zero(n, n);
for (Index i = 0; i < n; ++i) {
a(i, i) = ComplexScalar(RealScalar(1) + RealScalar(i) * RealScalar(2) * eps, RealScalar(0));
if (i + 1 < n) a(i, i + 1) = ComplexScalar(highest / RealScalar(4), RealScalar(0));
}
ComplexEigenSolver<MatrixType> solver(a);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY(solver.eigenvectors().allFinite());
VERIFY(solver.eigenvalues().allFinite());
for (Index k = 0; k < n; ++k) {
const RealScalar norm = solver.eigenvectors().col(k).stableNorm();
VERIFY(norm > RealScalar(0.5) && norm < RealScalar(2));
}
}
// A chain of rows with coefficients near highest() forces a component of the eigenvector of T above highest(). X is
// homogeneous of degree zero in T, so the eigenvectors must agree with those of the same matrix scaled down.
template <typename RealScalar>
void eigensolver_overflowing_eigenvector(int n) {
using MatrixType = Matrix<std::complex<RealScalar>, Dynamic, Dynamic>;
using ComplexScalar = std::complex<RealScalar>;
const RealScalar highest = NumTraits<RealScalar>::highest();
const RealScalar eps = NumTraits<RealScalar>::epsilon();
MatrixType a = MatrixType::Zero(n, n);
for (Index i = 0; i < n; ++i) {
a(i, i) = ComplexScalar(RealScalar(i) + RealScalar(1), RealScalar(0));
if (i + 1 < n) a(i, i + 1) = ComplexScalar(highest / RealScalar(4), highest / RealScalar(4));
}
ComplexEigenSolver<MatrixType> solver(a);
ComplexEigenSolver<MatrixType> reference(a / highest);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY_IS_EQUAL(reference.info(), Success);
VERIFY(solver.eigenvectors().allFinite());
VERIFY(solver.eigenvalues().allFinite());
for (Index k = 0; k < n; ++k) {
VERIFY_IS_APPROX(solver.eigenvectors().col(k).stableNorm(), RealScalar(1));
VERIFY((solver.eigenvectors().col(k) - reference.eigenvectors().col(k)).stableNorm() <= RealScalar(256 * n) * eps);
}
}
EIGEN_DECLARE_TEST(eigensolver_complex) {
int s = 0;
for (int i = 0; i < g_repeat; i++) {
CALL_SUBTEST_1(eigensolver(Matrix4cf()));
s = internal::random<int>(1, EIGEN_TEST_MAX_SIZE / 4);
CALL_SUBTEST_2(eigensolver(MatrixXcd(s, s)));
CALL_SUBTEST_3(eigensolver(Matrix<std::complex<float>, 1, 1>()));
CALL_SUBTEST_4(eigensolver(Matrix3f()));
TEST_SET_BUT_UNUSED_VARIABLE(s);
}
CALL_SUBTEST_1(eigensolver_verify_assert(Matrix4cf()));
s = internal::random<int>(1, EIGEN_TEST_MAX_SIZE / 4);
CALL_SUBTEST_2(eigensolver_verify_assert(MatrixXcd(s, s)));
CALL_SUBTEST_3(eigensolver_verify_assert(Matrix<std::complex<float>, 1, 1>()));
CALL_SUBTEST_4(eigensolver_verify_assert(Matrix3f()));
// Test problem size constructors
CALL_SUBTEST_5(ComplexEigenSolver<MatrixXf> tmp(s));
// ComplexSchur took the maximum of no coefficients for an empty matrix.
CALL_SUBTEST_2({
MatrixXcd A(0, 0);
ComplexEigenSolver<MatrixXcd> solver(A);
VERIFY_IS_EQUAL(solver.info(), Success);
VERIFY_IS_EQUAL(solver.eigenvectors().size(), 0);
VERIFY_IS_EQUAL(A.eigenvalues().size(), 0);
});
// Test custom complex scalar type.
CALL_SUBTEST_6(eigensolver(Matrix<CustomComplex<double>, 5, 5>()));
CALL_SUBTEST_6(custom_complex_stable_normalization());
CALL_SUBTEST_7(eigensolver_large_coefficients<MatrixXcd>());
CALL_SUBTEST_7(eigensolver_underflowing_correction<double>(2));
CALL_SUBTEST_7(eigensolver_underflowing_correction<double>(3));
CALL_SUBTEST_7(eigensolver_underflowing_correction<double>(4));
CALL_SUBTEST_7(eigensolver_underflowing_correction<float>(2));
CALL_SUBTEST_7(eigensolver_underflowing_correction<float>(4));
CALL_SUBTEST_7(eigensolver_overflowing_eigenvector<double>(3));
CALL_SUBTEST_7(eigensolver_overflowing_eigenvector<double>(8));
CALL_SUBTEST_7(eigensolver_overflowing_eigenvector<float>(3));
CALL_SUBTEST_7(eigensolver_overflowing_eigenvector<float>(8));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<float>(7));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<float>(8));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<float>(24));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<double>(30));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<double>(50));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<double>(64));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<float>(10, 64));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<float>(10, -80));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<double>(30, 510));
CALL_SUBTEST_5(complex_eigensolver_jordan_block<double>(30, -1000));
// |T|_F below max / (4 n) (exponents 1000, 1019, 123), between max / (4 n) and max (n = 2), above max (n = 5).
CALL_SUBTEST_5(complex_eigensolver_large_triangular<double>(2, 1000));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<double>(2, 1019));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<double>(2, 1021));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<double>(2, 1022));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<double>(5, 1021));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<float>(2, 123));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<float>(2, 125));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<float>(2, 126));
CALL_SUBTEST_5(complex_eigensolver_large_triangular<float>(5, 125));
TEST_SET_BUT_UNUSED_VARIABLE(s);
}