12#ifndef EIGEN_COLPIVOTINGHOUSEHOLDERQR_H
13#define EIGEN_COLPIVOTINGHOUSEHOLDERQR_H
16#include "./InternalHeaderCheck.h"
21template <
typename MatrixType_,
typename PermutationIndex_>
22struct traits<ColPivHouseholderQR<MatrixType_, PermutationIndex_>> : traits<MatrixType_> {
23 using XprKind = MatrixXpr;
24 using StorageKind = SolverStorage;
25 using PermutationIndex = PermutationIndex_;
54template <
typename MatrixType_,
typename PermutationIndex_>
56 public RankRevealingBase<ColPivHouseholderQR<MatrixType_, PermutationIndex_>> {
58 using MatrixType = MatrixType_;
60 using RankRevealingBase_ = RankRevealingBase<ColPivHouseholderQR>;
72 using PermutationIndex = PermutationIndex_;
76 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
77 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
79 using HCoeffsType =
typename internal::plain_diag_type<MatrixType>::type;
81 using IntRowVectorType =
typename internal::plain_row_type<MatrixType, PermutationIndex>::type;
82 using RowVectorType =
typename internal::plain_row_type<MatrixType>::type;
83 using RealRowVectorType =
typename internal::plain_row_type<MatrixType, RealScalar>::type;
84 using HouseholderSequenceType =
86 using PlainObject =
typename MatrixType::PlainObject;
89 void init(Index rows, Index cols) {
90 Index diag = numext::mini(rows, cols);
91 m_hCoeffs.resize(diag);
92 m_colsPermutation.resize(cols);
93 m_colsTranspositions.resize(cols);
95 m_colNormsUpdated.resize(cols);
96 m_colNormsDirect.resize(cols);
97 m_isInitialized =
false;
111 m_colsTranspositions(),
115 m_isInitialized(false) {}
137 template <
typename InputType>
150 template <
typename InputType>
156#ifdef EIGEN_PARSED_BY_DOXYGEN
171 template <
typename Rhs>
176 HouseholderSequenceType matrixQ()
const {
return householderQ(); }
181 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
195 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
199 template <
typename InputType>
204 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
205 return m_colsPermutation;
275 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
279 inline Index rows()
const {
return m_qr.rows(); }
280 inline Index cols()
const {
return m_qr.cols(); }
286 const HCoeffsType&
hCoeffs()
const {
return m_hCoeffs; }
295 eigen_assert(m_isInitialized &&
"Decomposition is not initialized.");
299#ifndef EIGEN_PARSED_BY_DOXYGEN
300 template <
typename RhsType,
typename DstType>
301 void _solve_impl(
const RhsType& rhs, DstType& dst)
const;
303 template <
bool Conjugate,
typename RhsType,
typename DstType>
304 void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const;
308 friend class internal::CompleteOrthogonalDecompositionImpl<MatrixType, PermutationIndex,
ColPivHouseholderQR>;
310 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
312 void computeInPlace();
313 void computeInPlaceNative();
316 HCoeffsType m_hCoeffs;
317 PermutationType m_colsPermutation;
318 IntRowVectorType m_colsTranspositions;
319 RowVectorType m_temp;
320 RealRowVectorType m_colNormsUpdated;
321 RealRowVectorType m_colNormsDirect;
322 bool m_isInitialized;
326template <
typename MatrixType,
typename PermutationIndex>
328 eigen_assert(m_isInitialized &&
"HouseholderQR is not initialized.");
329 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr,
"You can't take the determinant of a non-square matrix!");
331 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
332 return isInjective() ? (detQ * Scalar(m_det_p)) * internal::scaled_prod(m_qr.diagonal()).value() : Scalar(0);
335template <
typename MatrixType,
typename PermutationIndex>
337 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
338 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr,
"You can't take the determinant of a non-square matrix!");
339 return isInjective() ? internal::scaled_prod(m_qr.diagonal()).abs() : RealScalar(0);
342template <
typename MatrixType,
typename PermutationIndex>
344 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
345 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr,
"You can't take the determinant of a non-square matrix!");
346 return isInjective() ? internal::log_abs_prod(m_qr.diagonal()) : -NumTraits<RealScalar>::infinity();
349template <
typename MatrixType,
typename PermutationIndex>
351 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
352 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr,
"You can't take the determinant of a non-square matrix!");
354 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
355 return isInjective() ? (detQ * Scalar(m_det_p)) * m_qr.diagonal().array().sign().prod() : Scalar(0);
364template <
typename MatrixType,
typename PermutationIndex>
365template <
typename InputType>
368 m_qr.resize(matrix.
rows(), matrix.
cols());
374template <
typename MatrixType,
typename PermutationIndex>
375void ColPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlace() {
376 computeInPlaceNative();
379template <
typename MatrixType,
typename PermutationIndex>
380void ColPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlaceNative() {
381 eigen_assert(m_qr.cols() <= NumTraits<PermutationIndex>::highest());
383 Index rows = m_qr.rows();
384 Index cols = m_qr.cols();
385 Index size = m_qr.diagonalSize();
387 m_hCoeffs.resize(size);
391 m_colsTranspositions.resize(m_qr.cols());
392 Index number_of_transpositions = 0;
395 m_colNormsDirect.resize(cols);
396 m_colNormsUpdated.resize(cols);
397 const bool stable_norms = internal::column_norms_with_fallback(m_qr, m_colNormsDirect);
398 m_colNormsUpdated = m_colNormsDirect;
402 RealScalar threshold_helper =
403 cols == 0 ? RealScalar(0)
404 : m_colNormsUpdated.maxCoeff() * NumTraits<RealScalar>::epsilon() / numext::sqrt(RealScalar(rows));
405 RealScalar norm_downdate_threshold = numext::sqrt(NumTraits<RealScalar>::epsilon());
407 this->m_nonzero_pivots = size;
408 this->m_maxpivot = RealScalar(0);
410 for (Index k = 0; k < size; ++k) {
412 Index biggest_col_index;
413 RealScalar biggest_col_norm = m_colNormsUpdated.tail(cols - k).maxCoeff(&biggest_col_index);
414 biggest_col_index += k;
418 if (this->m_nonzero_pivots == size && biggest_col_norm < threshold_helper * numext::sqrt(RealScalar(rows - k)))
419 this->m_nonzero_pivots = k;
422 m_colsTranspositions.coeffRef(k) =
static_cast<PermutationIndex
>(biggest_col_index);
423 if (k != biggest_col_index) {
424 m_qr.col(k).swap(m_qr.col(biggest_col_index));
425 std::swap(m_colNormsUpdated.coeffRef(k), m_colNormsUpdated.coeffRef(biggest_col_index));
426 std::swap(m_colNormsDirect.coeffRef(k), m_colNormsDirect.coeffRef(biggest_col_index));
427 ++number_of_transpositions;
432 m_qr.col(k).tail(rows - k).makeHouseholderInPlace(m_hCoeffs.coeffRef(k), beta);
435 m_qr.coeffRef(k, k) = beta;
438 if (numext::abs(beta) > this->m_maxpivot) this->m_maxpivot = numext::abs(beta);
441 m_qr.bottomRightCorner(rows - k, cols - k - 1)
442 .applyHouseholderOnTheLeft(m_qr.col(k).tail(rows - k - 1), m_hCoeffs.coeffRef(k), &m_temp.coeffRef(k + 1));
445 for (Index j = k + 1; j < cols; ++j) {
450 if (!numext::is_exactly_zero(m_colNormsUpdated.coeffRef(j))) {
451 RealScalar temp = numext::abs(m_qr.coeffRef(k, j)) / m_colNormsUpdated.coeffRef(j);
452 temp = (RealScalar(1) + temp) * (RealScalar(1) - temp);
453 temp = temp < RealScalar(0) ? RealScalar(0) : temp;
455 temp * numext::abs2<RealScalar>(m_colNormsUpdated.coeffRef(j) / m_colNormsDirect.coeffRef(j));
456 if (temp2 <= norm_downdate_threshold) {
459 m_colNormsDirect.coeffRef(j) =
460 stable_norms ? m_qr.col(j).tail(rows - k - 1).stableNorm() : m_qr.col(j).tail(rows - k - 1).norm();
461 m_colNormsUpdated.coeffRef(j) = m_colNormsDirect.coeffRef(j);
463 m_colNormsUpdated.coeffRef(j) *= numext::sqrt(temp);
469 m_colsPermutation.setIdentity(cols);
470 for (Index k = 0; k < size; ++k)
471 m_colsPermutation.applyTranspositionOnTheRight(k,
static_cast<Index
>(m_colsTranspositions.coeff(k)));
473 m_det_p = (number_of_transpositions % 2) ? -1 : 1;
474 m_isInitialized =
true;
477#ifndef EIGEN_PARSED_BY_DOXYGEN
478template <
typename MatrixType_,
typename PermutationIndex_>
479template <
typename RhsType,
typename DstType>
481 const Index nonzero_pivots = nonzeroPivots();
483 if (nonzero_pivots == 0) {
488 typename RhsType::PlainObject c(rhs);
490 c.applyOnTheLeft(householderQ().setLength(nonzero_pivots).adjoint());
492 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
493 .template triangularView<Upper>()
494 .solveInPlace(c.topRows(nonzero_pivots));
496 for (Index i = 0; i < nonzero_pivots; ++i) dst.row(m_colsPermutation.indices().coeff(i)) = c.row(i);
497 for (Index i = nonzero_pivots; i < cols(); ++i) dst.row(m_colsPermutation.indices().coeff(i)).setZero();
500template <
typename MatrixType_,
typename PermutationIndex_>
501template <
bool Conjugate,
typename RhsType,
typename DstType>
503 DstType& dst)
const {
504 const Index nonzero_pivots = nonzeroPivots();
506 if (nonzero_pivots == 0) {
511 typename RhsType::PlainObject c(m_colsPermutation.transpose() * rhs);
513 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
514 .template triangularView<Upper>()
516 .template conjugateIf<Conjugate>()
517 .solveInPlace(c.topRows(nonzero_pivots));
519 dst.topRows(nonzero_pivots) = c.topRows(nonzero_pivots);
520 dst.bottomRows(rows() - nonzero_pivots).setZero();
522 dst.applyOnTheLeft(householderQ().setLength(nonzero_pivots).
template conjugateIf<!Conjugate>());
528template <
typename DstXprType,
typename MatrixType,
typename PermutationIndex>
529struct Assignment<DstXprType, Inverse<ColPivHouseholderQR<MatrixType, PermutationIndex>>,
530 internal::assign_op<typename DstXprType::Scalar,
531 typename ColPivHouseholderQR<MatrixType, PermutationIndex>::Scalar>,
533 using QrType = ColPivHouseholderQR<MatrixType, PermutationIndex>;
534 using SrcXprType = Inverse<QrType>;
535 static void run(DstXprType& dst,
const SrcXprType& src,
536 const internal::assign_op<typename DstXprType::Scalar, typename QrType::Scalar>&) {
537 dst = src.nestedExpression().solve(MatrixType::Identity(src.rows(), src.cols()));
546template <
typename MatrixType,
typename PermutationIndex>
547typename ColPivHouseholderQR<MatrixType, PermutationIndex>::HouseholderSequenceType
549 eigen_assert(m_isInitialized &&
"ColPivHouseholderQR is not initialized.");
550 return HouseholderSequenceType(m_qr, m_hCoeffs.conjugate());
557template <
typename Derived>
558template <
typename PermutationIndexType>
560MatrixBase<Derived>::colPivHouseholderQr()
const {
Householder rank-revealing QR decomposition of a matrix with column-pivoting.
Definition ColPivHouseholderQR.h:56
Solve< ColPivHouseholderQR, Rhs > solve(const MatrixBase< Rhs > &b) const
RealScalar pivotCoeff(Index i) const
Definition ColPivHouseholderQR.h:267
const HCoeffsType & hCoeffs() const
Definition ColPivHouseholderQR.h:286
MatrixType::Scalar signDeterminant() const
Definition ColPivHouseholderQR.h:350
MatrixType::RealScalar absDeterminant() const
Definition ColPivHouseholderQR.h:336
ColPivHouseholderQR(EigenBase< InputType > &matrix)
Constructs a QR factorization from a given matrix.
Definition ColPivHouseholderQR.h:151
bool isInjective() const
Definition RankRevealingBase.h:151
const PermutationType & colsPermutation() const
Definition ColPivHouseholderQR.h:203
const MatrixType & matrixQR() const
Definition ColPivHouseholderQR.h:180
ComputationInfo info() const
Reports whether the QR factorization was successful.
Definition ColPivHouseholderQR.h:294
ColPivHouseholderQR()
Default Constructor.
Definition ColPivHouseholderQR.h:107
HouseholderSequenceType householderQ() const
Definition ColPivHouseholderQR.h:548
MatrixType::Scalar determinant() const
Definition ColPivHouseholderQR.h:327
MatrixType::RealScalar logAbsDeterminant() const
Definition ColPivHouseholderQR.h:343
ColPivHouseholderQR(Index rows, Index cols)
Default Constructor with memory preallocation.
Definition ColPivHouseholderQR.h:123
const MatrixType & matrixR() const
Definition ColPivHouseholderQR.h:194
Inverse< ColPivHouseholderQR > inverse() const
Definition ColPivHouseholderQR.h:274
ColPivHouseholderQR(const EigenBase< InputType > &matrix)
Constructs a QR factorization from a given matrix.
Definition ColPivHouseholderQR.h:138
EvalReturnType eval() const
Definition DenseBase.h:389
Sequence of Householder reflections acting on subspaces with decreasing size.
Definition HouseholderSequence.h:155
Expression of the inverse of another expression.
Definition Inverse.h:44
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
Permutation matrix.
Definition PermutationMatrix.h:346
Index dimensionOfKernel() const
Definition RankRevealingBase.h:139
bool isInjective() const
Definition RankRevealingBase.h:151
bool isSurjective() const
Definition RankRevealingBase.h:163
ColPivHouseholderQR & setThreshold(const RealScalar &threshold)
Definition RankRevealingBase.h:87
Index nonzeroPivots() const
Definition RankRevealingBase.h:186
RealScalar threshold() const
Definition RankRevealingBase.h:110
RealScalar maxPivot() const
Definition RankRevealingBase.h:194
Index rank() const
Definition RankRevealingBase.h:125
bool isInvertible() const
Definition RankRevealingBase.h:174
Pseudo expression representing a solving operation.
Definition Solve.h:63
constexpr Derived & derived()
Definition EigenBase.h:50
ComputationInfo
Definition Constants.h:455
@ Success
Definition Constants.h:457
Definition EigenBase.h:34
constexpr Index cols() const noexcept
Definition EigenBase.h:62
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index rows() const noexcept
Definition EigenBase.h:60
Eigen::Index Index
The interface type of indices.
Definition EigenBase.h:44