Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ColPivHouseholderQR.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2009 Gael Guennebaud <gael.guennebaud@inria.fr>
5// Copyright (C) 2009 Benoit Jacob <jacob.benoit.1@gmail.com>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_COLPIVOTINGHOUSEHOLDERQR_H
13#define EIGEN_COLPIVOTINGHOUSEHOLDERQR_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21template <typename MatrixType_, typename PermutationIndex_>
22struct traits<ColPivHouseholderQR<MatrixType_, PermutationIndex_>> : traits<MatrixType_> {
23 using XprKind = MatrixXpr;
24 using StorageKind = SolverStorage;
25 using PermutationIndex = PermutationIndex_;
26 enum { Flags = 0 };
27};
28
29} // end namespace internal
30
54template <typename MatrixType_, typename PermutationIndex_>
55class ColPivHouseholderQR : public SolverBase<ColPivHouseholderQR<MatrixType_, PermutationIndex_>>,
56 public RankRevealingBase<ColPivHouseholderQR<MatrixType_, PermutationIndex_>> {
57 public:
58 using MatrixType = MatrixType_;
60 using RankRevealingBase_ = RankRevealingBase<ColPivHouseholderQR>;
61 friend class SolverBase<ColPivHouseholderQR>;
62 friend class RankRevealingBase<ColPivHouseholderQR>;
72 using PermutationIndex = PermutationIndex_;
73 EIGEN_GENERIC_PUBLIC_INTERFACE(ColPivHouseholderQR)
74
75 enum {
76 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
77 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
78 };
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;
87
88 private:
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);
94 m_temp.resize(cols);
95 m_colNormsUpdated.resize(cols);
96 m_colNormsDirect.resize(cols);
97 m_isInitialized = false;
98 }
99
100 public:
108 : m_qr(),
109 m_hCoeffs(),
110 m_colsPermutation(),
111 m_colsTranspositions(),
112 m_temp(),
113 m_colNormsUpdated(),
114 m_colNormsDirect(),
115 m_isInitialized(false) {}
116
123 ColPivHouseholderQR(Index rows, Index cols) : m_qr(rows, cols) { init(rows, cols); }
124
137 template <typename InputType>
138 explicit ColPivHouseholderQR(const EigenBase<InputType>& matrix) : m_qr(matrix.rows(), matrix.cols()) {
139 init(matrix.rows(), matrix.cols());
140 compute(matrix.derived());
141 }
142
150 template <typename InputType>
151 explicit ColPivHouseholderQR(EigenBase<InputType>& matrix) : m_qr(matrix.derived()) {
152 init(matrix.rows(), matrix.cols());
153 computeInPlace();
154 }
155
156#ifdef EIGEN_PARSED_BY_DOXYGEN
171 template <typename Rhs>
173#endif
174
175 HouseholderSequenceType householderQ() const;
176 HouseholderSequenceType matrixQ() const { return householderQ(); }
177
180 const MatrixType& matrixQR() const {
181 eigen_assert(m_isInitialized && "ColPivHouseholderQR is not initialized.");
182 return m_qr;
183 }
184
194 const MatrixType& matrixR() const {
195 eigen_assert(m_isInitialized && "ColPivHouseholderQR is not initialized.");
196 return m_qr;
197 }
198
199 template <typename InputType>
200 ColPivHouseholderQR& compute(const EigenBase<InputType>& matrix);
201
203 const PermutationType& colsPermutation() const {
204 eigen_assert(m_isInitialized && "ColPivHouseholderQR is not initialized.");
205 return m_colsPermutation;
206 }
207
221 typename MatrixType::Scalar determinant() const;
222
236 typename MatrixType::RealScalar absDeterminant() const;
237
250 typename MatrixType::RealScalar logAbsDeterminant() const;
251
264 typename MatrixType::Scalar signDeterminant() const;
265
267 RealScalar pivotCoeff(Index i) const { return numext::abs(m_qr.coeff(i, i)); }
268
275 eigen_assert(m_isInitialized && "ColPivHouseholderQR is not initialized.");
276 return Inverse<ColPivHouseholderQR>(*this);
277 }
278
279 inline Index rows() const { return m_qr.rows(); }
280 inline Index cols() const { return m_qr.cols(); }
281
286 const HCoeffsType& hCoeffs() const { return m_hCoeffs; }
287
295 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
296 return Success;
297 }
298
299#ifndef EIGEN_PARSED_BY_DOXYGEN
300 template <typename RhsType, typename DstType>
301 void _solve_impl(const RhsType& rhs, DstType& dst) const;
302
303 template <bool Conjugate, typename RhsType, typename DstType>
304 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const;
305#endif
306
307 protected:
308 friend class internal::CompleteOrthogonalDecompositionImpl<MatrixType, PermutationIndex, ColPivHouseholderQR>;
309
310 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
311
312 void computeInPlace();
313 void computeInPlaceNative();
314
315 MatrixType m_qr;
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;
323 Index m_det_p = 1;
324};
325
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!");
330 Scalar detQ;
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);
333}
334
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);
340}
341
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();
347}
348
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!");
353 Scalar detQ;
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);
356}
357
364template <typename MatrixType, typename PermutationIndex>
365template <typename InputType>
366ColPivHouseholderQR<MatrixType, PermutationIndex>& ColPivHouseholderQR<MatrixType, PermutationIndex>::compute(
367 const EigenBase<InputType>& matrix) {
368 m_qr.resize(matrix.rows(), matrix.cols());
369 m_qr = matrix.derived();
370 computeInPlace();
371 return *this;
372}
373
374template <typename MatrixType, typename PermutationIndex>
375void ColPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlace() {
376 computeInPlaceNative();
377}
378
379template <typename MatrixType, typename PermutationIndex>
380void ColPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlaceNative() {
381 eigen_assert(m_qr.cols() <= NumTraits<PermutationIndex>::highest());
382
383 Index rows = m_qr.rows();
384 Index cols = m_qr.cols();
385 Index size = m_qr.diagonalSize();
386
387 m_hCoeffs.resize(size);
388
389 m_temp.resize(cols);
390
391 m_colsTranspositions.resize(m_qr.cols());
392 Index number_of_transpositions = 0;
393
394 // m_colNormsDirect caches the most recent directly computed column norms.
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;
399
400 // A column is negligible when its norm is below eps * maxnorm * sqrt((rows - k) / rows). The test is written without
401 // squaring the norms, which overflow or underflow for entries beyond sqrt(max) or below sqrt(min).
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());
406
407 this->m_nonzero_pivots = size; // the generic case is that in which all pivots are nonzero (invertible case)
408 this->m_maxpivot = RealScalar(0);
409
410 for (Index k = 0; k < size; ++k) {
411 // first, we look up in our table m_colNormsUpdated which column has the biggest norm
412 Index biggest_col_index;
413 RealScalar biggest_col_norm = m_colNormsUpdated.tail(cols - k).maxCoeff(&biggest_col_index);
414 biggest_col_index += k;
415
416 // Track the number of meaningful pivots but do not stop the decomposition to make
417 // sure that the initial matrix is properly reproduced. See bug 941.
418 if (this->m_nonzero_pivots == size && biggest_col_norm < threshold_helper * numext::sqrt(RealScalar(rows - k)))
419 this->m_nonzero_pivots = k;
420
421 // apply the transposition to the columns
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;
428 }
429
430 // generate the householder vector, store it below the diagonal
431 RealScalar beta;
432 m_qr.col(k).tail(rows - k).makeHouseholderInPlace(m_hCoeffs.coeffRef(k), beta);
433
434 // apply the householder transformation to the diagonal coefficient
435 m_qr.coeffRef(k, k) = beta;
436
437 // remember the maximum absolute value of diagonal coefficients
438 if (numext::abs(beta) > this->m_maxpivot) this->m_maxpivot = numext::abs(beta);
439
440 // apply the householder transformation
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));
443
444 // update our table of norms of the columns
445 for (Index j = k + 1; j < cols; ++j) {
446 // The following implements the stable norm downgrade step discussed in
447 // http://www.netlib.org/lapack/lawnspdf/lawn176.pdf
448 // and used in LAPACK routines xGEQPF and xGEQP3.
449 // See lines 278-297 in http://www.netlib.org/lapack/explore-html/dc/df4/sgeqpf_8f_source.html
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;
454 RealScalar temp2 =
455 temp * numext::abs2<RealScalar>(m_colNormsUpdated.coeffRef(j) / m_colNormsDirect.coeffRef(j));
456 if (temp2 <= norm_downdate_threshold) {
457 // The updated norm has become too inaccurate so re-compute the column
458 // norm directly.
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);
462 } else {
463 m_colNormsUpdated.coeffRef(j) *= numext::sqrt(temp);
464 }
465 }
466 }
467 }
468
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)));
472
473 m_det_p = (number_of_transpositions % 2) ? -1 : 1;
474 m_isInitialized = true;
475}
476
477#ifndef EIGEN_PARSED_BY_DOXYGEN
478template <typename MatrixType_, typename PermutationIndex_>
479template <typename RhsType, typename DstType>
480void ColPivHouseholderQR<MatrixType_, PermutationIndex_>::_solve_impl(const RhsType& rhs, DstType& dst) const {
481 const Index nonzero_pivots = nonzeroPivots();
482
483 if (nonzero_pivots == 0) {
484 dst.setZero();
485 return;
486 }
487
488 typename RhsType::PlainObject c(rhs);
489
490 c.applyOnTheLeft(householderQ().setLength(nonzero_pivots).adjoint());
491
492 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
493 .template triangularView<Upper>()
494 .solveInPlace(c.topRows(nonzero_pivots));
495
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();
498}
499
500template <typename MatrixType_, typename PermutationIndex_>
501template <bool Conjugate, typename RhsType, typename DstType>
503 DstType& dst) const {
504 const Index nonzero_pivots = nonzeroPivots();
505
506 if (nonzero_pivots == 0) {
507 dst.setZero();
508 return;
509 }
510
511 typename RhsType::PlainObject c(m_colsPermutation.transpose() * rhs);
512
513 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
514 .template triangularView<Upper>()
515 .transpose()
516 .template conjugateIf<Conjugate>()
517 .solveInPlace(c.topRows(nonzero_pivots));
518
519 dst.topRows(nonzero_pivots) = c.topRows(nonzero_pivots);
520 dst.bottomRows(rows() - nonzero_pivots).setZero();
521
522 dst.applyOnTheLeft(householderQ().setLength(nonzero_pivots).template conjugateIf<!Conjugate>());
523}
524#endif
525
526namespace internal {
527
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>,
532 Dense2Dense> {
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()));
538 }
539};
540
541} // end namespace internal
542
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());
551}
552
557template <typename Derived>
558template <typename PermutationIndexType>
560MatrixBase<Derived>::colPivHouseholderQr() const {
562}
563
564} // end namespace Eigen
565
566#endif // EIGEN_COLPIVOTINGHOUSEHOLDERQR_H
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