template<typename MatrixType_, typename PermutationIndex_>
class Eigen::RandColPivHouseholderQR< MatrixType_, PermutationIndex_ >
Randomized blocked Householder rank-revealing QR with column pivoting.
- Template Parameters
-
| MatrixType_ | the type of the matrix being decomposed. |
| PermutationIndex_ | the type of the permutation indices. |
- Warning
- This decomposition is significantly slower when
MatrixType_ uses RowMajor storage. Prefer ColMajor storage when performance matters.
Computes \( \mathbf{A} \mathbf{P} = \mathbf{Q} \mathbf{R} \) using the BQRRP framework introduced by Melnichenko, Murray, Killian, Demmel, Mahoney, Luszczek, and Gates, Anatomy of High-Performance Column-Pivoted QR Decomposition, arXiv:2507.00976 (2025). BQRRP is itself a refinement of the earlier randomized blocked QRCP schemes of Duersch and Gu (RQRCP, SIAM J. Sci. Comput. 39(4):C263–C291, 2017, arXiv:1509.06820) and Martinsson, Quintana-Ortí, Heavner, and van de Geijn (HQRRP, SIAM J. Sci. Comput. 39(2):C96–C115, 2017, arXiv:1512.02671).
The classical Businger–Golub pivot scan is replaced by selecting blocks of b pivots from a small Gaussian sketch \( \mathbf{Y} = \mathbf{G}
\mathbf{A} \) with \( \mathbf{G} \in \mathbb{R}^{b \times m} \) having i.i.d. standard normal entries. Following the BQRRP paper, pivot decisions on the sketch are produced by a partial-pivoted LU on the transposed sketch (cheap and robust), the panel itself is factored with unpivoted blocked Householder QR, the trailing block is updated through the compact-WY apply, and the sketch is downdated by the closed-form Duersch–Gu update. After each block step the asymptotic flop count matches that of an unpivoted blocked Householder QR ( \( 2mn^2 - \tfrac{2}{3}n^3 \) for \( m \ge n \)); almost all computation is BLAS-3, which lifts the BLAS-2 ceiling that limits ColPivHouseholderQR.
The pivot-quality tradeoff is empirically minor: on the matrices in the cited papers, the rank-revealing behavior is comparable to classical column pivoting (LAPACK geqp3).
The block size b can be configured via setBlockSize(); a value of 0 (the default) leaves the algorithm free to pick a size that scales with the input. The seed for the internal RNG can be fixed with setSeed() for reproducible output.
- Note
- The
setOversampling() / oversampling() accessors are retained as documented no-ops for source compatibility with earlier HQRRP-style versions of this class. The BQRRP framework with partial-pivoted-LU pivot selection makes oversampling unnecessary (see Section 2.1 of arXiv:2507.00976).
This class supports the inplace decomposition mechanism. The same public API as ColPivHouseholderQR is provided.
- See also
- ColPivHouseholderQR, MatrixBase::randColPivHouseholderQr()
|
|
Index | blockSize () const |
| | Returns the user-set panel block size, or 0 if the algorithm should pick automatically. The actual block size used during compute() is not exposed.
|
| |
| Index | dimensionOfKernel () const |
| |
| bool | isInjective () const |
| |
| bool | isInvertible () const |
| |
| bool | isSurjective () const |
| |
| RealScalar | maxPivot () const |
| |
| Index | nonzeroPivots () const |
| |
| Index | oversampling () const |
| |
|
| RandColPivHouseholderQR ()=default |
| | Default constructor.
|
| |
|
template<typename InputType> |
| | RandColPivHouseholderQR (const EigenBase< InputType > &matrix) |
| | Constructs and computes a QR factorization from matrix.
|
| |
|
template<typename InputType> |
| | RandColPivHouseholderQR (EigenBase< InputType > &matrix) |
| | Inplace constructor: takes a Ref and decomposes in place.
|
| |
|
| RandColPivHouseholderQR (Index rows, Index cols) |
| | Constructor with memory preallocation.
|
| |
| Index | rank () const |
| |
| RandColPivHouseholderQR & | setBlockSize (Index b) |
| | Sets the panel block size b.
|
| |
| RandColPivHouseholderQR & | setOversampling (Index) |
| | Sets the oversampling parameter p.
|
| |
| RandColPivHouseholderQR & | setSeed (uint64_t seed) |
| | Fixes the seed of the internal RNG for reproducible factorization.
|
| |
| RandColPivHouseholderQR & | setThreshold (const RealScalar &threshold) |
| |
| RandColPivHouseholderQR & | setThreshold (Default_t) |
| |
| RealScalar | threshold () const |
| |
| const AdjointReturnType | adjoint () const |
| |
| constexpr RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | derived () |
| |
| constexpr const RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | derived () const |
| |
| Solve< RandColPivHouseholderQR< MatrixType_, PermutationIndex_ >, Rhs > | solve (const MatrixBase< Rhs > &b) const |
| |
| | SolverBase ()=default |
| |
| const ConstTransposeReturnType | transpose () const |
| |
| constexpr Index | cols () const noexcept |
| |
| constexpr RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | derived () |
| |
| constexpr const RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | derived () const |
| |
| constexpr Index | rows () const noexcept |
| |
| constexpr Index | size () const noexcept |
| |
| Index | dimensionOfKernel () const |
| |
| bool | isInjective () const |
| |
| bool | isInvertible () const |
| |
| bool | isSurjective () const |
| |
| RealScalar | maxPivot () const |
| |
| Index | nonzeroPivots () const |
| |
| Index | rank () const |
| |
| RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | setThreshold (const RealScalar &threshold) |
| |
| RandColPivHouseholderQR< MatrixType_, PermutationIndex_ > & | setThreshold (Default_t) |
| |
| RealScalar | threshold () const |
| |
template<typename MatrixType_, typename PermutationIndex_>
Allows to prescribe a threshold to be used by certain methods, such as rank(), which need to determine when pivots are to be considered nonzero. This is not used for the decomposition itself, except by CompleteOrthogonalDecomposition, whose rank is determined by compute().
When it needs to get the threshold value, Eigen calls threshold(). By default, this is \( 4 \, \min(rows, cols) \, \epsilon \), where \( \epsilon \) is NumTraits<Scalar>::epsilon() and rows and cols are the dimensions of the decomposed matrix. Once you have called the present method setThreshold(const RealScalar&), your value is used instead.
- Parameters
-
| threshold | The new value to use as the threshold. |
A pivot will be considered nonzero if its absolute value is strictly greater than \( threshold \times \vert maxpivot \vert \) where maxpivot is the biggest pivot.
If you want to come back to the default behavior, call setThreshold(Default_t)