blob: f8677858a3e5b7bfe143e01a4211d0a0925436eb [file] [edit]
// SPDX-FileCopyrightText: The Eigen Authors
// SPDX-License-Identifier: MPL-2.0
#include "main.h"
#include <Eigen/Dense>
#include <Eigen/Sparse>
// det(A) can be representable where the product of its pivots, taken in order, is not. The matrices are S D and
// D S D with S well conditioned and D = diag(2^(+-s)), half of each sign: the scaling is exact, so det(A) = det(S).
// The rank-revealing QR factorizations stop at a column below epsilon times the largest, so they get a D within
// that ratio and enough columns for the big pivots to overflow together.
namespace {
enum Symmetry { General, HermitianPositive, HermitianIndefinite, SymmetricComplex };
template <typename Scalar>
struct ScaledProblem {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
// An exponent of D whose square stays in range, so that a column norm and an entry of D S D do.
static int steepExponent() { return 2 * (std::numeric_limits<RealScalar>::max_exponent / 4 - 4); }
// An exponent of D that keeps every column within epsilon^(1/2) of the largest.
static int gentleExponent() { return std::numeric_limits<RealScalar>::digits / 4; }
// The number of columns at which half of them, scaled by 2^exponent, overflow together.
static Index overflowingSize(int exponent) {
return 2 * (std::numeric_limits<RealScalar>::max_exponent / exponent + 2);
}
ScaledProblem(Index size, Symmetry symmetry, int exponent) : scaleExponent(exponent) {
// S = L diag(u) M with L and M unit triangular, off-diagonal entries of magnitude at most 1 / (2 n) and
// 1 <= |u_i| <= 2, so that det(S) = prod(u), ||L||, ||M|| <= 3/2 and ||S^-1|| <= 4 in the 2-norm.
const RealScalar offDiagonal = RealScalar(1) / RealScalar(2 * size);
MatrixType lower = MatrixType::Identity(size, size);
lower.template triangularView<StrictlyLower>() = offDiagonal * MatrixType::Random(size, size);
MatrixType upper;
if (symmetry == General) {
upper = MatrixType::Identity(size, size);
upper.template triangularView<StrictlyUpper>() = offDiagonal * MatrixType::Random(size, size);
} else if (symmetry == SymmetricComplex) {
upper = lower.transpose();
} else {
upper = lower.adjoint();
}
determinant = Scalar(1);
Matrix<Scalar, Dynamic, 1> pivots(size);
for (Index i = 0; i < size; ++i) {
Scalar pivot = Scalar(internal::random<RealScalar>(RealScalar(1), RealScalar(2)));
// A random sign or phase, except where L L^T needs a real square root.
if (symmetry == General || (symmetry == SymmetricComplex && NumTraits<Scalar>::IsComplex))
pivot *= numext::sign(internal::random<Scalar>());
if (symmetry == HermitianIndefinite && i % 3 == 0) pivot = -pivot;
pivots[i] = pivot;
determinant *= pivot;
}
S = lower * pivots.asDiagonal() * upper;
// To first order, det(S + E) = det(S) (1 + tr(S^-1 E)) and |tr(S^-1 E)| <= n ||S^-1|| ||E||. Forming S and
// factoring it each leave ||E|| <= n epsilon ||L|| ||u|| ||M|| <= 9/2 n epsilon (Higham, Accuracy and Stability of
// Numerical Algorithms, 2nd ed., Theorem 9.3), column scaling aside: 36 n^2 epsilon in all.
tolerance = RealScalar(64 * size * size) * NumTraits<RealScalar>::epsilon();
VERIFY(tolerance < RealScalar(1) / RealScalar(16));
const RealScalar big = std::ldexp(RealScalar(1), scaleExponent);
const RealScalar bigRoot = std::ldexp(RealScalar(1), scaleExponent / 2);
columnScaled = S;
symmetricScaled = S;
allBig = big * S;
for (Index j = 0; j < size; ++j) {
const bool isBig = j < size / 2;
columnScaled.col(j) *= isBig ? big : RealScalar(1) / big;
symmetricScaled.col(j) *= isBig ? bigRoot : RealScalar(1) / bigRoot;
symmetricScaled.row(j) *= isBig ? bigRoot : RealScalar(1) / bigRoot;
}
}
// Whether the product of half of the pivots, each scaled by 2^exponentPerPivot, overflows.
bool bigPivotsOverflow(int exponentPerPivot) const {
return (S.rows() / 2) * exponentPerPivot > std::numeric_limits<RealScalar>::max_exponent;
}
int scaleExponent;
MatrixType S, columnScaled, symmetricScaled, allBig;
Scalar determinant;
RealScalar tolerance;
};
// absDeterminant() and logAbsDeterminant() return Scalar in SparseLU.
template <typename Solver, typename Scalar>
void check_determinant(const Solver& solver, const Scalar& expected,
const typename NumTraits<Scalar>::Real& tolerance) {
using RealScalar = typename NumTraits<Scalar>::Real;
const RealScalar expectedAbs = numext::abs(expected);
VERIFY(numext::abs(Scalar(solver.determinant()) - expected) <= tolerance * expectedAbs);
VERIFY(numext::abs(numext::real(Scalar(solver.absDeterminant())) - expectedAbs) <= tolerance * expectedAbs);
// d log|det| = d|det| / |det|, and the log itself rounds.
const RealScalar expectedLog = numext::log(expectedAbs);
VERIFY(numext::abs(numext::real(Scalar(solver.logAbsDeterminant())) - expectedLog) <=
tolerance + RealScalar(4) * NumTraits<RealScalar>::epsilon() * numext::abs(expectedLog));
}
// det(2^s S) overflows, and only it: the log is that of det(S) plus n s log(2).
template <typename Solver, typename Scalar>
void check_overflowing_determinant(const Solver& solver, const ScaledProblem<Scalar>& problem) {
using RealScalar = typename NumTraits<Scalar>::Real;
const Scalar det = solver.determinant();
VERIFY(!(numext::isfinite)(numext::abs(det)));
VERIFY(!(numext::isnan)(numext::real(det)) && !(numext::isnan)(numext::imag(det)));
VERIFY_IS_EQUAL(numext::real(Scalar(solver.absDeterminant())), NumTraits<RealScalar>::infinity());
const RealScalar expectedLog = numext::log(numext::abs(problem.determinant)) +
RealScalar(problem.S.rows() * problem.scaleExponent) * numext::log(RealScalar(2));
VERIFY(numext::abs(numext::real(Scalar(solver.logAbsDeterminant())) - expectedLog) <=
problem.tolerance + RealScalar(4) * NumTraits<RealScalar>::epsilon() * expectedLog);
}
template <typename Scalar>
void determinant_scaling_general(Index size) {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
const ScaledProblem<Scalar> problem(size, General, ScaledProblem<Scalar>::steepExponent());
const MatrixType& A = problem.columnScaled;
const Scalar det = problem.determinant;
const RealScalar tolerance = problem.tolerance;
VERIFY(problem.bigPivotsOverflow(problem.scaleExponent));
check_determinant(PartialPivLU<MatrixType>(A), det, tolerance);
check_determinant(HouseholderQR<MatrixType>(A), det, tolerance);
VERIFY(numext::abs(A.determinant() - det) <= tolerance * numext::abs(det));
// The small columns are below any rank threshold relative to the big ones.
FullPivLU<MatrixType> fullPivLU(size, size);
fullPivLU.setThreshold(RealScalar(0));
fullPivLU.compute(A);
check_determinant(fullPivLU, det, tolerance);
check_overflowing_determinant(PartialPivLU<MatrixType>(problem.allBig), problem);
check_overflowing_determinant(FullPivLU<MatrixType>(problem.allBig), problem);
check_overflowing_determinant(HouseholderQR<MatrixType>(problem.allBig), problem);
check_overflowing_determinant(ColPivHouseholderQR<MatrixType>(problem.allBig), problem);
// U of P A = L U holds the pivots; det(P) = +-1.
const PartialPivLU<MatrixType> lu(A);
const Scalar triangular = lu.matrixLU().template triangularView<Upper>().determinant();
VERIFY(numext::abs(triangular * Scalar(RealScalar(lu.permutationP().determinant())) - det) <=
tolerance * numext::abs(det));
SparseLU<SparseMatrix<Scalar>> sparseLU(A.sparseView());
VERIFY_IS_EQUAL(sparseLU.info(), Success);
check_determinant(sparseLU, det, tolerance);
SparseLU<SparseMatrix<Scalar>> sparseBig(problem.allBig.sparseView());
VERIFY_IS_EQUAL(sparseBig.info(), Success);
check_overflowing_determinant(sparseBig, problem);
}
template <typename Scalar>
void determinant_scaling_rank_revealing() {
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
const int exponent = ScaledProblem<Scalar>::gentleExponent();
const ScaledProblem<Scalar> problem(ScaledProblem<Scalar>::overflowingSize(exponent), General, exponent);
VERIFY(problem.bigPivotsOverflow(exponent));
const ColPivHouseholderQR<MatrixType> colPiv(problem.columnScaled);
VERIFY(colPiv.isInjective());
check_determinant(colPiv, problem.determinant, problem.tolerance);
const FullPivHouseholderQR<MatrixType> fullPiv(problem.columnScaled);
VERIFY(fullPiv.isInjective());
check_determinant(fullPiv, problem.determinant, problem.tolerance);
check_determinant(CompleteOrthogonalDecomposition<MatrixType>(problem.columnScaled), problem.determinant,
problem.tolerance);
const RandColPivHouseholderQR<MatrixType> randColPiv(problem.columnScaled);
VERIFY(randColPiv.isInjective());
check_determinant(randColPiv, problem.determinant, problem.tolerance);
const FullPivLU<MatrixType> fullPivLU(problem.columnScaled);
VERIFY(fullPivLU.isInjective());
check_determinant(fullPivLU, problem.determinant, problem.tolerance);
}
template <typename Scalar>
void determinant_scaling_hermitian(Index size) {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
using SparseType = SparseMatrix<Scalar>;
{
const ScaledProblem<Scalar> problem(size, HermitianPositive, ScaledProblem<Scalar>::steepExponent());
const MatrixType& A = problem.symmetricScaled;
const Scalar det = problem.determinant;
const RealScalar tolerance = problem.tolerance;
// The pivots of L are 2^(s / 2) l_ii and those of D are 2^s d_i.
VERIFY(problem.bigPivotsOverflow(problem.scaleExponent / 2));
const LLT<MatrixType> llt(A);
VERIFY_IS_EQUAL(llt.info(), Success);
check_determinant(llt, det, tolerance);
const LDLT<MatrixType> ldlt(A);
VERIFY_IS_EQUAL(ldlt.info(), Success);
check_determinant(ldlt, det, tolerance);
check_determinant(BunchKaufman<MatrixType>(A), det, tolerance);
const SparseType sparse = A.sparseView();
const SimplicialLLT<SparseType> simplicialLLT(sparse);
VERIFY_IS_EQUAL(simplicialLLT.info(), Success);
check_determinant(simplicialLLT, det, tolerance);
const SimplicialLDLT<SparseType> simplicialLDLT(sparse);
VERIFY_IS_EQUAL(simplicialLDLT.info(), Success);
check_determinant(simplicialLDLT, det, tolerance);
const SimplicialCholesky<SparseType> simplicialCholesky(sparse);
VERIFY_IS_EQUAL(simplicialCholesky.info(), Success);
VERIFY(numext::abs(simplicialCholesky.determinant() - det) <= tolerance * numext::abs(det));
const LLT<MatrixType> big(problem.allBig);
VERIFY_IS_EQUAL(big.info(), Success);
check_overflowing_determinant(big, problem);
check_overflowing_determinant(LDLT<MatrixType>(problem.allBig), problem);
check_overflowing_determinant(SimplicialLLT<SparseType>(problem.allBig.sparseView()), problem);
check_overflowing_determinant(SimplicialLDLT<SparseType>(problem.allBig.sparseView()), problem);
}
{
const ScaledProblem<Scalar> problem(size, HermitianIndefinite, ScaledProblem<Scalar>::steepExponent());
check_determinant(BunchKaufman<MatrixType, Lower>(problem.symmetricScaled), problem.determinant, problem.tolerance);
check_determinant(BunchKaufman<MatrixType, Upper>(problem.symmetricScaled), problem.determinant, problem.tolerance);
check_overflowing_determinant(BunchKaufman<MatrixType>(problem.allBig), problem);
}
{
// A = L L^T and A = L D L^T of a symmetric matrix, which is not Hermitian for a complex scalar.
const ScaledProblem<Scalar> problem(size, SymmetricComplex, ScaledProblem<Scalar>::steepExponent());
const SparseType sparse = problem.symmetricScaled.sparseView();
const SimplicialNonHermitianLLT<SparseType> llt(sparse);
VERIFY_IS_EQUAL(llt.info(), Success);
check_determinant(llt, problem.determinant, problem.tolerance);
const SimplicialNonHermitianLDLT<SparseType> ldlt(sparse);
VERIFY_IS_EQUAL(ldlt.info(), Success);
check_determinant(ldlt, problem.determinant, problem.tolerance);
}
}
// A zero pivot that follows pivots whose product overflows gives a zero determinant, not inf * 0.
template <typename Scalar>
void determinant_scaling_singular() {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
using VectorType = Matrix<Scalar, Dynamic, 1>;
const RealScalar big = std::ldexp(RealScalar(1), ScaledProblem<Scalar>::steepExponent());
VectorType diagonal = VectorType::Constant(6, Scalar(big));
diagonal[5] = Scalar(0);
const MatrixType A = diagonal.asDiagonal();
VERIFY_IS_EQUAL(PartialPivLU<MatrixType>(A).determinant(), Scalar(0));
VERIFY_IS_EQUAL(PartialPivLU<MatrixType>(A).absDeterminant(), RealScalar(0));
VERIFY_IS_EQUAL(PartialPivLU<MatrixType>(A).logAbsDeterminant(), -NumTraits<RealScalar>::infinity());
VERIFY_IS_EQUAL(FullPivLU<MatrixType>(A).determinant(), Scalar(0));
VERIFY_IS_EQUAL(HouseholderQR<MatrixType>(A).determinant(), Scalar(0));
VERIFY_IS_EQUAL(HouseholderQR<MatrixType>(A).absDeterminant(), RealScalar(0));
VERIFY_IS_EQUAL(A.determinant(), Scalar(0));
VERIFY_IS_EQUAL(A.template triangularView<Upper>().determinant(), Scalar(0));
VERIFY_IS_EQUAL(A.template triangularView<Lower>().determinant(), Scalar(0));
VERIFY_IS_EQUAL(BunchKaufman<MatrixType>(A).determinant(), Scalar(0));
}
template <typename Scalar>
void determinant_scaling_views() {
using RealScalar = typename NumTraits<Scalar>::Real;
using MatrixType = Matrix<Scalar, Dynamic, Dynamic>;
const RealScalar big = std::ldexp(RealScalar(1), ScaledProblem<Scalar>::steepExponent());
const RealScalar small = RealScalar(1) / big;
Matrix<Scalar, 6, 6> triangular = Matrix<Scalar, 6, 6>::Random();
triangular.diagonal() << Scalar(big), Scalar(3 * big), Scalar(-big), Scalar(small), Scalar(small), Scalar(5 * small);
VERIFY_IS_EQUAL(triangular.template triangularView<Upper>().determinant(), Scalar(-15));
VERIFY_IS_EQUAL(triangular.template triangularView<Lower>().determinant(), Scalar(-15));
VERIFY_IS_EQUAL(triangular.template triangularView<UnitUpper>().determinant(), Scalar(1));
VERIFY_IS_EQUAL(MatrixType(triangular).template triangularView<Upper>().determinant(), Scalar(-15));
Matrix<int, 6, 1> indices;
indices << 1, 0, 2, 3, 4, 5;
const PermutationMatrix<6> transposition(indices);
const DiagonalMatrix<Scalar, 6> scales(triangular.diagonal());
const ScaledPermutationMatrix<Scalar, 6> scaled = transposition * scales;
VERIFY_IS_EQUAL(scaled.determinant(), Scalar(15));
}
// A scalar without an exact frexp keeps the plain product and the sum of logs.
template <typename = void>
void determinant_scaling_plain_scalar() {
using Scalar = Eigen::half;
STATIC_CHECK(!internal::has_scaled_product<Scalar>::value);
Matrix<Scalar, 3, 3> A;
A << Scalar(2.0f), Scalar(1.0f), Scalar(0.0f), Scalar(0.0f), Scalar(-4.0f), Scalar(1.0f), Scalar(0.0f), Scalar(0.0f),
Scalar(0.5f);
VERIFY_IS_EQUAL(A.template triangularView<Upper>().determinant(), Scalar(-4.0f));
const PartialPivLU<Matrix<Scalar, 3, 3>> lu(A);
VERIFY_IS_EQUAL(lu.determinant(), Scalar(-4.0f));
VERIFY_IS_EQUAL(lu.absDeterminant(), Scalar(4.0f));
VERIFY_IS_APPROX(float(lu.logAbsDeterminant()), std::log(4.0f));
}
// BunchKaufman balances the product of the blocks of D for the scalars that scaled_product multiplies directly.
template <typename Scalar>
void determinant_scaling_bunch_kaufman_plain_scalar() {
STATIC_CHECK(!internal::has_scaled_product<Scalar>::value);
using MatrixType = Matrix<Scalar, 4, 4>;
// big^2 overflows and small^2 underflows.
const int exponent = (std::numeric_limits<Scalar>::max_exponent + 1) / 2 + 1;
const Scalar big(std::ldexp(1.0f, exponent)), small(std::ldexp(1.0f, -exponent));
VERIFY(!(numext::isfinite)(big * big));
MatrixType A = MatrixType::Zero();
A.diagonal() << big, -big, small, small;
const BunchKaufman<MatrixType> pivots1x1(A);
VERIFY_IS_EQUAL(pivots1x1.info(), Success);
VERIFY_IS_EQUAL(pivots1x1.determinant(), Scalar(-1.0f));
VERIFY_IS_EQUAL(pivots1x1.absDeterminant(), Scalar(1.0f));
VERIFY_IS_EQUAL(pivots1x1.logAbsDeterminant(), Scalar(0.0f));
// Two 2x2 pivot blocks with determinants -big^2 and -small^2.
A.setZero();
A(0, 1) = A(1, 0) = big;
A(2, 3) = A(3, 2) = small;
const BunchKaufman<MatrixType> pivots2x2(A);
VERIFY_IS_EQUAL(pivots2x2.info(), Success);
VERIFY_IS_EQUAL(pivots2x2.determinant(), Scalar(1.0f));
VERIFY_IS_EQUAL(pivots2x2.absDeterminant(), Scalar(1.0f));
A.diagonal() << big, big, big, Scalar(0.0f);
A(0, 1) = A(1, 0) = A(2, 3) = A(3, 2) = Scalar(0.0f);
VERIFY_IS_EQUAL(BunchKaufman<MatrixType>(A).determinant(), Scalar(0.0f));
}
} // namespace
EIGEN_DECLARE_TEST(determinant_scaling) {
for (int i = 0; i < g_repeat; ++i) {
// The pivots of half the columns must overflow together, including those of L in L L^*, which scale by 2^(s / 2).
const Index size = 2 * internal::random<Index>(6, 10);
CALL_SUBTEST_1(determinant_scaling_general<float>(size));
CALL_SUBTEST_1(determinant_scaling_hermitian<float>(size));
CALL_SUBTEST_2(determinant_scaling_general<double>(size));
CALL_SUBTEST_2(determinant_scaling_hermitian<double>(size));
CALL_SUBTEST_3(determinant_scaling_general<std::complex<float>>(size));
CALL_SUBTEST_3(determinant_scaling_hermitian<std::complex<float>>(size));
CALL_SUBTEST_4(determinant_scaling_general<std::complex<double>>(size));
CALL_SUBTEST_4(determinant_scaling_hermitian<std::complex<double>>(size));
CALL_SUBTEST_5(determinant_scaling_general<long double>(size));
CALL_SUBTEST_5(determinant_scaling_hermitian<long double>(size));
}
CALL_SUBTEST_1(determinant_scaling_rank_revealing<float>());
CALL_SUBTEST_2(determinant_scaling_rank_revealing<double>());
CALL_SUBTEST_3(determinant_scaling_rank_revealing<std::complex<float>>());
CALL_SUBTEST_4(determinant_scaling_rank_revealing<std::complex<double>>());
CALL_SUBTEST_1(determinant_scaling_singular<float>());
CALL_SUBTEST_2(determinant_scaling_singular<double>());
CALL_SUBTEST_3(determinant_scaling_singular<std::complex<float>>());
CALL_SUBTEST_4(determinant_scaling_singular<std::complex<double>>());
CALL_SUBTEST_5(determinant_scaling_singular<long double>());
CALL_SUBTEST_1(determinant_scaling_views<float>());
CALL_SUBTEST_2(determinant_scaling_views<double>());
CALL_SUBTEST_3(determinant_scaling_views<std::complex<float>>());
CALL_SUBTEST_4(determinant_scaling_views<std::complex<double>>());
CALL_SUBTEST_5(determinant_scaling_views<long double>());
CALL_SUBTEST_1(determinant_scaling_plain_scalar());
CALL_SUBTEST_1(determinant_scaling_bunch_kaufman_plain_scalar<Eigen::half>());
CALL_SUBTEST_1(determinant_scaling_bunch_kaufman_plain_scalar<Eigen::bfloat16>());
}