Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
RandColPivHouseholderQR.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9
10#ifndef EIGEN_RANDCOLPIVOTINGHOUSEHOLDERQR_H
11#define EIGEN_RANDCOLPIVOTINGHOUSEHOLDERQR_H
12
13#include <random>
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
22template <typename MatrixType_, typename PermutationIndex_>
23struct traits<RandColPivHouseholderQR<MatrixType_, PermutationIndex_>> : traits<MatrixType_> {
24 using XprKind = MatrixXpr;
25 using StorageKind = SolverStorage;
26 using PermutationIndex = PermutationIndex_;
27 enum { Flags = 0 };
28};
29
30// Fill `mat` with iid samples drawn from a real standard normal distribution.
31template <typename Derived, typename Engine>
32EIGEN_STRONG_INLINE std::enable_if_t<!NumTraits<typename Derived::Scalar>::IsComplex> fill_gaussian(
33 MatrixBase<Derived>& mat, Engine& engine) {
34 using Scalar = typename Derived::Scalar;
35 std::normal_distribution<Scalar> dist(Scalar(0), Scalar(1));
36 for (Index j = 0; j < mat.cols(); ++j)
37 for (Index i = 0; i < mat.rows(); ++i) mat.coeffRef(i, j) = dist(engine);
38}
39
40// Fill `mat` with iid samples drawn from a complex standard normal
41// distribution (real and imaginary parts sampled independently).
42template <typename Derived, typename Engine>
43EIGEN_STRONG_INLINE std::enable_if_t<NumTraits<typename Derived::Scalar>::IsComplex> fill_gaussian(
44 MatrixBase<Derived>& mat, Engine& engine) {
45 using Scalar = typename Derived::Scalar;
46 using RealScalar = typename NumTraits<Scalar>::Real;
47 std::normal_distribution<RealScalar> dist(RealScalar(0), RealScalar(1));
48 for (Index j = 0; j < mat.cols(); ++j)
49 for (Index i = 0; i < mat.rows(); ++i) mat.coeffRef(i, j) = Scalar(dist(engine), dist(engine));
50}
51
52// Stable LAWN-176 column-norm downdate after a Householder reflector has
53// been applied. `pivot_entry` is the entry of the just-pivoted row above
54// column `j`; `tail_norm_fn` recomputes the trailing-column norm from
55// scratch when the running estimate has lost too much precision (see
56// http://www.netlib.org/lapack/lawnspdf/lawn176.pdf).
57template <typename RealScalar, typename Scalar, typename RecomputeFn>
58EIGEN_STRONG_INLINE void lawn176_norm_downdate(RealScalar& norm_updated, RealScalar& norm_direct, Scalar pivot_entry,
59 RealScalar downdate_threshold, RecomputeFn&& tail_norm_fn) {
60 if (numext::is_exactly_zero(norm_updated)) return;
61 RealScalar t = numext::abs(pivot_entry) / norm_updated;
62 t = (RealScalar(1) + t) * (RealScalar(1) - t);
63 if (t < RealScalar(0)) t = RealScalar(0);
64 RealScalar t2 = t * numext::abs2<RealScalar>(norm_updated / norm_direct);
65 if (t2 <= downdate_threshold) {
66 norm_direct = tail_norm_fn();
67 norm_updated = norm_direct;
68 } else {
69 norm_updated *= numext::sqrt(t);
70 }
71}
72
73} // end namespace internal
74
131template <typename MatrixType_, typename PermutationIndex_>
132class RandColPivHouseholderQR : public SolverBase<RandColPivHouseholderQR<MatrixType_, PermutationIndex_>>,
133 public RankRevealingBase<RandColPivHouseholderQR<MatrixType_, PermutationIndex_>> {
134 public:
135 using MatrixType = MatrixType_;
137 using RankRevealingBase_ = RankRevealingBase<RandColPivHouseholderQR>;
139 friend class RankRevealingBase<RandColPivHouseholderQR>;
149 using PermutationIndex = PermutationIndex_;
150 EIGEN_GENERIC_PUBLIC_INTERFACE(RandColPivHouseholderQR)
151
152 enum {
153 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
154 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
155 };
156 using HCoeffsType = typename internal::plain_diag_type<MatrixType>::type;
158 using IntRowVectorType = typename internal::plain_row_type<MatrixType, PermutationIndex>::type;
159 using RowVectorType = typename internal::plain_row_type<MatrixType>::type;
160 using RealRowVectorType = typename internal::plain_row_type<MatrixType, RealScalar>::type;
161 using HouseholderSequenceType =
163 using PlainObject = typename MatrixType::PlainObject;
164
165 private:
166 // Default `m_blockSize == 0` means: let computeInPlace pick a size
167 // tuned to the input dimensions and the host cache hierarchy.
168 static constexpr Index kAutoBlockSize = 0;
169
170 // SIMD-kernel efficiency floor; smaller blocks degrade the panel-QR
171 // and trailing-GEMM kernels without speeding up the sketch.
172 static constexpr Index kKernelFloor = 48;
173 // Hard upper bound on the auto block size.
174 static constexpr Index kBlockCeiling = 1024;
175
176 // Minimum min(rows, cols) at which auto-block enters the blocked path.
177 // Below this, the per-compute sketch overhead (G fill, G*A, per-panel
178 // LU on the sketch) is not amortized by the trailing-GEMM savings vs.
179 // classical Businger-Golub pivoting. Empirically calibrated (Apple M4,
180 // double): n ~= 128 loses by ~1.5x, n >= 256 wins. Set above the
181 // kernel-efficiency floor so that `can_block` (size >= 2*b) cannot
182 // fire below it. A user who calls `setBlockSize(b > 0)` explicitly
183 // bypasses this gate.
184 static constexpr Index kAutoBlockedPathMinSize = 192;
185
186 // L2 cache size in bytes, from Eigen's shared cache-sizes singleton
187 // (which handles cross-platform detection plus user overrides via
188 // setCpuCacheSizes).
189 static Index defaultL2Bytes() {
190 std::ptrdiff_t l1, l2, l3;
191 internal::manage_caching_sizes(GetAction, &l1, &l2, &l3);
192 return Index(l2);
193 }
194
195 // Roofline-derived auto block size for `m_blockSize == kAutoBlockSize`.
196 // `size = min(rows, cols)` is passed in to avoid recomputing it.
197 //
198 // The dominant per-iteration cost is the trailing-update GEMM
199 // (compact-WY apply: C := C - V*T*V^T*C). With panel V resident in
200 // cache, the arithmetic intensity is
201 // AI = 2*b / sizeof(Scalar) [FLOPS / byte]
202 // which crosses the roofline ceiling AI_crit = peak_FLOPS / cache_BW
203 // at b roughly 2-3 on current hardware. That bound is dominated by the
204 // SIMD-kernel efficiency floor (~48); the roofline therefore gives no
205 // useful lower bound on b.
206 //
207 // The binding constraint is the cache-fit invariant: V must stay
208 // resident across the trailing sweep, otherwise the streamed re-reads
209 // drop us off the compute roof onto the DRAM-bandwidth side. That
210 // yields the upper bound
211 // b * rows * sizeof(Scalar) <= L2 / 2 (half of L2; remainder
212 // for the streamed C tile)
213 // BQRRP's recommended b ~= n/32 (paper Section 3.2) sits inside this
214 // window for matrices up to roughly 16 * L2 / (rows * sizeof(Scalar));
215 // beyond that, the cache bound binds and clamps b.
216 static Index computeAutoBlockSize(Index rows, Index size) {
217 // Degenerate empty inputs (0 rows or 0 cols): there is no work, and
218 // the cache-bound calculation below would divide by `rows`. Return 0
219 // so the caller's can_block check (b > 0) routes to the unblocked
220 // path, which handles empty matrices correctly.
221 if (rows <= 0 || size <= 0) return Index(0);
222 const Index scalar_bytes = Index(sizeof(Scalar));
223 const Index b_cache = numext::maxi(Index(1), (defaultL2Bytes() / Index(2)) / (rows * scalar_bytes));
224 const Index b_bqrrp = size / Index(32);
225
226 Index b = numext::maxi(Index(kKernelFloor), b_bqrrp);
227 b = numext::mini(b, numext::maxi(Index(kKernelFloor), b_cache));
228 b = numext::mini(b, Index(kBlockCeiling));
229 return b;
230 }
231
232 void init(Index rows, Index cols) {
233 Index diag = numext::mini(rows, cols);
234 m_hCoeffs.resize(diag);
235 m_colsPermutation.resize(cols);
236 m_temp.resize(cols);
237 m_isInitialized = false;
238 }
239
240 public:
243
245 RandColPivHouseholderQR(Index rows, Index cols) : m_qr(rows, cols) { init(rows, cols); }
246
248 template <typename InputType>
249 explicit RandColPivHouseholderQR(const EigenBase<InputType>& matrix) : m_qr(matrix.rows(), matrix.cols()) {
250 init(matrix.rows(), matrix.cols());
251 compute(matrix.derived());
252 }
253
255 template <typename InputType>
256 explicit RandColPivHouseholderQR(EigenBase<InputType>& matrix) : m_qr(matrix.derived()) {
257 init(matrix.rows(), matrix.cols());
258 computeInPlace();
259 }
260
261#ifdef EIGEN_PARSED_BY_DOXYGEN
262 template <typename Rhs>
263 inline Solve<RandColPivHouseholderQR, Rhs> solve(const MatrixBase<Rhs>& b) const;
264#endif
265
266 HouseholderSequenceType householderQ() const;
267 HouseholderSequenceType matrixQ() const { return householderQ(); }
268
269 const MatrixType& matrixQR() const {
270 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
271 return m_qr;
272 }
273
274 const MatrixType& matrixR() const {
275 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
276 return m_qr;
277 }
278
279 template <typename InputType>
280 RandColPivHouseholderQR& compute(const EigenBase<InputType>& matrix);
281
282 const PermutationType& colsPermutation() const {
283 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
284 return m_colsPermutation;
285 }
286
287 typename MatrixType::Scalar determinant() const;
288 typename MatrixType::RealScalar absDeterminant() const;
289 typename MatrixType::RealScalar logAbsDeterminant() const;
290 typename MatrixType::Scalar signDeterminant() const;
291
292 RealScalar pivotCoeff(Index i) const { return numext::abs(m_qr.coeff(i, i)); }
293
294 inline Inverse<RandColPivHouseholderQR> inverse() const {
295 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
296 return Inverse<RandColPivHouseholderQR>(*this);
297 }
298
299 inline Index rows() const { return m_qr.rows(); }
300 inline Index cols() const { return m_qr.cols(); }
301
302 const HCoeffsType& hCoeffs() const { return m_hCoeffs; }
303
304 ComputationInfo info() const {
305 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
306 return Success;
307 }
308
321 eigen_assert(b >= 0 && "Block size must be non-negative.");
322 m_blockSize = b;
323 return *this;
324 }
325
335
342 m_seed = seed;
343 m_seedSet = true;
344 return *this;
345 }
346
351 Index blockSize() const { return m_blockSize; }
352
354 Index oversampling() const { return Index(0); }
355
356#ifndef EIGEN_PARSED_BY_DOXYGEN
357 template <typename RhsType, typename DstType>
358 void _solve_impl(const RhsType& rhs, DstType& dst) const;
359
360 template <bool Conjugate, typename RhsType, typename DstType>
361 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const;
362#endif
363
364 protected:
365 friend class internal::CompleteOrthogonalDecompositionImpl<MatrixType, PermutationIndex, RandColPivHouseholderQR>;
366
367 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
368
369 void computeInPlace();
370
371 // Unblocked column-pivoted Householder QR on rows [row0, m) and columns
372 // [col0, col0 + ncols), using full-column swaps. Updates m_hCoeffs in
373 // [col0, col0 + ncols), m_colsPermutation, and the maxpivot tracker.
374 // Returns the number of column transpositions applied. Used both as
375 // the small-matrix fallback path and as the rank-deficient tail of the
376 // blocked path.
377 Index unblocked_pivoted_qr(Index row0, Index col0, Index ncols, RealScalar threshold_helper);
378
379 // Scan the diagonal of m_qr and set m_nonzero_pivots / m_maxpivot using
380 // the LAWN-176 threshold (same scale as ColPivHouseholderQR).
381 void finalize_rank(RealScalar threshold_helper);
382
383 MatrixType m_qr;
384 HCoeffsType m_hCoeffs;
385 PermutationType m_colsPermutation;
386 RowVectorType m_temp;
387 Index m_blockSize = kAutoBlockSize;
388 uint64_t m_seed = 0;
389 bool m_seedSet = false;
390 bool m_isInitialized = false;
391 Index m_det_p = 1;
392};
393
394template <typename MatrixType, typename PermutationIndex>
395typename MatrixType::Scalar RandColPivHouseholderQR<MatrixType, PermutationIndex>::determinant() const {
396 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
397 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
398 Scalar detQ;
399 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
400 return isInjective() ? (detQ * Scalar(m_det_p)) * internal::scaled_prod(m_qr.diagonal()).value() : Scalar(0);
401}
402
403template <typename MatrixType, typename PermutationIndex>
404typename MatrixType::RealScalar RandColPivHouseholderQR<MatrixType, PermutationIndex>::absDeterminant() const {
405 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
406 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
407 return isInjective() ? internal::scaled_prod(m_qr.diagonal()).abs() : RealScalar(0);
408}
409
410template <typename MatrixType, typename PermutationIndex>
411typename MatrixType::RealScalar RandColPivHouseholderQR<MatrixType, PermutationIndex>::logAbsDeterminant() const {
412 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
413 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
414 return isInjective() ? internal::log_abs_prod(m_qr.diagonal()) : -NumTraits<RealScalar>::infinity();
415}
416
417template <typename MatrixType, typename PermutationIndex>
418typename MatrixType::Scalar RandColPivHouseholderQR<MatrixType, PermutationIndex>::signDeterminant() const {
419 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
420 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_qr, "You can't take the determinant of a non-square matrix!");
421 Scalar detQ;
422 internal::householder_determinant<HCoeffsType, Scalar, NumTraits<Scalar>::IsComplex>::run(m_hCoeffs, detQ);
423 return isInjective() ? (detQ * Scalar(m_det_p)) * m_qr.diagonal().array().sign().prod() : Scalar(0);
424}
425
426template <typename MatrixType, typename PermutationIndex>
427template <typename InputType>
428RandColPivHouseholderQR<MatrixType, PermutationIndex>& RandColPivHouseholderQR<MatrixType, PermutationIndex>::compute(
429 const EigenBase<InputType>& matrix) {
430 m_qr.resize(matrix.rows(), matrix.cols());
431 m_qr = matrix.derived();
432 computeInPlace();
433 return *this;
434}
435
436template <typename MatrixType, typename PermutationIndex>
437Index RandColPivHouseholderQR<MatrixType, PermutationIndex>::unblocked_pivoted_qr(Index row0, Index col0, Index ncols,
438 RealScalar threshold_helper) {
439 const Index rows = m_qr.rows();
440 const Index col_end = col0 + ncols;
441 const Index sub_rows = rows - row0;
442 Index num_transpositions = 0;
443
445 const bool stable_norms = internal::column_norms_with_fallback(m_qr.block(row0, col0, sub_rows, ncols), norms_direct);
446 Matrix<RealScalar, 1, Dynamic> norms_updated = norms_direct;
447 const RealScalar downdate_threshold = numext::sqrt(NumTraits<RealScalar>::epsilon());
448
449 const Index size = (std::min)(sub_rows, ncols);
450 for (Index k = 0; k < size; ++k) {
451 Index biggest;
452 RealScalar biggest_norm = norms_updated.tail(ncols - k).maxCoeff(&biggest);
453 biggest += k;
454
455 if (this->m_nonzero_pivots == m_qr.diagonalSize() &&
456 biggest_norm < threshold_helper * numext::sqrt(RealScalar(rows - row0 - k)))
457 this->m_nonzero_pivots = col0 + k;
458
459 if (k != biggest) {
460 m_qr.col(col0 + k).swap(m_qr.col(col0 + biggest));
461 std::swap(norms_updated.coeffRef(k), norms_updated.coeffRef(biggest));
462 std::swap(norms_direct.coeffRef(k), norms_direct.coeffRef(biggest));
463 m_colsPermutation.applyTranspositionOnTheRight(col0 + k, col0 + biggest);
464 ++num_transpositions;
465 }
466
467 RealScalar beta;
468 m_qr.col(col0 + k).tail(sub_rows - k).makeHouseholderInPlace(m_hCoeffs.coeffRef(col0 + k), beta);
469 m_qr.coeffRef(row0 + k, col0 + k) = beta;
470 if (numext::abs(beta) > this->m_maxpivot) this->m_maxpivot = numext::abs(beta);
471
472 // Apply the reflector only to the remaining panel columns. Columns at
473 // indices >= col_end are owned by the outer caller and updated via a
474 // BLAS-3 trailing update; in the tail/fallback path col_end equals
475 // m_qr.cols(), so this naturally degrades to a full apply.
476 const Index trail_cols = col_end - col0 - k - 1;
477 if (trail_cols > 0) {
478 m_qr.block(row0 + k, col0 + k + 1, sub_rows - k, trail_cols)
479 .applyHouseholderOnTheLeft(m_qr.col(col0 + k).tail(sub_rows - k - 1), m_hCoeffs.coeff(col0 + k),
480 &m_temp.coeffRef(col0 + k + 1));
481 }
482
483 for (Index j = k + 1; j < ncols; ++j) {
484 internal::lawn176_norm_downdate(norms_updated.coeffRef(j), norms_direct.coeffRef(j),
485 m_qr.coeff(row0 + k, col0 + j), downdate_threshold, [&] {
486 const auto tail = m_qr.col(col0 + j).tail(sub_rows - k - 1);
487 return stable_norms ? tail.stableNorm() : tail.norm();
488 });
489 }
490 }
491 return num_transpositions;
492}
493
494template <typename MatrixType, typename PermutationIndex>
495void RandColPivHouseholderQR<MatrixType, PermutationIndex>::finalize_rank(RealScalar threshold_helper) {
496 const Index rows = m_qr.rows();
497 const Index size = (std::min)(rows, m_qr.cols());
498 // m_maxpivot is already up-to-date: the blocked path tracks it per
499 // panel, and unblocked_pivoted_qr tracks it per step.
500 // If neither the blocked path nor the unblocked tail tightened the
501 // rank cap, fall back to the LAWN-176 first-below-threshold scan.
502 // This handles the full-rank-blocked-path case where every panel
503 // was full rank and the only "small" diagonal entries are in the
504 // unblocked tail.
505 if (this->m_nonzero_pivots == size) {
506 for (Index i = 0; i < size; ++i) {
507 RealScalar a = numext::abs(m_qr.coeff(i, i));
508 if (a < threshold_helper * numext::sqrt(RealScalar(rows - i))) {
509 this->m_nonzero_pivots = i;
510 break;
511 }
512 }
513 }
514}
515
516template <typename MatrixType, typename PermutationIndex>
517void RandColPivHouseholderQR<MatrixType, PermutationIndex>::computeInPlace() {
518 eigen_assert(m_qr.cols() <= NumTraits<PermutationIndex>::highest());
519
520 const Index rows = m_qr.rows();
521 const Index cols = m_qr.cols();
522 const Index size = (std::min)(rows, cols);
523
524 m_hCoeffs.resize(size);
525 m_temp.resize(cols);
526 m_colsPermutation.resize(cols);
527 m_colsPermutation.setIdentity();
528 this->m_nonzero_pivots = size;
529 this->m_maxpivot = RealScalar(0);
530 Index num_transpositions = 0;
531
532 // Global rank-detection scale, derived from the original column norms
533 // exactly as ColPivHouseholderQR does (LAWN-176). All panel calls share
534 // this threshold so rank revelation is consistent across blocks.
535 // The test "norm < eps * max_initial_norm * sqrt((rows - k) / rows)" is written without squaring the norms, which
536 // overflow or underflow for entries beyond sqrt(max) or below sqrt(min).
537 Matrix<RealScalar, 1, Dynamic> initial_norms;
538 internal::column_norms_with_fallback(m_qr, initial_norms);
539 const RealScalar threshold_helper =
540 cols == 0 ? RealScalar(0)
541 : initial_norms.maxCoeff() * NumTraits<RealScalar>::epsilon() / numext::sqrt(RealScalar(rows));
542
543 const bool auto_block = (m_blockSize == kAutoBlockSize);
544 const Index requested_b = auto_block ? computeAutoBlockSize(rows, size) : m_blockSize;
545 const Index b = (std::min)(requested_b, size);
546
547 // Gates for entering the blocked path:
548 // - `b > 0` and `rows > b` for the trailing update to have work,
549 // - `size >= 2*b` so at least two full blocks fit (one block + tail
550 // is handled more efficiently by the unblocked path),
551 // - in the auto-block path, an additional size threshold so the
552 // sketch overhead is amortized by trailing-GEMM savings (see
553 // kAutoBlockedPathMinSize). Users who pin a block size via
554 // setBlockSize() bypass this — useful for tests that need to
555 // exercise the blocked path on small inputs.
556 const bool can_block = (b > 0) && (size >= 2 * b) && (rows > b) && (!auto_block || size >= kAutoBlockedPathMinSize);
557 if (!can_block) {
558 num_transpositions += unblocked_pivoted_qr(0, 0, cols, threshold_helper);
559 m_det_p = (num_transpositions % 2) ? -1 : 1;
560 finalize_rank(threshold_helper);
561 m_isInitialized = true;
562 return;
563 }
564
566 using WorkVector = Matrix<Scalar, Dynamic, 1>;
567 // Dynamic-sized Ref types so that a fixed-size MatrixType (e.g.
568 // Matrix<float, 8, 10>) and its run-time-sized blocks can both be
569 // wrapped without tripping Ref's compile-time-size check.
570 using WorkMatrixRef = Ref<WorkMatrix, 0, OuterStride<>>;
571 // Panels of m_qr carry MatrixType's storage order, which need not be the workspaces'.
573 using QrPanelRef = Ref<QrMatrix, 0, OuterStride<>>;
574 using HCoeffsRef = Ref<WorkVector>;
576
577 // Hoisted workspaces — allocated once per compute() call. Worst-case
578 // sizes are computed from the first iteration (n_remain = cols,
579 // trail_cols = cols - b); subsequent iterations use shrinking
580 // sub-blocks via leftCols/topRows.
581 WorkMatrix Y(b, cols);
582 WorkMatrix YT(cols, b);
583 WorkMatrix sketch_R(b, b);
584 IpivType ipiv(b);
585 WorkVector y_hcoeffs(b);
586 WorkVector y_temp(cols);
587
588 // Initialize the sketch Y = G * A. We don't keep G around; the
589 // Duersch-Gu update (step 24) maintains Y deterministically from
590 // here on.
591 {
592 WorkMatrix G(b, rows);
593 uint64_t seed = m_seed;
594 if (!m_seedSet) {
595 std::random_device rd;
596 seed = (uint64_t(rd()) << 32) | uint64_t(rd());
597 }
598 std::mt19937_64 engine(seed);
599 internal::fill_gaussian(G, engine);
600 Y.noalias() = G * m_qr;
601 }
602
603 Index k = 0;
604 bool blocked_terminated_early = false;
605 while (k + b <= size && cols - k > b) {
606 const Index n_remain = cols - k; // columns from k to end
607 const Index trail_cols = n_remain - b; // columns to the right of the panel
608 const Index sub_rows = rows - k; // rows from k to end
609
610 // === Step 7 (Algorithm 2): "crazy man's QRCP" on the sketch.
611 // Form Y_T = Y(:, k:)^T and run partial-pivoted LU on it. The IPIV
612 // vector tells us which b columns of Y(:, k:) (and thus which
613 // columns of m_qr.middleCols(k, n_remain)) to bring to the front.
614 auto Y_curr = Y.middleCols(k, n_remain);
615 auto Y_T = YT.topRows(n_remain);
616 Y_T = Y_curr.transpose();
617
618 typename IpivType::StorageIndex nb_lu_transp = 0;
619 internal::partial_lu_inplace(Y_T, ipiv, nb_lu_transp);
620
621 // === Steps 9-11: apply IPIV to columns of m_qr and Y starting at
622 // absolute column k (LAPACK-style serial swaps; equivalent to
623 // applying Algorithm 4 of the BQRRP paper to the converted pivot
624 // vector).
625 for (Index i = 0; i < b; ++i) {
626 Index dst = static_cast<Index>(ipiv.coeff(i));
627 if (dst != i) {
628 m_qr.col(k + i).swap(m_qr.col(k + dst));
629 Y.col(k + i).swap(Y.col(k + dst));
630 m_colsPermutation.applyTranspositionOnTheRight(k + i, k + dst);
631 ++num_transpositions;
632 }
633 }
634
635 // Materialize R_sk in the upper triangle of Y(:, k:) via unpivoted
636 // blocked Householder QR. We discard the resulting Householder
637 // vectors and tau; only R_sk feeds the step-24 sketch update.
638 // Wrap in `Ref` so householder_qr_inplace_blocked sees a flat
639 // MatrixQR — its internal `Block<MatrixQR, ...>` typedef does not
640 // compose with Block-of-Block expressions.
641 {
642 WorkMatrixRef Y_curr_ref(Y_curr);
643 Ref<WorkVector> y_hc_ref(y_hcoeffs);
644 internal::householder_qr_inplace_blocked<WorkMatrixRef, Ref<WorkVector>>::run(
645 Y_curr_ref, y_hc_ref, /*maxBlockSize=*/(std::min)(b, Index(48)), y_temp.data());
646 }
647
648 // Save R_sk_11 = upper-triangular portion of Y(:, k:k+b) before the
649 // panel QR overwrites the corresponding columns of m_qr (via the
650 // trailing update); we need it for step 24.
651 sketch_R = Y.block(0, k, b, b);
652 // The step-24 update below consumes R_sk_11 as a plain matrix, so clear
653 // the Householder vectors the sketch QR left below its diagonal.
654 sketch_R.template triangularView<StrictlyLower>().setZero();
655
656 // === Step 12: tall unpivoted Householder QR on the panel.
657 auto panel = m_qr.block(k, k, sub_rows, b);
658 auto hCoeffsSegment = m_hCoeffs.segment(k, b);
659 {
660 QrPanelRef panel_ref(panel);
661 HCoeffsRef hc_ref(hCoeffsSegment);
662 internal::householder_qr_inplace_blocked<QrPanelRef, HCoeffsRef>::run(
663 panel_ref, hc_ref, /*maxBlockSize=*/(std::min)(b, Index(48)), m_temp.data());
664 }
665
666 this->m_maxpivot = (std::max)(this->m_maxpivot, m_qr.diagonal().segment(k, b).cwiseAbs().maxCoeff());
667
668 // Detect rank deficiency by scanning the panel's diagonal against
669 // a relative threshold (max pivot seen so far times the default
670 // RankRevealingBase tolerance). The LAWN-176 threshold used by
671 // ColPivHouseholderQR assumes a strictly monotonic diagonal —
672 // BQRRP's unpivoted panel QR breaks that assumption for matrices
673 // with closely-spaced singular values (e.g. partial isometries),
674 // so we use the same relative tolerance that RankRevealingBase::
675 // rank() applies to the final diagonal.
676 Index panel_rank = b;
677 {
678 const RealScalar relative_cutoff = this->m_maxpivot * NumTraits<RealScalar>::epsilon() * RealScalar(4 * size);
679 for (Index i = 0; i < b; ++i) {
680 RealScalar a = numext::abs(m_qr.coeff(k + i, k + i));
681 if (a <= relative_cutoff) {
682 panel_rank = i;
683 break;
684 }
685 }
686 }
687
688 // === Step 17: apply Q^H from the panel to the trailing block.
689 // The loop guard `cols - k > b` guarantees `trail_cols > 0`. We
690 // pass the un-conjugated coeffs because apply_block_householder_on_the_left
691 // conjugates internally when forward=false (matching how HouseholderQR
692 // drives this same routine).
693 auto trailing = m_qr.block(k, k + b, sub_rows, trail_cols);
694 internal::apply_block_householder_on_the_left(trailing, panel, hCoeffsSegment,
695 /*forward=*/false);
696
697 if (panel_rank < b) {
698 // Pin the rank cap and break out; the unblocked tail will
699 // process the remaining columns. The tail's m_nonzero_pivots
700 // write is gated on it still being unset (== diagonalSize),
701 // so a tighter cap from here survives.
702 if (this->m_nonzero_pivots == size) {
703 this->m_nonzero_pivots = k + panel_rank;
704 }
705 k += b;
706 blocked_terminated_early = true;
707 break;
708 }
709
710 // === Step 24: Duersch-Gu sketch update.
711 // Y(:, k+b:) := R_sk_12 - R_sk_11 * R_11^{-1} * R_12
712 // R_sk_12 currently sits in Y.middleCols(k+b, trail_cols) (the QR of
713 // the sketch above placed it there). R_sk_11 we saved into sketch_R.
714 // R_11 and R_12 are the corresponding blocks of m_qr after the
715 // panel QR + trailing update.
716 // Associating as (R_sk_11 * R_11^{-1}) * R_12 keeps the triangular solve at
717 // b x b and leaves a single GEMM reading R_12 straight out of m_qr: no
718 // b x trail_cols workspace, and no wide triangular solve/product (both of
719 // which run well below GEMM throughput).
720 {
721 m_qr.block(k, k, b, b).template triangularView<Upper>().template solveInPlace<OnTheRight>(sketch_R);
722 Y.middleCols(k + b, trail_cols).noalias() -= sketch_R * m_qr.block(k, k + b, b, trail_cols);
723 }
724
725 k += b;
726 }
727
728 // Tail loop: any remaining columns (last partial block, or the rank-
729 // deficient remainder after early termination) handled by the
730 // unblocked pivoted QR. This routine also updates m_nonzero_pivots
731 // along its diagonal scan, which finalize_rank below cross-checks.
732 if (k < cols && (k < size || blocked_terminated_early)) {
733 num_transpositions += unblocked_pivoted_qr(k, k, cols - k, threshold_helper);
734 }
735
736 m_det_p = (num_transpositions % 2) ? -1 : 1;
737
738 // Final rank determination: scan the entire diagonal with the LAWN-176
739 // threshold. This refines whatever the unblocked tail set, and covers
740 // the full-rank blocked path where m_nonzero_pivots was never touched.
741 finalize_rank(threshold_helper);
742
743 m_isInitialized = true;
744}
745
746#ifndef EIGEN_PARSED_BY_DOXYGEN
747template <typename MatrixType_, typename PermutationIndex_>
748template <typename RhsType, typename DstType>
749void RandColPivHouseholderQR<MatrixType_, PermutationIndex_>::_solve_impl(const RhsType& rhs, DstType& dst) const {
750 const Index nonzero_pivots = nonzeroPivots();
751
752 if (nonzero_pivots == 0) {
753 dst.setZero();
754 return;
755 }
756
757 typename RhsType::PlainObject c(rhs);
758
759 c.applyOnTheLeft(householderQ().setLength(nonzero_pivots).adjoint());
760
761 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
762 .template triangularView<Upper>()
763 .solveInPlace(c.topRows(nonzero_pivots));
764
765 for (Index i = 0; i < nonzero_pivots; ++i) dst.row(m_colsPermutation.indices().coeff(i)) = c.row(i);
766 for (Index i = nonzero_pivots; i < cols(); ++i) dst.row(m_colsPermutation.indices().coeff(i)).setZero();
767}
768
769template <typename MatrixType_, typename PermutationIndex_>
770template <bool Conjugate, typename RhsType, typename DstType>
772 DstType& dst) const {
773 const Index nonzero_pivots = nonzeroPivots();
774
775 if (nonzero_pivots == 0) {
776 dst.setZero();
777 return;
778 }
779
780 typename RhsType::PlainObject c(m_colsPermutation.transpose() * rhs);
781
782 m_qr.topLeftCorner(nonzero_pivots, nonzero_pivots)
783 .template triangularView<Upper>()
784 .transpose()
785 .template conjugateIf<Conjugate>()
786 .solveInPlace(c.topRows(nonzero_pivots));
787
788 dst.topRows(nonzero_pivots) = c.topRows(nonzero_pivots);
789 dst.bottomRows(rows() - nonzero_pivots).setZero();
790
791 dst.applyOnTheLeft(householderQ().setLength(nonzero_pivots).template conjugateIf<!Conjugate>());
792}
793#endif
794
795namespace internal {
796
797template <typename DstXprType, typename MatrixType, typename PermutationIndex>
798struct Assignment<DstXprType, Inverse<RandColPivHouseholderQR<MatrixType, PermutationIndex>>,
799 internal::assign_op<typename DstXprType::Scalar,
800 typename RandColPivHouseholderQR<MatrixType, PermutationIndex>::Scalar>,
801 Dense2Dense> {
802 using QrType = RandColPivHouseholderQR<MatrixType, PermutationIndex>;
803 using SrcXprType = Inverse<QrType>;
804 static void run(DstXprType& dst, const SrcXprType& src,
805 const internal::assign_op<typename DstXprType::Scalar, typename QrType::Scalar>&) {
806 dst = src.nestedExpression().solve(MatrixType::Identity(src.rows(), src.cols()));
807 }
808};
809
810} // end namespace internal
811
812template <typename MatrixType, typename PermutationIndex>
813typename RandColPivHouseholderQR<MatrixType, PermutationIndex>::HouseholderSequenceType
814RandColPivHouseholderQR<MatrixType, PermutationIndex>::householderQ() const {
815 eigen_assert(m_isInitialized && "RandColPivHouseholderQR is not initialized.");
816 return HouseholderSequenceType(m_qr, m_hCoeffs.conjugate());
817}
818
823template <typename Derived>
824template <typename PermutationIndexType>
826MatrixBase<Derived>::randColPivHouseholderQr() const {
828}
829
830} // end namespace Eigen
831
832#endif // EIGEN_RANDCOLPIVOTINGHOUSEHOLDERQR_H
EvalReturnType eval() const
Definition DenseBase.h:389
Sequence of Householder reflections acting on subspaces with decreasing size.
Definition HouseholderSequence.h:155
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
Permutation matrix.
Definition PermutationMatrix.h:346
Randomized blocked Householder rank-revealing QR with column pivoting.
Definition RandColPivHouseholderQR.h:133
RandColPivHouseholderQR(Index rows, Index cols)
Constructor with memory preallocation.
Definition RandColPivHouseholderQR.h:245
RandColPivHouseholderQR & setBlockSize(Index b)
Sets the panel block size b.
Definition RandColPivHouseholderQR.h:320
RandColPivHouseholderQR & setOversampling(Index)
Sets the oversampling parameter p.
Definition RandColPivHouseholderQR.h:334
Index oversampling() const
Definition RandColPivHouseholderQR.h:354
Index blockSize() const
Returns the user-set panel block size, or 0 if the algorithm should pick automatically....
Definition RandColPivHouseholderQR.h:351
RandColPivHouseholderQR()=default
Default constructor.
RandColPivHouseholderQR(EigenBase< InputType > &matrix)
Inplace constructor: takes a Ref and decomposes in place.
Definition RandColPivHouseholderQR.h:256
RandColPivHouseholderQR(const EigenBase< InputType > &matrix)
Constructs and computes a QR factorization from matrix.
Definition RandColPivHouseholderQR.h:249
RandColPivHouseholderQR & setSeed(uint64_t seed)
Fixes the seed of the internal RNG for reproducible factorization.
Definition RandColPivHouseholderQR.h:341
Index dimensionOfKernel() const
Definition RankRevealingBase.h:139
bool isInjective() const
Definition RankRevealingBase.h:151
bool isSurjective() const
Definition RankRevealingBase.h:163
RandColPivHouseholderQR & 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
A matrix or vector expression mapping an existing expression.
Definition Ref.h:261
Pseudo expression representing a solving operation.
Definition Solve.h:63
constexpr Derived & derived()
Definition EigenBase.h:50
Represents a sequence of transpositions (row/column interchange)
Definition Transpositions.h:144
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
constexpr Index size() const noexcept
Definition EigenBase.h:65
Eigen::Index Index
The interface type of indices.
Definition EigenBase.h:44
Holds information about the various numeric (i.e. scalar) types allowed by Eigen.
Definition NumTraits.h:267