Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
FullPivHouseholderQR.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_FULLPIVOTINGHOUSEHOLDERQR_H
13#define EIGEN_FULLPIVOTINGHOUSEHOLDERQR_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
22template <typename MatrixType_, typename PermutationIndex_>
23struct traits<FullPivHouseholderQR<MatrixType_, PermutationIndex_> > : traits<MatrixType_> {
24 using XprKind = MatrixXpr;
25 using StorageKind = SolverStorage;
26 using PermutationIndex = PermutationIndex_;
27 enum { Flags = 0 };
28};
29
30template <typename MatrixType, typename PermutationIndex>
32
33template <typename MatrixType, typename PermutationIndex>
34struct traits<FullPivHouseholderQRMatrixQReturnType<MatrixType, PermutationIndex> > {
35 using ReturnType = typename MatrixType::PlainObject;
36};
37
38} // end namespace internal
39
64template <typename MatrixType_, typename PermutationIndex_>
65class FullPivHouseholderQR : public SolverBase<FullPivHouseholderQR<MatrixType_, PermutationIndex_> >,
66 public RankRevealingBase<FullPivHouseholderQR<MatrixType_, PermutationIndex_> > {
67 public:
68 using MatrixType = MatrixType_;
70 using RankRevealingBase_ = RankRevealingBase<FullPivHouseholderQR>;
71 friend class SolverBase<FullPivHouseholderQR>;
72 friend class RankRevealingBase<FullPivHouseholderQR>;
82 using PermutationIndex = PermutationIndex_;
83 EIGEN_GENERIC_PUBLIC_INTERFACE(FullPivHouseholderQR)
84
85 enum {
86 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
87 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
88 };
90 using HCoeffsType = typename internal::plain_diag_type<MatrixType>::type;
91 using IntDiagSizeVectorType =
92 Matrix<PermutationIndex, 1, internal::min_size_prefer_dynamic(ColsAtCompileTime, RowsAtCompileTime), RowMajor, 1,
93 internal::min_size_prefer_fixed(MaxColsAtCompileTime, MaxRowsAtCompileTime)>;
95 using RowVectorType = typename internal::plain_row_type<MatrixType>::type;
96 using ColVectorType = typename internal::plain_col_type<MatrixType>::type;
97 using PlainObject = typename MatrixType::PlainObject;
98
106 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
107 return Success;
108 }
109
116 : m_qr(),
117 m_hCoeffs(),
118 m_rows_transpositions(),
119 m_cols_transpositions(),
120 m_cols_permutation(),
121 m_temp(),
122 m_isInitialized(false) {}
123
131 : m_qr(rows, cols),
132 m_hCoeffs((std::min)(rows, cols)),
133 m_rows_transpositions((std::min)(rows, cols)),
134 m_cols_transpositions((std::min)(rows, cols)),
135 m_cols_permutation(cols),
136 m_temp(cols),
137 m_isInitialized(false) {}
138
151 template <typename InputType>
153 : m_qr(matrix.rows(), matrix.cols()),
154 m_hCoeffs((std::min)(matrix.rows(), matrix.cols())),
155 m_rows_transpositions((std::min)(matrix.rows(), matrix.cols())),
156 m_cols_transpositions((std::min)(matrix.rows(), matrix.cols())),
157 m_cols_permutation(matrix.cols()),
158 m_temp(matrix.cols()),
159 m_isInitialized(false) {
160 compute(matrix.derived());
161 }
162
170 template <typename InputType>
172 : m_qr(matrix.derived()),
173 m_hCoeffs((std::min)(matrix.rows(), matrix.cols())),
174 m_rows_transpositions((std::min)(matrix.rows(), matrix.cols())),
175 m_cols_transpositions((std::min)(matrix.rows(), matrix.cols())),
176 m_cols_permutation(matrix.cols()),
177 m_temp(matrix.cols()),
178 m_isInitialized(false) {
179 computeInPlace();
180 }
181
182#ifdef EIGEN_PARSED_BY_DOXYGEN
201 template <typename Rhs>
203#endif
204
207 MatrixQReturnType matrixQ(void) const;
208
211 const MatrixType& matrixQR() const {
212 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
213 return m_qr;
214 }
215
216 template <typename InputType>
217 FullPivHouseholderQR& compute(const EigenBase<InputType>& matrix);
218
220 const PermutationType& colsPermutation() const {
221 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
222 return m_cols_permutation;
223 }
224
226 const IntDiagSizeVectorType& rowsTranspositions() const {
227 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
228 return m_rows_transpositions;
229 }
230
244 typename MatrixType::Scalar determinant() const;
245
259 typename MatrixType::RealScalar absDeterminant() const;
260
273 typename MatrixType::RealScalar logAbsDeterminant() const;
274
287 typename MatrixType::Scalar signDeterminant() const;
288
290 RealScalar pivotCoeff(Index i) const { return numext::abs(m_qr.coeff(i, i)); }
291
298 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
299 return Inverse<FullPivHouseholderQR>(*this);
300 }
301
302 inline Index rows() const { return m_qr.rows(); }
303 inline Index cols() const { return m_qr.cols(); }
304
309 const HCoeffsType& hCoeffs() const { return m_hCoeffs; }
310
311#ifndef EIGEN_PARSED_BY_DOXYGEN
312 template <typename RhsType, typename DstType>
313 void _solve_impl(const RhsType& rhs, DstType& dst) const;
314
315 template <bool Conjugate, typename RhsType, typename DstType>
316 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const;
317#endif
318
319 protected:
320 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
321
322 void computeInPlace();
323
324 MatrixType m_qr;
325 HCoeffsType m_hCoeffs;
326 IntDiagSizeVectorType m_rows_transpositions;
327 IntDiagSizeVectorType m_cols_transpositions;
328 PermutationType m_cols_permutation;
329 RowVectorType m_temp;
330 bool m_isInitialized;
331 RealScalar m_precision;
332 Index m_det_p;
333};
334
335template <typename MatrixType, typename PermutationIndex>
337 eigen_assert(m_isInitialized && "HouseholderQR is not initialized.");
338 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
339 Scalar detQ;
340 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
341 return isInjective() ? (detQ * Scalar(m_det_p)) * internal::scaled_prod(m_qr.diagonal()).value() : Scalar(0);
342}
343
344template <typename MatrixType, typename PermutationIndex>
346 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
347 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
348 return isInjective() ? internal::scaled_prod(m_qr.diagonal()).abs() : RealScalar(0);
349}
350
351template <typename MatrixType, typename PermutationIndex>
353 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
354 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
355 return isInjective() ? internal::log_abs_prod(m_qr.diagonal()) : -NumTraits<RealScalar>::infinity();
356}
357
358template <typename MatrixType, typename PermutationIndex>
360 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
361 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
362 Scalar detQ;
363 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
364 return isInjective() ? (detQ * Scalar(m_det_p)) * m_qr.diagonal().array().sign().prod() : Scalar(0);
365}
366
373template <typename MatrixType, typename PermutationIndex>
374template <typename InputType>
375FullPivHouseholderQR<MatrixType, PermutationIndex>& FullPivHouseholderQR<MatrixType, PermutationIndex>::compute(
376 const EigenBase<InputType>& matrix) {
377 m_qr.resize(matrix.rows(), matrix.cols());
378 m_qr = matrix.derived();
379 computeInPlace();
380 return *this;
381}
382
383template <typename MatrixType, typename PermutationIndex>
384void FullPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlace() {
385 eigen_assert(m_qr.cols() <= NumTraits<PermutationIndex>::highest());
386 Index rows = m_qr.rows();
387 Index cols = m_qr.cols();
388 Index size = (std::min)(rows, cols);
389
390 m_hCoeffs.resize(size);
391
392 m_temp.resize(cols);
393
394 m_precision = NumTraits<Scalar>::epsilon() * RealScalar(size);
395
396 m_rows_transpositions.resize(size);
397 m_cols_transpositions.resize(size);
398 Index number_of_transpositions = 0;
399
400 RealScalar biggest(0);
401
402 this->m_nonzero_pivots = size; // the generic case is that in which all pivots are nonzero (invertible case)
403 this->m_maxpivot = RealScalar(0);
404
405 for (Index k = 0; k < size; ++k) {
406 Index row_of_biggest_in_corner, col_of_biggest_in_corner;
407 using Scoring = internal::scalar_score_coeff_op<Scalar>;
408 using Score = typename Scoring::result_type;
409
410 Score score = m_qr.bottomRightCorner(rows - k, cols - k)
411 .unaryExpr(Scoring())
412 .maxCoeff(&row_of_biggest_in_corner, &col_of_biggest_in_corner);
413 row_of_biggest_in_corner += k;
414 col_of_biggest_in_corner += k;
415 RealScalar biggest_in_corner =
416 internal::abs_knowing_score<Scalar>()(m_qr(row_of_biggest_in_corner, col_of_biggest_in_corner), score);
417 if (k == 0) biggest = biggest_in_corner;
418
419 // if the corner is negligible, then we have less than full rank, and we can finish early
420 if (internal::isMuchSmallerThan(biggest_in_corner, biggest, m_precision)) {
421 this->m_nonzero_pivots = k;
422 for (Index i = k; i < size; i++) {
423 m_rows_transpositions.coeffRef(i) = internal::convert_index<PermutationIndex>(i);
424 m_cols_transpositions.coeffRef(i) = internal::convert_index<PermutationIndex>(i);
425 m_hCoeffs.coeffRef(i) = Scalar(0);
426 }
427 break;
428 }
429
430 m_rows_transpositions.coeffRef(k) = internal::convert_index<PermutationIndex>(row_of_biggest_in_corner);
431 m_cols_transpositions.coeffRef(k) = internal::convert_index<PermutationIndex>(col_of_biggest_in_corner);
432 if (k != row_of_biggest_in_corner) {
433 m_qr.row(k).tail(cols - k).swap(m_qr.row(row_of_biggest_in_corner).tail(cols - k));
434 ++number_of_transpositions;
435 }
436 if (k != col_of_biggest_in_corner) {
437 m_qr.col(k).swap(m_qr.col(col_of_biggest_in_corner));
438 ++number_of_transpositions;
439 }
440
441 RealScalar beta;
442 m_qr.col(k).tail(rows - k).makeHouseholderInPlace(m_hCoeffs.coeffRef(k), beta);
443 m_qr.coeffRef(k, k) = beta;
444
445 // remember the maximum absolute value of diagonal coefficients
446 if (numext::abs(beta) > this->m_maxpivot) this->m_maxpivot = numext::abs(beta);
447
448 m_qr.bottomRightCorner(rows - k, cols - k - 1)
449 .applyHouseholderOnTheLeft(m_qr.col(k).tail(rows - k - 1), m_hCoeffs.coeffRef(k), &m_temp.coeffRef(k + 1));
450 }
451
452 m_cols_permutation.setIdentity(cols);
453 for (Index k = 0; k < size; ++k) m_cols_permutation.applyTranspositionOnTheRight(k, m_cols_transpositions.coeff(k));
454
455 m_det_p = (number_of_transpositions % 2) ? -1 : 1;
456 m_isInitialized = true;
457}
458
459#ifndef EIGEN_PARSED_BY_DOXYGEN
460template <typename MatrixType_, typename PermutationIndex_>
461template <typename RhsType, typename DstType>
462void FullPivHouseholderQR<MatrixType_, PermutationIndex_>::_solve_impl(const RhsType& rhs, DstType& dst) const {
463 const Index l_rank = rank();
464
465 // FIXME: introduce nonzeroPivots() and apply the same improvements as in FullPivLU.
466 if (l_rank == 0) {
467 dst.setZero();
468 return;
469 }
470
471 typename RhsType::PlainObject c(rhs);
472
474 for (Index k = 0; k < l_rank; ++k) {
475 Index remainingSize = rows() - k;
476 c.row(k).swap(c.row(m_rows_transpositions.coeff(k)));
477 c.bottomRightCorner(remainingSize, rhs.cols())
478 .applyHouseholderOnTheLeft(m_qr.col(k).tail(remainingSize - 1), m_hCoeffs.coeff(k), temp.data());
479 }
480
481 m_qr.topLeftCorner(l_rank, l_rank).template triangularView<Upper>().solveInPlace(c.topRows(l_rank));
482
483 for (Index i = 0; i < l_rank; ++i) dst.row(m_cols_permutation.indices().coeff(i)) = c.row(i);
484 for (Index i = l_rank; i < cols(); ++i) dst.row(m_cols_permutation.indices().coeff(i)).setZero();
485}
486
487template <typename MatrixType_, typename PermutationIndex_>
488template <bool Conjugate, typename RhsType, typename DstType>
490 DstType& dst) const {
491 const Index l_rank = rank();
492
493 if (l_rank == 0) {
494 dst.setZero();
495 return;
496 }
497
498 typename RhsType::PlainObject c(m_cols_permutation.transpose() * rhs);
499
500 m_qr.topLeftCorner(l_rank, l_rank)
501 .template triangularView<Upper>()
502 .transpose()
503 .template conjugateIf<Conjugate>()
504 .solveInPlace(c.topRows(l_rank));
505
506 dst.topRows(l_rank) = c.topRows(l_rank);
507 dst.bottomRows(rows() - l_rank).setZero();
508
510 const Index size = (std::min)(rows(), cols());
511 for (Index k = size - 1; k >= 0; --k) {
512 Index remainingSize = rows() - k;
513
514 dst.bottomRightCorner(remainingSize, dst.cols())
515 .applyHouseholderOnTheLeft(m_qr.col(k).tail(remainingSize - 1).template conjugateIf<!Conjugate>(),
516 m_hCoeffs.template conjugateIf<Conjugate>().coeff(k), temp.data());
517
518 dst.row(k).swap(dst.row(m_rows_transpositions.coeff(k)));
519 }
520}
521#endif
522
523namespace internal {
524
525template <typename DstXprType, typename MatrixType, typename PermutationIndex>
526struct Assignment<DstXprType, Inverse<FullPivHouseholderQR<MatrixType, PermutationIndex> >,
527 internal::assign_op<typename DstXprType::Scalar,
528 typename FullPivHouseholderQR<MatrixType, PermutationIndex>::Scalar>,
529 Dense2Dense> {
530 using QrType = FullPivHouseholderQR<MatrixType, PermutationIndex>;
531 using SrcXprType = Inverse<QrType>;
532 static void run(DstXprType& dst, const SrcXprType& src,
533 const internal::assign_op<typename DstXprType::Scalar, typename QrType::Scalar>&) {
534 dst = src.nestedExpression().solve(MatrixType::Identity(src.rows(), src.cols()));
535 }
536};
537
544template <typename MatrixType, typename PermutationIndex>
545struct FullPivHouseholderQRMatrixQReturnType
546 : public ReturnByValue<FullPivHouseholderQRMatrixQReturnType<MatrixType, PermutationIndex> > {
547 public:
548 using IntDiagSizeVectorType = typename FullPivHouseholderQR<MatrixType, PermutationIndex>::IntDiagSizeVectorType;
549 using HCoeffsType = typename internal::plain_diag_type<MatrixType>::type;
550 using WorkVectorType = Matrix<typename MatrixType::Scalar, 1, MatrixType::RowsAtCompileTime, RowMajor, 1,
551 MatrixType::MaxRowsAtCompileTime>;
552
553 FullPivHouseholderQRMatrixQReturnType(const MatrixType& qr, const HCoeffsType& hCoeffs,
554 const IntDiagSizeVectorType& rowsTranspositions)
555 : m_qr(qr), m_hCoeffs(hCoeffs), m_rowsTranspositions(rowsTranspositions) {}
556
557 template <typename ResultType>
558 void evalTo(ResultType& result) const {
559 const Index rows = m_qr.rows();
560 WorkVectorType workspace(rows);
561 evalTo(result, workspace);
562 }
563
564 template <typename ResultType>
565 void evalTo(ResultType& result, WorkVectorType& workspace) const {
566 // compute the product H'_0 H'_1 ... H'_n-1,
567 // where H_k is the k-th Householder transformation I - h_k v_k v_k'
568 // and v_k is the k-th Householder vector [1,m_qr(k+1,k), m_qr(k+2,k), ...]
569 const Index rows = m_qr.rows();
570 const Index cols = m_qr.cols();
571 const Index size = (std::min)(rows, cols);
572 workspace.resize(rows);
573 result.setIdentity(rows, rows);
574 for (Index k = size - 1; k >= 0; k--) {
575 result.block(k, k, rows - k, rows - k)
576 .applyHouseholderOnTheLeft(m_qr.col(k).tail(rows - k - 1), numext::conj(m_hCoeffs.coeff(k)),
577 &workspace.coeffRef(k));
578 result.row(k).swap(result.row(m_rowsTranspositions.coeff(k)));
579 }
580 }
581
582 Index rows() const { return m_qr.rows(); }
583 Index cols() const { return m_qr.rows(); }
584
585 protected:
586 typename MatrixType::Nested m_qr;
587 typename HCoeffsType::Nested m_hCoeffs;
588 typename IntDiagSizeVectorType::Nested m_rowsTranspositions;
589};
590
591} // end namespace internal
592
593template <typename MatrixType, typename PermutationIndex>
594inline typename FullPivHouseholderQR<MatrixType, PermutationIndex>::MatrixQReturnType
596 eigen_assert(m_isInitialized && "FullPivHouseholderQR is not initialized.");
597 return MatrixQReturnType(m_qr, m_hCoeffs, m_rows_transpositions);
598}
599
604template <typename Derived>
605template <typename PermutationIndex>
607MatrixBase<Derived>::fullPivHouseholderQr() const {
609}
610
611} // end namespace Eigen
612
613#endif // EIGEN_FULLPIVOTINGHOUSEHOLDERQR_H
EvalReturnType eval() const
Definition DenseBase.h:389
Householder rank-revealing QR decomposition of a matrix with full pivoting.
Definition FullPivHouseholderQR.h:66
const MatrixType & matrixQR() const
Definition FullPivHouseholderQR.h:211
ComputationInfo info() const
Reports whether the QR factorization was successful.
Definition FullPivHouseholderQR.h:105
MatrixQReturnType matrixQ(void) const
Definition FullPivHouseholderQR.h:595
Inverse< FullPivHouseholderQR > inverse() const
Definition FullPivHouseholderQR.h:297
Solve< FullPivHouseholderQR, Rhs > solve(const MatrixBase< Rhs > &b) const
MatrixType::RealScalar logAbsDeterminant() const
Definition FullPivHouseholderQR.h:352
const PermutationType & colsPermutation() const
Definition FullPivHouseholderQR.h:220
const IntDiagSizeVectorType & rowsTranspositions() const
Definition FullPivHouseholderQR.h:226
MatrixType::Scalar determinant() const
Definition FullPivHouseholderQR.h:336
FullPivHouseholderQR()
Default Constructor.
Definition FullPivHouseholderQR.h:115
const HCoeffsType & hCoeffs() const
Definition FullPivHouseholderQR.h:309
MatrixType::RealScalar absDeterminant() const
Definition FullPivHouseholderQR.h:345
FullPivHouseholderQR(Index rows, Index cols)
Default Constructor with memory preallocation.
Definition FullPivHouseholderQR.h:130
bool isInjective() const
Definition RankRevealingBase.h:151
FullPivHouseholderQR(const EigenBase< InputType > &matrix)
Constructs a QR factorization from a given matrix.
Definition FullPivHouseholderQR.h:152
RealScalar pivotCoeff(Index i) const
Definition FullPivHouseholderQR.h:290
FullPivHouseholderQR(EigenBase< InputType > &matrix)
Constructs a QR factorization from a given matrix.
Definition FullPivHouseholderQR.h:171
MatrixType::Scalar signDeterminant() const
Definition FullPivHouseholderQR.h:359
Expression of the inverse of another expression.
Definition Inverse.h:44
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
constexpr Scalar & coeffRef(Index rowId, Index colId)
Definition PlainObjectBase.h:205
Permutation matrix.
Definition PermutationMatrix.h:346
constexpr void resize(Index rows, Index cols)
Definition PlainObjectBase.h:282
Index dimensionOfKernel() const
Definition RankRevealingBase.h:139
bool isInjective() const
Definition RankRevealingBase.h:151
bool isSurjective() const
Definition RankRevealingBase.h:163
FullPivHouseholderQR & 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
@ RowMajor
Definition Constants.h:321
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
Expression type for return value of FullPivHouseholderQR::matrixQ()
Definition FullPivHouseholderQR.h:546