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 |
| |
Inheritance diagram for Eigen::RandColPivHouseholderQR< MatrixType_, PermutationIndex_ >:
1.13.2 