| // This file is part of Eigen, a lightweight C++ template library | |
| // for linear algebra. | |
| // | |
| // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr> | |
| // Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com> | |
| // | |
| // 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 <Eigen/QR> | |
| #include <Eigen/SVD> | |
| #include "solverbase.h" | |
| #include "fp_control.h" | |
| template <typename MatrixType> | |
| void cod() { | |
| Index rows = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE); | |
| Index cols = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE); | |
| Index cols2 = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE); | |
| Index rank = internal::random<Index>(1, (std::min)(rows, cols) - 1); | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| using MatrixQType = Matrix<Scalar, MatrixType::RowsAtCompileTime, MatrixType::RowsAtCompileTime>; | |
| MatrixType matrix; | |
| createRandomPIMatrixOfRank(rank, rows, cols, matrix); | |
| CompleteOrthogonalDecomposition<MatrixType> cod(matrix); | |
| VERIFY(rank == cod.rank()); | |
| VERIFY(cols - cod.rank() == cod.dimensionOfKernel()); | |
| VERIFY(!cod.isInjective()); | |
| VERIFY(!cod.isInvertible()); | |
| VERIFY(!cod.isSurjective()); | |
| MatrixQType q = cod.householderQ(); | |
| VERIFY_IS_UNITARY(q); | |
| MatrixType z = cod.matrixZ(); | |
| VERIFY_IS_UNITARY(z); | |
| MatrixType t; | |
| t.setZero(rows, cols); | |
| t.topLeftCorner(rank, rank) = cod.matrixT().topLeftCorner(rank, rank).template triangularView<Upper>(); | |
| MatrixType c = q * t * z * cod.colsPermutation().inverse(); | |
| VERIFY_IS_APPROX(matrix, c); | |
| check_solverbase<MatrixType, MatrixType>(matrix, cod, rows, cols, cols2); | |
| // Verify that we get the same minimum-norm solution as the SVD. | |
| MatrixType exact_solution = MatrixType::Random(cols, cols2); | |
| MatrixType rhs = matrix * exact_solution; | |
| MatrixType cod_solution = cod.solve(rhs); | |
| JacobiSVD<MatrixType, ComputeThinU | ComputeThinV> svd(matrix); | |
| MatrixType svd_solution = svd.solve(rhs); | |
| VERIFY_IS_APPROX(cod_solution, svd_solution); | |
| MatrixType pinv = cod.pseudoInverse(); | |
| VERIFY_IS_APPROX(cod_solution, pinv * rhs); | |
| // Z is the identity at full column rank, also when reusing a rank-deficient decomposition of the same shape. | |
| MatrixType deficient; | |
| createRandomPIMatrixOfRank(cols - 1, cols, cols, deficient); | |
| CompleteOrthogonalDecomposition<MatrixType> cod3(deficient); | |
| cod3.compute(MatrixType::Identity(cols, cols)); | |
| VERIFY_IS_APPROX(MatrixType(cod3.matrixZ()), MatrixType::Identity(cols, cols)); | |
| // now construct a (square) matrix with prescribed determinant | |
| Index size = internal::random<Index>(2, 20); | |
| matrix.setZero(size, size); | |
| setRandomWellConditionedDiagonal(matrix); | |
| Scalar det = matrix.diagonal().prod(); | |
| RealScalar absdet = numext::abs(det); | |
| // Rotate the diagonal matrix by a random unitary matrix, so that the determinants are those of a dense matrix. | |
| q = generateRandomUnitaryMatrix<MatrixQType>(size); | |
| matrix = q * matrix * q.adjoint(); | |
| CompleteOrthogonalDecomposition<MatrixType> cod2(matrix); | |
| VERIFY_IS_APPROX(det, cod2.determinant()); | |
| VERIFY_IS_APPROX(absdet, cod2.absDeterminant()); | |
| VERIFY_IS_APPROX(numext::log(absdet), cod2.logAbsDeterminant()); | |
| VERIFY_IS_APPROX(numext::sign(det), cod2.signDeterminant()); | |
| } | |
| template <typename MatrixType, int Cols2> | |
| void cod_fixedsize() { | |
| enum { Rows = MatrixType::RowsAtCompileTime, Cols = MatrixType::ColsAtCompileTime }; | |
| using Scalar = typename MatrixType::Scalar; | |
| using COD = CompleteOrthogonalDecomposition<Matrix<Scalar, Rows, Cols>>; | |
| int rank = internal::random<int>(1, (std::min)(int(Rows), int(Cols)) - 1); | |
| Matrix<Scalar, Rows, Cols> matrix; | |
| createRandomPIMatrixOfRank(rank, Rows, Cols, matrix); | |
| COD cod(matrix); | |
| VERIFY(rank == cod.rank()); | |
| VERIFY(Cols - cod.rank() == cod.dimensionOfKernel()); | |
| VERIFY(cod.isInjective() == (rank == Rows)); | |
| VERIFY(cod.isSurjective() == (rank == Cols)); | |
| VERIFY(cod.isInvertible() == (cod.isInjective() && cod.isSurjective())); | |
| Matrix<Scalar, Cols, Cols> z = cod.matrixZ(); | |
| VERIFY_IS_UNITARY(z); | |
| check_solverbase<Matrix<Scalar, Cols, Cols2>, Matrix<Scalar, Rows, Cols2> >(matrix, cod, Rows, Cols, Cols2); | |
| // Verify that we get the same minimum-norm solution as the SVD. | |
| Matrix<Scalar, Cols, Cols2> exact_solution; | |
| exact_solution.setRandom(Cols, Cols2); | |
| Matrix<Scalar, Rows, Cols2> rhs = matrix * exact_solution; | |
| Matrix<Scalar, Cols, Cols2> cod_solution = cod.solve(rhs); | |
| JacobiSVD<MatrixType, ComputeFullU | ComputeFullV> svd(matrix); | |
| Matrix<Scalar, Cols, Cols2> svd_solution = svd.solve(rhs); | |
| VERIFY_IS_APPROX(cod_solution, svd_solution); | |
| typename Inverse<COD>::PlainObject pinv = cod.pseudoInverse(); | |
| VERIFY_IS_APPROX(cod_solution, pinv * rhs); | |
| } | |
| template <typename MatrixType> | |
| void qr() { | |
| using std::sqrt; | |
| Index rows = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE), cols = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE), | |
| cols2 = internal::random<Index>(2, EIGEN_TEST_MAX_SIZE); | |
| Index rank = internal::random<Index>(1, (std::min)(rows, cols) - 1); | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| using MatrixQType = Matrix<Scalar, MatrixType::RowsAtCompileTime, MatrixType::RowsAtCompileTime>; | |
| MatrixType m1; | |
| createRandomPIMatrixOfRank(rank, rows, cols, m1); | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| VERIFY_IS_EQUAL(rank, qr.rank()); | |
| VERIFY_IS_EQUAL(cols - qr.rank(), qr.dimensionOfKernel()); | |
| VERIFY(!qr.isInjective()); | |
| VERIFY(!qr.isInvertible()); | |
| VERIFY(!qr.isSurjective()); | |
| MatrixQType q = qr.householderQ(); | |
| VERIFY_IS_UNITARY(q); | |
| MatrixType r = qr.matrixQR().template triangularView<Upper>(); | |
| MatrixType c = q * r * qr.colsPermutation().inverse(); | |
| VERIFY_IS_APPROX(m1, c); | |
| // Verify that the absolute value of the diagonal elements in R are | |
| // non-increasing until they reach the singularity threshold. | |
| RealScalar threshold = sqrt(RealScalar(rows)) * numext::abs(r(0, 0)) * NumTraits<Scalar>::epsilon(); | |
| for (Index i = 0; i < (std::min)(rows, cols) - 1; ++i) { | |
| RealScalar x = numext::abs(r(i, i)); | |
| RealScalar y = numext::abs(r(i + 1, i + 1)); | |
| if (x < threshold && y < threshold) continue; | |
| if (!test_isApproxOrLessThan(y, x)) { | |
| for (Index j = 0; j < (std::min)(rows, cols); ++j) { | |
| std::cout << "i = " << j << ", |r_ii| = " << numext::abs(r(j, j)) << std::endl; | |
| } | |
| std::cout << "Failure at i=" << i << ", rank=" << rank << ", threshold=" << threshold << std::endl; | |
| } | |
| VERIFY_IS_APPROX_OR_LESS_THAN(y, x); | |
| } | |
| check_solverbase<MatrixType, MatrixType>(m1, qr, rows, cols, cols2); | |
| { | |
| MatrixType m2, m3; | |
| Index size = rows; | |
| // Create a random diagonally dominant (thus invertible) matrix. | |
| m1 = MatrixType::Random(size, size); | |
| m1.diagonal().array() += Scalar(2 * size); | |
| qr.compute(m1); | |
| MatrixType m1_inv = qr.inverse(); | |
| m3 = m1 * MatrixType::Random(size, cols2); | |
| m2 = qr.solve(m3); | |
| VERIFY_IS_APPROX(m2, m1_inv * m3); | |
| } | |
| } | |
| template <typename MatrixType, int Cols2> | |
| void qr_fixedsize() { | |
| using std::abs; | |
| using std::sqrt; | |
| enum { Rows = MatrixType::RowsAtCompileTime, Cols = MatrixType::ColsAtCompileTime }; | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| int rank = internal::random<int>(1, (std::min)(int(Rows), int(Cols)) - 1); | |
| Matrix<Scalar, Rows, Cols> m1; | |
| createRandomPIMatrixOfRank(rank, Rows, Cols, m1); | |
| ColPivHouseholderQR<Matrix<Scalar, Rows, Cols> > qr(m1); | |
| VERIFY_IS_EQUAL(rank, qr.rank()); | |
| VERIFY_IS_EQUAL(Cols - qr.rank(), qr.dimensionOfKernel()); | |
| VERIFY_IS_EQUAL(qr.isInjective(), (rank == Rows)); | |
| VERIFY_IS_EQUAL(qr.isSurjective(), (rank == Cols)); | |
| VERIFY_IS_EQUAL(qr.isInvertible(), (qr.isInjective() && qr.isSurjective())); | |
| Matrix<Scalar, Rows, Cols> r = qr.matrixQR().template triangularView<Upper>(); | |
| Matrix<Scalar, Rows, Cols> c = qr.householderQ() * r * qr.colsPermutation().inverse(); | |
| VERIFY_IS_APPROX(m1, c); | |
| check_solverbase<Matrix<Scalar, Cols, Cols2>, Matrix<Scalar, Rows, Cols2> >(m1, qr, Rows, Cols, Cols2); | |
| // Verify that the absolute value of the diagonal elements in R are | |
| // non-increasing until they reache the singularity threshold. | |
| RealScalar threshold = sqrt(RealScalar(Rows)) * (std::abs)(r(0, 0)) * NumTraits<Scalar>::epsilon(); | |
| for (Index i = 0; i < (std::min)(int(Rows), int(Cols)) - 1; ++i) { | |
| RealScalar x = numext::abs(r(i, i)); | |
| RealScalar y = numext::abs(r(i + 1, i + 1)); | |
| if (x < threshold && y < threshold) continue; | |
| if (!test_isApproxOrLessThan(y, x)) { | |
| for (Index j = 0; j < (std::min)(int(Rows), int(Cols)); ++j) { | |
| std::cout << "i = " << j << ", |r_ii| = " << numext::abs(r(j, j)) << std::endl; | |
| } | |
| std::cout << "Failure at i=" << i << ", rank=" << rank << ", threshold=" << threshold << std::endl; | |
| } | |
| VERIFY_IS_APPROX_OR_LESS_THAN(y, x); | |
| } | |
| } | |
| // This test is meant to verify that pivots are chosen such that | |
| // even for a graded matrix, the diagonal of R falls of roughly | |
| // monotonically until it reaches the threshold for singularity. | |
| // We use the so-called Kahan matrix, which is a famous counter-example | |
| // for rank-revealing QR. See | |
| // http://www.netlib.org/lapack/lawnspdf/lawn176.pdf | |
| // page 3 for more detail. | |
| template <typename MatrixType> | |
| void qr_kahan_matrix() { | |
| using std::abs; | |
| using std::sqrt; | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| Index rows = 300, cols = rows; | |
| MatrixType m1; | |
| m1.setZero(rows, cols); | |
| RealScalar s = std::pow(NumTraits<RealScalar>::epsilon(), 1.0 / rows); | |
| RealScalar c = std::sqrt(1 - s * s); | |
| RealScalar pow_s_i(1.0); // pow(s,i) | |
| for (Index i = 0; i < rows; ++i) { | |
| m1(i, i) = pow_s_i; | |
| m1.row(i).tail(rows - i - 1) = -pow_s_i * c * MatrixType::Ones(1, rows - i - 1); | |
| pow_s_i *= s; | |
| } | |
| m1 = (m1 + m1.transpose()).eval(); | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| MatrixType r = qr.matrixQR().template triangularView<Upper>(); | |
| RealScalar threshold = std::sqrt(RealScalar(rows)) * numext::abs(r(0, 0)) * NumTraits<Scalar>::epsilon(); | |
| for (Index i = 0; i < (std::min)(rows, cols) - 1; ++i) { | |
| RealScalar x = numext::abs(r(i, i)); | |
| RealScalar y = numext::abs(r(i + 1, i + 1)); | |
| if (x < threshold && y < threshold) continue; | |
| if (!test_isApproxOrLessThan(y, x)) { | |
| for (Index j = 0; j < (std::min)(rows, cols); ++j) { | |
| std::cout << "i = " << j << ", |r_ii| = " << numext::abs(r(j, j)) << std::endl; | |
| } | |
| std::cout << "Failure at i=" << i << ", rank=" << qr.rank() << ", threshold=" << threshold << std::endl; | |
| } | |
| VERIFY_IS_APPROX_OR_LESS_THAN(y, x); | |
| } | |
| } | |
| template <typename MatrixType> | |
| void qr_invertible() { | |
| using std::abs; | |
| using std::log; | |
| using RealScalar = typename NumTraits<typename MatrixType::Scalar>::Real; | |
| using Scalar = typename MatrixType::Scalar; | |
| int size = internal::random<int>(10, 50); | |
| MatrixType m1(size, size), m2(size, size), m3(size, size); | |
| m1 = MatrixType::Random(size, size); | |
| if (std::is_same<RealScalar, float>::value) { | |
| // let's build a matrix more stable to inverse | |
| MatrixType a = MatrixType::Random(size, size * 2); | |
| m1 += a * a.adjoint(); | |
| } | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| check_solverbase<MatrixType, MatrixType>(m1, qr, size, size, size); | |
| // now construct a matrix with prescribed determinant | |
| m1.setZero(); | |
| setRandomWellConditionedDiagonal(m1); | |
| Scalar det = m1.diagonal().prod(); | |
| RealScalar absdet = abs(det); | |
| m3 = qr.householderQ(); // get a unitary | |
| m1 = m3 * m1 * m3.adjoint(); | |
| qr.compute(m1); | |
| VERIFY_IS_APPROX(det, qr.determinant()); | |
| VERIFY_IS_APPROX(absdet, qr.absDeterminant()); | |
| VERIFY_IS_APPROX(log(absdet), qr.logAbsDeterminant()); | |
| VERIFY_IS_APPROX(numext::sign(det), qr.signDeterminant()); | |
| } | |
| template <typename MatrixType> | |
| void qr_verify_assert() { | |
| MatrixType tmp; | |
| ColPivHouseholderQR<MatrixType> qr; | |
| VERIFY_RAISES_ASSERT(qr.matrixQR()) | |
| VERIFY_RAISES_ASSERT(qr.solve(tmp)) | |
| VERIFY_RAISES_ASSERT(qr.transpose().solve(tmp)) | |
| VERIFY_RAISES_ASSERT(qr.adjoint().solve(tmp)) | |
| VERIFY_RAISES_ASSERT(qr.householderQ()) | |
| VERIFY_RAISES_ASSERT(qr.dimensionOfKernel()) | |
| VERIFY_RAISES_ASSERT(qr.isInjective()) | |
| VERIFY_RAISES_ASSERT(qr.isSurjective()) | |
| VERIFY_RAISES_ASSERT(qr.isInvertible()) | |
| VERIFY_RAISES_ASSERT(qr.inverse()) | |
| VERIFY_RAISES_ASSERT(qr.determinant()) | |
| VERIFY_RAISES_ASSERT(qr.absDeterminant()) | |
| VERIFY_RAISES_ASSERT(qr.logAbsDeterminant()) | |
| VERIFY_RAISES_ASSERT(qr.signDeterminant()) | |
| } | |
| template <typename MatrixType> | |
| void cod_verify_assert() { | |
| MatrixType tmp; | |
| CompleteOrthogonalDecomposition<MatrixType> cod; | |
| VERIFY_RAISES_ASSERT(cod.matrixQTZ()) | |
| VERIFY_RAISES_ASSERT(cod.solve(tmp)) | |
| VERIFY_RAISES_ASSERT(cod.transpose().solve(tmp)) | |
| VERIFY_RAISES_ASSERT(cod.adjoint().solve(tmp)) | |
| VERIFY_RAISES_ASSERT(cod.householderQ()) | |
| VERIFY_RAISES_ASSERT(cod.dimensionOfKernel()) | |
| VERIFY_RAISES_ASSERT(cod.isInjective()) | |
| VERIFY_RAISES_ASSERT(cod.isSurjective()) | |
| VERIFY_RAISES_ASSERT(cod.isInvertible()) | |
| VERIFY_RAISES_ASSERT(cod.pseudoInverse()) | |
| VERIFY_RAISES_ASSERT(cod.determinant()) | |
| VERIFY_RAISES_ASSERT(cod.absDeterminant()) | |
| VERIFY_RAISES_ASSERT(cod.logAbsDeterminant()) | |
| VERIFY_RAISES_ASSERT(cod.signDeterminant()) | |
| } | |
| // Stress test: verify rank detection on partial isometries (SVs = 0 or 1) across | |
| // many random trials and various aspect ratios (square, tall, wide). | |
| // This tests ROBUSTNESS: the threshold must be large enough that roundoff noise | |
| // in the null-space R diagonal elements does not cause rank overestimation. | |
| template <typename MatrixType> | |
| void qr_rank_detection_stress() { | |
| // Test a range of matrix sizes and aspect ratios. | |
| const Index sizes[][2] = {{10, 10}, {20, 20}, {50, 50}, {100, 100}, {40, 10}, {100, 10}, {10, 40}, {10, 100}}; | |
| for (const auto& sz : sizes) { | |
| const Index rows = sz[0], cols = sz[1]; | |
| const Index min_dim = (std::min)(rows, cols); | |
| // Test several rank values: 1, half, and min_dim - 1. | |
| for (Index rank : {Index(1), (std::max)(Index(1), min_dim / 2), min_dim - 1}) { | |
| if (rank >= min_dim) continue; | |
| for (int trial = 0; trial < 20; ++trial) { | |
| MatrixType m1; | |
| createRandomPIMatrixOfRank(rank, rows, cols, m1); | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| VERIFY_IS_EQUAL(rank, qr.rank()); | |
| } | |
| } | |
| } | |
| } | |
| // Efficiency test: verify the threshold is not so large that it causes false | |
| // rank deficiency. Creates matrices with smallest singular value well above | |
| // the backward error bound, and verifies they are detected as full rank. | |
| template <typename MatrixType> | |
| void qr_threshold_efficiency() { | |
| using RealScalar = typename MatrixType::RealScalar; | |
| using RealVectorType = Matrix<RealScalar, Dynamic, 1>; | |
| const Index sizes[][2] = {{10, 10}, {50, 50}, {100, 100}, {40, 10}, {10, 40}}; | |
| for (const auto& sz : sizes) { | |
| const Index rows = sz[0], cols = sz[1]; | |
| const Index min_dim = (std::min)(rows, cols); | |
| // Create a matrix with prescribed singular values: smallest SV = 100 * threshold. | |
| // The threshold is 4*min(m,n)*eps, so we set sigma_min = 400*min(m,n)*eps. | |
| // This must be detected as full rank. | |
| RealScalar sigma_min = RealScalar(400) * RealScalar(min_dim) * NumTraits<RealScalar>::epsilon(); | |
| RealVectorType svs = setupRangeSvs<RealVectorType>(min_dim, sigma_min, RealScalar(1)); | |
| MatrixType m1; | |
| generateRandomMatrixSvs(svs, rows, cols, m1); | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| // sigma_min is 100x the threshold — must be detected as full rank. | |
| VERIFY_IS_EQUAL(min_dim, qr.rank()); | |
| // Also check with FullPivHouseholderQR. | |
| FullPivHouseholderQR<MatrixType> fpqr(m1); | |
| VERIFY_IS_EQUAL(min_dim, fpqr.rank()); | |
| } | |
| } | |
| // Test rank detection on matrices with geometrically distributed singular values | |
| // and a clear gap at the desired rank. This mimics real-world matrices better | |
| // than partial isometries and stresses the threshold from both sides. | |
| template <typename MatrixType> | |
| void qr_rank_gap_test() { | |
| using RealScalar = typename MatrixType::RealScalar; | |
| using RealVectorType = Matrix<RealScalar, Dynamic, 1>; | |
| const Index sizes[][2] = {{20, 20}, {50, 50}, {100, 100}, {50, 20}, {20, 50}}; | |
| for (const auto& sz : sizes) { | |
| const Index rows = sz[0], cols = sz[1]; | |
| const Index min_dim = (std::min)(rows, cols); | |
| const Index rank = (std::max)(Index(1), min_dim / 2); | |
| // Singular values: [1, ..., sigma_rank] for the "signal" part, | |
| // then [eps_level, ..., eps_level] for the "noise" part. | |
| // The gap ratio is sigma_rank / eps_level >> 1. | |
| RealScalar sigma_rank = RealScalar(0.1); | |
| RealScalar eps_level = NumTraits<RealScalar>::epsilon(); | |
| RealVectorType svs(min_dim); | |
| // Signal part: geometrically spaced from 1 to sigma_rank. | |
| for (Index i = 0; i < rank; ++i) { | |
| RealScalar t = (rank > 1) ? RealScalar(i) / RealScalar(rank - 1) : RealScalar(0); | |
| svs(i) = std::pow(sigma_rank, t); // svs(0) = 1, svs(rank-1) = sigma_rank | |
| } | |
| // Noise part: near machine epsilon (well below any reasonable threshold). | |
| for (Index i = rank; i < min_dim; ++i) { | |
| svs(i) = eps_level * RealScalar(min_dim - i); | |
| } | |
| MatrixType m1; | |
| generateRandomMatrixSvs(svs, rows, cols, m1); | |
| ColPivHouseholderQR<MatrixType> qr(m1); | |
| VERIFY_IS_EQUAL(rank, qr.rank()); | |
| FullPivHouseholderQR<MatrixType> fpqr(m1); | |
| VERIFY_IS_EQUAL(rank, fpqr.rank()); | |
| } | |
| } | |
| // Regression: a matrix without columns has no column norm to take the maximum of. | |
| template <typename MatrixType> | |
| void qr_empty() { | |
| ColPivHouseholderQR<MatrixType> qr{MatrixType(3, 0)}; | |
| VERIFY_IS_EQUAL(qr.rank(), Index(0)); | |
| qr.compute(MatrixType(0, 0)); | |
| VERIFY_IS_EQUAL(qr.rank(), Index(0)); | |
| CompleteOrthogonalDecomposition<MatrixType> cod{MatrixType(3, 0)}; | |
| VERIFY_IS_EQUAL(cod.rank(), Index(0)); | |
| } | |
| // Column norms and the rank threshold must not square the entries: pivoting and rank detection have to work for entries | |
| // whose squares overflow or underflow. | |
| template <typename MatrixType> | |
| void qr_configure_blocking(ColPivHouseholderQR<MatrixType>&) {} | |
| template <typename QRType> | |
| void qr_configure_blocking(QRType&) {} | |
| template <typename MatrixType> | |
| void qr_configure_blocking(RandColPivHouseholderQR<MatrixType>& qr) { | |
| qr.setBlockSize(4).setSeed(0x5ca1e); | |
| } | |
| template <typename QRType> | |
| void qr_extreme_scale() { | |
| using MatrixType = typename QRType::MatrixType; | |
| using Scalar = typename MatrixType::Scalar; | |
| using VectorType = Matrix<Scalar, Dynamic, 1>; | |
| const Scalar eps = NumTraits<Scalar>::epsilon(); | |
| const Scalar big = numext::pow((std::numeric_limits<Scalar>::max)(), Scalar(0.55)); | |
| for (const Scalar scale : {big, Scalar(1) / big}) { | |
| // Rank one: only the largest column, the second one, can be a pivot. | |
| VectorType u(6), v(4); | |
| u << 1, 2, -1, Scalar(0.5), 3, -2; | |
| v << Scalar(0.5), -2, 1, Scalar(0.25); | |
| MatrixType A = u * v.transpose(); | |
| A *= scale; | |
| QRType qr; | |
| qr_configure_blocking(qr); | |
| qr.compute(A); | |
| VERIFY_IS_EQUAL(qr.rank(), Index(1)); | |
| VERIFY_IS_EQUAL(qr.nonzeroPivots(), Index(1)); | |
| VERIFY_IS_EQUAL(qr.colsPermutation().indices()(0), 1); | |
| VERIFY((A * qr.solve(u) - u).stableNorm() <= Scalar(64) * eps * u.stableNorm()); | |
| // Rank 12 in a size for which the randomized QR takes its blocked path. | |
| MatrixType B = MatrixType::Random(60, 12) * MatrixType::Random(12, 40); | |
| B *= scale; | |
| QRType qr2; | |
| qr_configure_blocking(qr2); | |
| qr2.compute(B); | |
| VERIFY_IS_EQUAL(qr2.rank(), Index(12)); | |
| const MatrixType R = qr2.matrixR().template triangularView<Upper>(); | |
| VERIFY((qr2.householderQ() * R - B * qr2.colsPermutation()).stableNorm() <= Scalar(1024) * eps * B.stableNorm()); | |
| } | |
| } | |
| // Entries uniform in [-1, 1) from a linear congruential generator, so that the matrices of qr_flush_band are the same | |
| // on every platform and for every seed of the test. | |
| template <typename Scalar> | |
| Scalar qr_lcg_scalar(typename NumTraits<Scalar>::Real re, typename NumTraits<Scalar>::Real, std::false_type) { | |
| return Scalar(re); | |
| } | |
| template <typename Scalar> | |
| Scalar qr_lcg_scalar(typename NumTraits<Scalar>::Real re, typename NumTraits<Scalar>::Real im, std::true_type) { | |
| return Scalar(re, im); | |
| } | |
| template <typename MatrixType> | |
| MatrixType qr_lcg_matrix(Index rows, Index cols, uint32_t& state) { | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| const auto next = [&state]() { | |
| state = state * 1664525u + 1013904223u; | |
| return RealScalar((state >> 8) & 0xffff) / RealScalar(32768) - RealScalar(1); | |
| }; | |
| MatrixType m(rows, cols); | |
| for (Index j = 0; j < cols; ++j) | |
| for (Index i = 0; i < rows; ++i) { | |
| const RealScalar re = next(); | |
| const RealScalar im = next(); | |
| m(i, j) = qr_lcg_scalar<Scalar>(re, im, internal::bool_constant<NumTraits<Scalar>::IsComplex>()); | |
| } | |
| return m; | |
| } | |
| // Rank detection compares residual column norms with eps * maxnorm. For maxnorm a few 1e4 times sqrt(min) the squares | |
| // of the entries of the residual of the last pivot are subnormal: the rank must not drop, whether or not subnormals are | |
| // flushed to zero. A has rank 7 plus a perturbation of relative size 1e-4, which is above the default threshold; the | |
| // cancellation in the first seven steps makes the factorization recompute the column norms. | |
| template <typename QRType, bool Blocked> | |
| void qr_flush_band() { | |
| using MatrixType = typename QRType::MatrixType; | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| const Index rows = 40, rank = 7, cols = 8; | |
| uint32_t state = 3u * 7919u; | |
| // The factors are generated one after the other: the evaluation order of the operands of a product is unspecified. | |
| const MatrixType B1 = qr_lcg_matrix<MatrixType>(rows, rank, state); | |
| const MatrixType B2 = qr_lcg_matrix<MatrixType>(rank, cols, state); | |
| const MatrixType C1 = qr_lcg_matrix<MatrixType>(rows, 1, state); | |
| const MatrixType C2 = qr_lcg_matrix<MatrixType>(1, cols, state); | |
| const MatrixType B = B1 * B2; | |
| const MatrixType C = C1 * C2; | |
| const MatrixType A = B + Scalar(RealScalar(1e-4)) * C; | |
| const RealScalar maxnorm = A.colwise().norm().maxCoeff(); | |
| for (const RealScalar factor : {RealScalar(2e4), RealScalar(3e4), RealScalar(4.5e4)}) { | |
| const MatrixType scaled = A * Scalar(factor * numext::sqrt((std::numeric_limits<RealScalar>::min)()) / maxnorm); | |
| for (const FlushToZeroMode mode : {FlushToZeroMode::None, FlushToZeroMode::Both}) { | |
| ScopedFlushToZero flush(mode); | |
| QRType qr; | |
| EIGEN_IF_CONSTEXPR (Blocked) qr_configure_blocking(qr); | |
| qr.compute(scaled); | |
| VERIFY_IS_EQUAL(qr.rank(), cols); | |
| } | |
| } | |
| } | |
| template <typename MatrixType> | |
| void cod_extreme_scale() { | |
| using Scalar = typename MatrixType::Scalar; | |
| const Scalar eps = NumTraits<Scalar>::epsilon(); | |
| const Scalar big = numext::pow((std::numeric_limits<Scalar>::max)(), Scalar(0.55)); | |
| for (const Scalar scale : {big, Scalar(1) / big}) { | |
| MatrixType A = MatrixType::Random(6, 2) * MatrixType::Random(2, 4); | |
| A *= scale; | |
| const MatrixType b = A * MatrixType::Ones(4, 1); | |
| CompleteOrthogonalDecomposition<MatrixType> cod(A); | |
| VERIFY_IS_EQUAL(cod.rank(), Index(2)); | |
| VERIFY((A * cod.solve(b) - b).stableNorm() <= Scalar(256) * eps * b.stableNorm()); | |
| } | |
| } | |
| // The rank, and with it the Z reflectors, of a complete orthogonal decomposition are fixed by compute(): a threshold | |
| // set afterwards applies to the next compute() and leaves the decomposition and its solutions unchanged. | |
| template <typename MatrixType> | |
| void cod_set_threshold_after_compute() { | |
| using Scalar = typename MatrixType::Scalar; | |
| using RealScalar = typename MatrixType::RealScalar; | |
| const Index rows = 8, cols = 6; | |
| MatrixType A = MatrixType::Random(rows, cols); | |
| A.col(cols - 1) = A.col(0) + Scalar(RealScalar(1e-6)) * MatrixType::Random(rows, 1); | |
| const MatrixType b = MatrixType::Random(rows, 2); | |
| CompleteOrthogonalDecomposition<MatrixType> cod(A); | |
| VERIFY_IS_EQUAL(cod.rank(), cols); | |
| const MatrixType x_full = cod.solve(b); | |
| cod.setThreshold(RealScalar(1e-4)); | |
| VERIFY_IS_EQUAL(cod.rank(), cols); | |
| VERIFY_IS_APPROX(cod.solve(b), x_full); | |
| VERIFY(cod.matrixZ().isUnitary()); | |
| cod.compute(A); | |
| VERIFY_IS_EQUAL(cod.rank(), cols - 1); | |
| CompleteOrthogonalDecomposition<MatrixType> reference; | |
| reference.setThreshold(RealScalar(1e-4)); | |
| reference.compute(A); | |
| VERIFY_IS_EQUAL(reference.rank(), cols - 1); | |
| const MatrixType x_deficient = cod.solve(b); | |
| VERIFY_IS_APPROX(x_deficient, reference.solve(b)); | |
| VERIFY(cod.matrixZ().isUnitary()); | |
| // Going back to the default threshold does not change a decomposition that has already been computed either. | |
| cod.setThreshold(Default); | |
| VERIFY_IS_EQUAL(cod.rank(), cols - 1); | |
| VERIFY_IS_APPROX(cod.solve(b), x_deficient); | |
| VERIFY_IS_EQUAL(cod.dimensionOfKernel(), Index(1)); | |
| VERIFY(!cod.isInjective()); | |
| } | |
| // A right-hand side without columns, and an empty matrix, give an empty solution of the right size; sanitizer builds | |
| // reported a reference to the first element of an empty workspace. | |
| template <typename Decomposition, typename MatrixType> | |
| void qr_empty_rhs() { | |
| const MatrixType A = MatrixType::Random(4, 4); | |
| const Decomposition dec(A); | |
| const MatrixType empty_rhs(4, 0); | |
| VERIFY_IS_EQUAL(dec.solve(empty_rhs).rows(), 4); | |
| VERIFY_IS_EQUAL(dec.solve(empty_rhs).cols(), 0); | |
| VERIFY_IS_EQUAL(dec.transpose().solve(empty_rhs).rows(), 4); | |
| VERIFY_IS_EQUAL(dec.transpose().solve(empty_rhs).cols(), 0); | |
| VERIFY_IS_EQUAL(dec.adjoint().solve(empty_rhs).cols(), 0); | |
| const MatrixType B = MatrixType::Random(4, 3); | |
| const MatrixType X = dec.solve(B); | |
| VERIFY_IS_EQUAL(X.cols(), 3); | |
| VERIFY_IS_APPROX(A * X, B); | |
| const Decomposition empty_dec{MatrixType(0, 0)}; | |
| VERIFY_IS_EQUAL(empty_dec.solve(MatrixType(0, 2)).rows(), 0); | |
| VERIFY_IS_EQUAL(empty_dec.solve(MatrixType(0, 2)).cols(), 2); | |
| VERIFY_IS_EQUAL(empty_dec.transpose().solve(MatrixType(0, 0)).cols(), 0); | |
| } | |
| EIGEN_DECLARE_TEST(qr_colpivoting) { | |
| for (int i = 0; i < g_repeat; i++) { | |
| CALL_SUBTEST_1(qr<MatrixXf>()); | |
| CALL_SUBTEST_2(qr<MatrixXd>()); | |
| CALL_SUBTEST_3(qr<MatrixXcd>()); | |
| CALL_SUBTEST_10((qr<Matrix<double, Dynamic, Dynamic, RowMajor>>())); | |
| CALL_SUBTEST_11((qr<Matrix<std::complex<double>, Dynamic, Dynamic, RowMajor>>())); | |
| CALL_SUBTEST_4((qr_fixedsize<Matrix<float, 3, 5>, 4>())); | |
| CALL_SUBTEST_5((qr_fixedsize<Matrix<double, 6, 2>, 3>())); | |
| CALL_SUBTEST_5((qr_fixedsize<Matrix<double, 1, 1>, 1>())); | |
| } | |
| for (int i = 0; i < g_repeat; i++) { | |
| CALL_SUBTEST_1(cod<MatrixXf>()); | |
| CALL_SUBTEST_2(cod<MatrixXd>()); | |
| CALL_SUBTEST_3(cod<MatrixXcd>()); | |
| CALL_SUBTEST_4((cod_fixedsize<Matrix<float, 3, 5>, 4>())); | |
| CALL_SUBTEST_5((cod_fixedsize<Matrix<double, 6, 2>, 3>())); | |
| CALL_SUBTEST_5((cod_fixedsize<Matrix<double, 1, 1>, 1>())); | |
| } | |
| for (int i = 0; i < g_repeat; i++) { | |
| CALL_SUBTEST_1(qr_invertible<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_invertible<MatrixXd>()); | |
| CALL_SUBTEST_6(qr_invertible<MatrixXcf>()); | |
| CALL_SUBTEST_3(qr_invertible<MatrixXcd>()); | |
| } | |
| CALL_SUBTEST_7(qr_verify_assert<Matrix3f>()); | |
| CALL_SUBTEST_8(qr_verify_assert<Matrix3d>()); | |
| CALL_SUBTEST_1(qr_verify_assert<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_verify_assert<MatrixXd>()); | |
| CALL_SUBTEST_6(qr_verify_assert<MatrixXcf>()); | |
| CALL_SUBTEST_3(qr_verify_assert<MatrixXcd>()); | |
| CALL_SUBTEST_7(cod_verify_assert<Matrix3f>()); | |
| CALL_SUBTEST_8(cod_verify_assert<Matrix3d>()); | |
| CALL_SUBTEST_1(cod_verify_assert<MatrixXf>()); | |
| CALL_SUBTEST_2(cod_verify_assert<MatrixXd>()); | |
| CALL_SUBTEST_6(cod_verify_assert<MatrixXcf>()); | |
| CALL_SUBTEST_3(cod_verify_assert<MatrixXcd>()); | |
| // Test problem size constructors | |
| CALL_SUBTEST_9(ColPivHouseholderQR<MatrixXf>(10, 20)); | |
| CALL_SUBTEST_2(qr_empty<MatrixXd>()); | |
| CALL_SUBTEST_2((qr_empty_rhs<ColPivHouseholderQR<MatrixXd>, MatrixXd>())); | |
| CALL_SUBTEST_2((qr_empty_rhs<CompleteOrthogonalDecomposition<MatrixXd>, MatrixXd>())); | |
| CALL_SUBTEST_3((qr_empty_rhs<ColPivHouseholderQR<MatrixXcd>, MatrixXcd>())); | |
| CALL_SUBTEST_3((qr_empty_rhs<CompleteOrthogonalDecomposition<MatrixXcd>, MatrixXcd>())); | |
| CALL_SUBTEST_2((qr_empty_rhs<RandColPivHouseholderQR<MatrixXd>, MatrixXd>())); | |
| CALL_SUBTEST_1((qr_extreme_scale<ColPivHouseholderQR<MatrixXf>>())); | |
| CALL_SUBTEST_2((qr_extreme_scale<ColPivHouseholderQR<MatrixXd>>())); | |
| CALL_SUBTEST_1((qr_extreme_scale<RandColPivHouseholderQR<MatrixXf>>())); | |
| CALL_SUBTEST_2((qr_extreme_scale<RandColPivHouseholderQR<MatrixXd>>())); | |
| CALL_SUBTEST_1((qr_flush_band<ColPivHouseholderQR<MatrixXf>, false>())); | |
| CALL_SUBTEST_2((qr_flush_band<ColPivHouseholderQR<MatrixXd>, false>())); | |
| CALL_SUBTEST_1((qr_flush_band<RandColPivHouseholderQR<MatrixXf>, false>())); | |
| CALL_SUBTEST_1((qr_flush_band<RandColPivHouseholderQR<MatrixXf>, true>())); | |
| CALL_SUBTEST_2((qr_flush_band<RandColPivHouseholderQR<MatrixXd>, true>())); | |
| CALL_SUBTEST_1((qr_flush_band<CompleteOrthogonalDecomposition<MatrixXf>, false>())); | |
| CALL_SUBTEST_2((qr_flush_band<CompleteOrthogonalDecomposition<MatrixXd>, false>())); | |
| CALL_SUBTEST_3((qr_flush_band<ColPivHouseholderQR<MatrixXcf>, false>())); | |
| CALL_SUBTEST_10((qr_flush_band<ColPivHouseholderQR<Matrix<float, Dynamic, Dynamic, RowMajor>>, false>())); | |
| CALL_SUBTEST_10((qr_flush_band<RandColPivHouseholderQR<Matrix<float, Dynamic, Dynamic, RowMajor>>, true>())); | |
| CALL_SUBTEST_1(cod_extreme_scale<MatrixXf>()); | |
| CALL_SUBTEST_2(cod_extreme_scale<MatrixXd>()); | |
| CALL_SUBTEST_2(cod_set_threshold_after_compute<MatrixXd>()); | |
| CALL_SUBTEST_3(cod_set_threshold_after_compute<MatrixXcd>()); | |
| CALL_SUBTEST_1(qr_kahan_matrix<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_kahan_matrix<MatrixXd>()); | |
| // Stress tests for rank detection threshold robustness and efficiency. | |
| CALL_SUBTEST_1(qr_rank_detection_stress<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_rank_detection_stress<MatrixXd>()); | |
| CALL_SUBTEST_1(qr_threshold_efficiency<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_threshold_efficiency<MatrixXd>()); | |
| CALL_SUBTEST_1(qr_rank_gap_test<MatrixXf>()); | |
| CALL_SUBTEST_2(qr_rank_gap_test<MatrixXd>()); | |
| } |