test/simplicial_cholesky.cpp - mirror - Git at Google


            
            // This file is part of Eigen, a lightweight C++ template library

            
            // for linear algebra.

            
            //

            
            // 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 "sparse_solver.h"


            template <typename Solver>

            
            void verify_determinant_asserts(const Solver& solver) {

            
              VERIFY_RAISES_ASSERT(solver.determinant());

            
              VERIFY_RAISES_ASSERT(solver.absDeterminant());

            
              VERIFY_RAISES_ASSERT(solver.logAbsDeterminant());

            
              VERIFY_RAISES_ASSERT(solver.signDeterminant());

            
            }


            // factorize_preordered() breaks out of its column loop on a bad pivot but still sets m_factorizationIsOk,

            
            // leaving the tail of D -- and of L's diagonal -- unwritten. The determinant accessors read exactly those,

            
            // so they check info() too, as the dense LLT ones do.

            
            template <typename SparseMatrixType>

            
            void test_simplicial_cholesky_determinant_asserts() {

            
              typedef typename SparseMatrixType::Scalar Scalar;

            
              const Index n = 6;


              // A zero pivot stops all four classes; SimplicialLLT alone also rejects a negative one.

            
              SparseMatrixType zero_pivot(n, n), negative_pivot(n, n);

            
              for (Index i = 0; i < n; ++i) {

            
                zero_pivot.insert(i, i) = (i == 0) ? Scalar(0) : Scalar(1);

            
                negative_pivot.insert(i, i) = (i == n - 1) ? Scalar(-1) : Scalar(1);

            
              }

            
              zero_pivot.makeCompressed();

            
              negative_pivot.makeCompressed();


              SimplicialLLT<SparseMatrixType> llt(zero_pivot);

            
              VERIFY(llt.info() == NumericalIssue);

            
              verify_determinant_asserts(llt);


              SimplicialLLT<SparseMatrixType> indefinite_llt(negative_pivot);

            
              VERIFY(indefinite_llt.info() == NumericalIssue);

            
              verify_determinant_asserts(indefinite_llt);


              SimplicialLDLT<SparseMatrixType> ldlt(zero_pivot);

            
              VERIFY(ldlt.info() == NumericalIssue);

            
              verify_determinant_asserts(ldlt);


              SimplicialNonHermitianLLT<SparseMatrixType> nhllt(zero_pivot);

            
              VERIFY(nhllt.info() == NumericalIssue);

            
              verify_determinant_asserts(nhllt);


              SimplicialNonHermitianLDLT<SparseMatrixType> nhldlt(zero_pivot);

            
              VERIFY(nhldlt.info() == NumericalIssue);

            
              verify_determinant_asserts(nhldlt);


              // The deprecated SimplicialCholesky exposes determinant() alone, and reads the same tail.

            
              SimplicialCholesky<SparseMatrixType> deprecated(zero_pivot);

            
              VERIFY(deprecated.info() == NumericalIssue);

            
              VERIFY_RAISES_ASSERT(deprecated.determinant());


              // info() alone would not reject an unfactorized decomposition: it is constructed Success.

            
              SimplicialLDLT<SparseMatrixType> unfactorized;

            
              verify_determinant_asserts(unfactorized);

            
            }


            template <typename T, typename I_, int flag>

            
            void test_simplicial_cholesky_T() {

            
              typedef SparseMatrix<T, flag, I_> SparseMatrixType;

            
              SimplicialCholesky<SparseMatrixType, Lower> chol_colmajor_lower_amd;

            
              SimplicialCholesky<SparseMatrixType, Upper> chol_colmajor_upper_amd;

            
              SimplicialLLT<SparseMatrixType, Lower> llt_colmajor_lower_amd;

            
              SimplicialLLT<SparseMatrixType, Upper> llt_colmajor_upper_amd;

            
              SimplicialLDLT<SparseMatrixType, Lower> ldlt_colmajor_lower_amd;

            
              SimplicialLDLT<SparseMatrixType, Upper> ldlt_colmajor_upper_amd;

            
              SimplicialLDLT<SparseMatrixType, Lower, NaturalOrdering<I_> > ldlt_colmajor_lower_nat;

            
              SimplicialLDLT<SparseMatrixType, Upper, NaturalOrdering<I_> > ldlt_colmajor_upper_nat;

            
              SimplicialNonHermitianLLT<SparseMatrixType, Lower> nhllt_colmajor_lower_amd;

            
              SimplicialNonHermitianLLT<SparseMatrixType, Upper> nhllt_colmajor_upper_amd;

            
              SimplicialNonHermitianLDLT<SparseMatrixType, Lower> nhldlt_colmajor_lower_amd;

            
              SimplicialNonHermitianLDLT<SparseMatrixType, Upper> nhldlt_colmajor_upper_amd;

            
              SimplicialNonHermitianLDLT<SparseMatrixType, Lower, NaturalOrdering<I_> > nhldlt_colmajor_lower_nat;

            
              SimplicialNonHermitianLDLT<SparseMatrixType, Upper, NaturalOrdering<I_> > nhldlt_colmajor_upper_nat;


              check_sparse_spd_solving(chol_colmajor_lower_amd);

            
              check_sparse_spd_solving(chol_colmajor_upper_amd);

            
              check_sparse_spd_solving(llt_colmajor_lower_amd);

            
              check_sparse_spd_solving(llt_colmajor_upper_amd);

            
              check_sparse_spd_solving(ldlt_colmajor_lower_amd);

            
              check_sparse_spd_solving(ldlt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_solving(nhllt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_solving(nhllt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_solving(nhldlt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_solving(nhldlt_colmajor_upper_amd);


              check_sparse_spd_determinant(chol_colmajor_lower_amd);

            
              check_sparse_spd_determinant(chol_colmajor_upper_amd);

            
              check_sparse_spd_determinant(llt_colmajor_lower_amd);

            
              check_sparse_spd_determinant(llt_colmajor_upper_amd);

            
              check_sparse_spd_determinant(ldlt_colmajor_lower_amd);

            
              check_sparse_spd_determinant(ldlt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_determinant(nhllt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_determinant(nhllt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_determinant(nhldlt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_determinant(nhldlt_colmajor_upper_amd);


              check_sparse_spd_log_abs_determinant(llt_colmajor_lower_amd);

            
              check_sparse_spd_log_abs_determinant(llt_colmajor_upper_amd);

            
              check_sparse_spd_log_abs_determinant(ldlt_colmajor_lower_amd);

            
              check_sparse_spd_log_abs_determinant(ldlt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_log_abs_determinant(nhllt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_log_abs_determinant(nhllt_colmajor_upper_amd);

            
              check_sparse_nonhermitian_log_abs_determinant(nhldlt_colmajor_lower_amd);

            
              check_sparse_nonhermitian_log_abs_determinant(nhldlt_colmajor_upper_amd);


              test_simplicial_cholesky_determinant_asserts<SparseMatrixType>();


              check_sparse_spd_solving(ldlt_colmajor_lower_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);

            
              check_sparse_spd_solving(ldlt_colmajor_upper_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);

            
              check_sparse_nonhermitian_solving(nhldlt_colmajor_lower_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);

            
              check_sparse_nonhermitian_solving(nhldlt_colmajor_upper_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);

            
            }


            template <typename Scalar>

            
            void test_simplicial_cholesky_scatter(Index bandwidth) {

            
              using RealScalar = typename NumTraits<Scalar>::Real;

            
              using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;

            
              using SparseMatrixType = SparseMatrix<Scalar, ColMajor, long long>;

            
              const Index n = 67;

            
              DenseMatrix matrix = DenseMatrix::Zero(n, n);

            
              for (Index j = 0; j < n; ++j) {

            
                matrix(j, j) = Scalar(2 * bandwidth + 1);

            
                for (Index i = j + 1; i < (std::min)(n, j + bandwidth + 1); ++i) {

            
                  matrix(i, j) = Scalar(0.125) + Scalar(0.0625) * internal::random<Scalar>();

            
                  matrix(j, i) = numext::conj(matrix(i, j));

            
                }

            
              }

            
              SparseMatrixType sparse = matrix.sparseView();

            
              SimplicialLLT<SparseMatrixType, Lower, NaturalOrdering<long long>> solver;

            
              SimplicialLDLT<SparseMatrixType, Lower, NaturalOrdering<long long>> ldlt;

            
              solver.analyzePattern(sparse);

            
              ldlt.analyzePattern(sparse);

            
              // Reconstruction error scales with the O(n * epsilon) factorization backward error.

            
              const RealScalar tolerance = RealScalar(16 * n) * NumTraits<RealScalar>::epsilon();

            
              DenseMatrix lower;

            
              for (int repeat = 0; repeat < 2; ++repeat) {

            
                solver.factorize(sparse);

            
                VERIFY_IS_EQUAL(solver.info(), Success);

            
                lower = solver.matrixL();

            
                VERIFY((lower * lower.adjoint() - matrix).norm() <= tolerance * matrix.norm());

            
                ldlt.factorize(sparse);

            
                VERIFY_IS_EQUAL(ldlt.info(), Success);

            
                lower = ldlt.matrixL();

            
                VERIFY((lower * ldlt.vectorD().asDiagonal() * lower.adjoint() - matrix).norm() <= tolerance * matrix.norm());

            
                matrix.diagonal().array() += Scalar(1);

            
                sparse.diagonal().array() += Scalar(1);

            
              }

            
            }


            EIGEN_DECLARE_TEST(simplicial_cholesky) {

            
              CALL_SUBTEST_31(test_simplicial_cholesky_scatter<float>(3));

            
              CALL_SUBTEST_31(test_simplicial_cholesky_scatter<float>(37));

            
              CALL_SUBTEST_32(test_simplicial_cholesky_scatter<std::complex<float>>(3));

            
              CALL_SUBTEST_32(test_simplicial_cholesky_scatter<std::complex<float>>(37));

            
              CALL_SUBTEST_11((test_simplicial_cholesky_T<double, int, ColMajor>()));

            
              CALL_SUBTEST_12((test_simplicial_cholesky_T<std::complex<double>, int, ColMajor>()));

            
              CALL_SUBTEST_13((test_simplicial_cholesky_T<double, long int, ColMajor>()));

            
              CALL_SUBTEST_21((test_simplicial_cholesky_T<double, int, RowMajor>()));

            
              CALL_SUBTEST_22((test_simplicial_cholesky_T<std::complex<double>, int, RowMajor>()));

            
              CALL_SUBTEST_23((test_simplicial_cholesky_T<double, long int, RowMajor>()));

            
            }
	// This file is part of Eigen, a lightweight C++ template library
	// for linear algebra.
	//
	// 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 "sparse_solver.h"

	template <typename Solver>
	void verify_determinant_asserts(const Solver& solver) {
	VERIFY_RAISES_ASSERT(solver.determinant());
	VERIFY_RAISES_ASSERT(solver.absDeterminant());
	VERIFY_RAISES_ASSERT(solver.logAbsDeterminant());
	VERIFY_RAISES_ASSERT(solver.signDeterminant());
	}

	// factorize_preordered() breaks out of its column loop on a bad pivot but still sets m_factorizationIsOk,
	// leaving the tail of D -- and of L's diagonal -- unwritten. The determinant accessors read exactly those,
	// so they check info() too, as the dense LLT ones do.
	template <typename SparseMatrixType>
	void test_simplicial_cholesky_determinant_asserts() {
	typedef typename SparseMatrixType::Scalar Scalar;
	const Index n = 6;

	// A zero pivot stops all four classes; SimplicialLLT alone also rejects a negative one.
	SparseMatrixType zero_pivot(n, n), negative_pivot(n, n);
	for (Index i = 0; i < n; ++i) {
	zero_pivot.insert(i, i) = (i == 0) ? Scalar(0) : Scalar(1);
	negative_pivot.insert(i, i) = (i == n - 1) ? Scalar(-1) : Scalar(1);
	}
	zero_pivot.makeCompressed();
	negative_pivot.makeCompressed();

	SimplicialLLT<SparseMatrixType> llt(zero_pivot);
	VERIFY(llt.info() == NumericalIssue);
	verify_determinant_asserts(llt);

	SimplicialLLT<SparseMatrixType> indefinite_llt(negative_pivot);
	VERIFY(indefinite_llt.info() == NumericalIssue);
	verify_determinant_asserts(indefinite_llt);

	SimplicialLDLT<SparseMatrixType> ldlt(zero_pivot);
	VERIFY(ldlt.info() == NumericalIssue);
	verify_determinant_asserts(ldlt);

	SimplicialNonHermitianLLT<SparseMatrixType> nhllt(zero_pivot);
	VERIFY(nhllt.info() == NumericalIssue);
	verify_determinant_asserts(nhllt);

	SimplicialNonHermitianLDLT<SparseMatrixType> nhldlt(zero_pivot);
	VERIFY(nhldlt.info() == NumericalIssue);
	verify_determinant_asserts(nhldlt);

	// The deprecated SimplicialCholesky exposes determinant() alone, and reads the same tail.
	SimplicialCholesky<SparseMatrixType> deprecated(zero_pivot);
	VERIFY(deprecated.info() == NumericalIssue);
	VERIFY_RAISES_ASSERT(deprecated.determinant());

	// info() alone would not reject an unfactorized decomposition: it is constructed Success.
	SimplicialLDLT<SparseMatrixType> unfactorized;
	verify_determinant_asserts(unfactorized);
	}

	template <typename T, typename I_, int flag>
	void test_simplicial_cholesky_T() {
	typedef SparseMatrix<T, flag, I_> SparseMatrixType;
	SimplicialCholesky<SparseMatrixType, Lower> chol_colmajor_lower_amd;
	SimplicialCholesky<SparseMatrixType, Upper> chol_colmajor_upper_amd;
	SimplicialLLT<SparseMatrixType, Lower> llt_colmajor_lower_amd;
	SimplicialLLT<SparseMatrixType, Upper> llt_colmajor_upper_amd;
	SimplicialLDLT<SparseMatrixType, Lower> ldlt_colmajor_lower_amd;
	SimplicialLDLT<SparseMatrixType, Upper> ldlt_colmajor_upper_amd;
	SimplicialLDLT<SparseMatrixType, Lower, NaturalOrdering<I_> > ldlt_colmajor_lower_nat;
	SimplicialLDLT<SparseMatrixType, Upper, NaturalOrdering<I_> > ldlt_colmajor_upper_nat;
	SimplicialNonHermitianLLT<SparseMatrixType, Lower> nhllt_colmajor_lower_amd;
	SimplicialNonHermitianLLT<SparseMatrixType, Upper> nhllt_colmajor_upper_amd;
	SimplicialNonHermitianLDLT<SparseMatrixType, Lower> nhldlt_colmajor_lower_amd;
	SimplicialNonHermitianLDLT<SparseMatrixType, Upper> nhldlt_colmajor_upper_amd;
	SimplicialNonHermitianLDLT<SparseMatrixType, Lower, NaturalOrdering<I_> > nhldlt_colmajor_lower_nat;
	SimplicialNonHermitianLDLT<SparseMatrixType, Upper, NaturalOrdering<I_> > nhldlt_colmajor_upper_nat;

	check_sparse_spd_solving(chol_colmajor_lower_amd);
	check_sparse_spd_solving(chol_colmajor_upper_amd);
	check_sparse_spd_solving(llt_colmajor_lower_amd);
	check_sparse_spd_solving(llt_colmajor_upper_amd);
	check_sparse_spd_solving(ldlt_colmajor_lower_amd);
	check_sparse_spd_solving(ldlt_colmajor_upper_amd);
	check_sparse_nonhermitian_solving(nhllt_colmajor_lower_amd);
	check_sparse_nonhermitian_solving(nhllt_colmajor_upper_amd);
	check_sparse_nonhermitian_solving(nhldlt_colmajor_lower_amd);
	check_sparse_nonhermitian_solving(nhldlt_colmajor_upper_amd);

	check_sparse_spd_determinant(chol_colmajor_lower_amd);
	check_sparse_spd_determinant(chol_colmajor_upper_amd);
	check_sparse_spd_determinant(llt_colmajor_lower_amd);
	check_sparse_spd_determinant(llt_colmajor_upper_amd);
	check_sparse_spd_determinant(ldlt_colmajor_lower_amd);
	check_sparse_spd_determinant(ldlt_colmajor_upper_amd);
	check_sparse_nonhermitian_determinant(nhllt_colmajor_lower_amd);
	check_sparse_nonhermitian_determinant(nhllt_colmajor_upper_amd);
	check_sparse_nonhermitian_determinant(nhldlt_colmajor_lower_amd);
	check_sparse_nonhermitian_determinant(nhldlt_colmajor_upper_amd);

	check_sparse_spd_log_abs_determinant(llt_colmajor_lower_amd);
	check_sparse_spd_log_abs_determinant(llt_colmajor_upper_amd);
	check_sparse_spd_log_abs_determinant(ldlt_colmajor_lower_amd);
	check_sparse_spd_log_abs_determinant(ldlt_colmajor_upper_amd);
	check_sparse_nonhermitian_log_abs_determinant(nhllt_colmajor_lower_amd);
	check_sparse_nonhermitian_log_abs_determinant(nhllt_colmajor_upper_amd);
	check_sparse_nonhermitian_log_abs_determinant(nhldlt_colmajor_lower_amd);
	check_sparse_nonhermitian_log_abs_determinant(nhldlt_colmajor_upper_amd);

	test_simplicial_cholesky_determinant_asserts<SparseMatrixType>();

	check_sparse_spd_solving(ldlt_colmajor_lower_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);
	check_sparse_spd_solving(ldlt_colmajor_upper_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);
	check_sparse_nonhermitian_solving(nhldlt_colmajor_lower_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);
	check_sparse_nonhermitian_solving(nhldlt_colmajor_upper_nat, (std::min)(300, EIGEN_TEST_MAX_SIZE), 1000);
	}

	template <typename Scalar>
	void test_simplicial_cholesky_scatter(Index bandwidth) {
	using RealScalar = typename NumTraits<Scalar>::Real;
	using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
	using SparseMatrixType = SparseMatrix<Scalar, ColMajor, long long>;
	const Index n = 67;
	DenseMatrix matrix = DenseMatrix::Zero(n, n);
	for (Index j = 0; j < n; ++j) {
	matrix(j, j) = Scalar(2 * bandwidth + 1);
	for (Index i = j + 1; i < (std::min)(n, j + bandwidth + 1); ++i) {
	matrix(i, j) = Scalar(0.125) + Scalar(0.0625) * internal::random<Scalar>();
	matrix(j, i) = numext::conj(matrix(i, j));
	}
	}
	SparseMatrixType sparse = matrix.sparseView();
	SimplicialLLT<SparseMatrixType, Lower, NaturalOrdering<long long>> solver;
	SimplicialLDLT<SparseMatrixType, Lower, NaturalOrdering<long long>> ldlt;
	solver.analyzePattern(sparse);
	ldlt.analyzePattern(sparse);
	// Reconstruction error scales with the O(n * epsilon) factorization backward error.
	const RealScalar tolerance = RealScalar(16 * n) * NumTraits<RealScalar>::epsilon();
	DenseMatrix lower;
	for (int repeat = 0; repeat < 2; ++repeat) {
	solver.factorize(sparse);
	VERIFY_IS_EQUAL(solver.info(), Success);
	lower = solver.matrixL();
	VERIFY((lower * lower.adjoint() - matrix).norm() <= tolerance * matrix.norm());
	ldlt.factorize(sparse);
	VERIFY_IS_EQUAL(ldlt.info(), Success);
	lower = ldlt.matrixL();
	VERIFY((lower * ldlt.vectorD().asDiagonal() * lower.adjoint() - matrix).norm() <= tolerance * matrix.norm());
	matrix.diagonal().array() += Scalar(1);
	sparse.diagonal().array() += Scalar(1);
	}
	}

	EIGEN_DECLARE_TEST(simplicial_cholesky) {
	CALL_SUBTEST_31(test_simplicial_cholesky_scatter<float>(3));
	CALL_SUBTEST_31(test_simplicial_cholesky_scatter<float>(37));
	CALL_SUBTEST_32(test_simplicial_cholesky_scatter<std::complex<float>>(3));
	CALL_SUBTEST_32(test_simplicial_cholesky_scatter<std::complex<float>>(37));
	CALL_SUBTEST_11((test_simplicial_cholesky_T<double, int, ColMajor>()));
	CALL_SUBTEST_12((test_simplicial_cholesky_T<std::complex<double>, int, ColMajor>()));
	CALL_SUBTEST_13((test_simplicial_cholesky_T<double, long int, ColMajor>()));
	CALL_SUBTEST_21((test_simplicial_cholesky_T<double, int, RowMajor>()));
	CALL_SUBTEST_22((test_simplicial_cholesky_T<std::complex<double>, int, RowMajor>()));
	CALL_SUBTEST_23((test_simplicial_cholesky_T<double, long int, RowMajor>()));
	}