Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseQR.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012-2013 Desire Nuentsa <desire.nuentsa_wakam@inria.fr>
5// Copyright (C) 2012-2014 Gael Guennebaud <gael.guennebaud@inria.fr>
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_SPARSE_QR_H
13#define EIGEN_SPARSE_QR_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20template <typename MatrixType, typename OrderingType>
21class SparseQR;
22template <typename SparseQRType>
23struct SparseQRMatrixQReturnType;
24template <typename SparseQRType>
25struct SparseQRMatrixQTransposeReturnType;
26template <typename SparseQRType, typename Derived>
27struct SparseQR_QProduct;
28namespace internal {
29template <typename SparseQRType>
30struct traits<SparseQRMatrixQReturnType<SparseQRType> > {
31 using ReturnType = typename SparseQRType::MatrixType;
32 using StorageIndex = typename ReturnType::StorageIndex;
33 using StorageKind = typename ReturnType::StorageKind;
34 enum { RowsAtCompileTime = Dynamic, ColsAtCompileTime = Dynamic };
35};
36template <typename SparseQRType>
37struct traits<SparseQRMatrixQTransposeReturnType<SparseQRType> > {
38 using ReturnType = typename SparseQRType::MatrixType;
39};
40template <typename SparseQRType, typename Derived>
41struct traits<SparseQR_QProduct<SparseQRType, Derived> > {
42 using ReturnType = typename Derived::PlainObject;
43};
44} // End namespace internal
45
94template <typename MatrixType_, typename OrderingType_>
95class SparseQR : public SparseSolverBase<SparseQR<MatrixType_, OrderingType_> > {
96 protected:
98 using Base::m_isInitialized;
99
100 public:
101 using Base::_solve_impl;
102 using MatrixType = MatrixType_;
103 using OrderingType = OrderingType_;
104 using Scalar = typename MatrixType::Scalar;
105 using RealScalar = typename MatrixType::RealScalar;
106 using StorageIndex = typename MatrixType::StorageIndex;
108 using IndexVector = Matrix<StorageIndex, Dynamic, 1>;
109 using ScalarVector = Matrix<Scalar, Dynamic, 1>;
111
112 enum { ColsAtCompileTime = MatrixType::ColsAtCompileTime, MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime };
113
114 public:
115 SparseQR()
116 : m_analysisIsok(false),
117 m_lastError(""),
118 m_useDefaultThreshold(true),
119 m_lastPivotLookAheadSkipped(false),
120 m_isQSorted(false),
121 m_isEtreeOk(false) {}
122
129 explicit SparseQR(const MatrixType& mat)
130 : m_analysisIsok(false),
131 m_lastError(""),
132 m_useDefaultThreshold(true),
133 m_lastPivotLookAheadSkipped(false),
134 m_isQSorted(false),
135 m_isEtreeOk(false) {
136 compute(mat);
137 }
138
145 void compute(const MatrixType& mat) {
146 analyzePattern(mat);
147 factorize(mat);
148 }
149 void analyzePattern(const MatrixType& mat);
150 void factorize(const MatrixType& mat);
151
154 inline Index rows() const { return m_pmat.rows(); }
155
158 inline Index cols() const { return m_pmat.cols(); }
159
173 const QRMatrixType& matrixR() const { return m_R; }
174
179 Index rank() const {
180 eigen_assert(m_isInitialized && "The factorization should be called first, use compute()");
181 return m_nonzeropivots;
182 }
183
202 SparseQRMatrixQReturnType<SparseQR> matrixQ() const { return SparseQRMatrixQReturnType<SparseQR>(*this); }
203
207 const PermutationType& colsPermutation() const {
208 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
209 return m_outputPerm_c;
210 }
211
221 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
222 return m_lastPivotLookAheadSkipped;
223 }
224
228 std::string lastErrorMessage() const { return m_lastError; }
229
231 template <typename Rhs, typename Dest>
232 bool _solve_impl(const MatrixBase<Rhs>& B, MatrixBase<Dest>& dest) const {
233 eigen_assert(m_isInitialized && "The factorization should be called first, use compute()");
234 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, B, false,
235 "SparseQR::solve() : invalid number of rows in the right hand side matrix");
236
237 Index rank = this->rank();
238
239 // Compute Q^* * b;
240 typename Dest::PlainObject y, b;
241 y = this->matrixQ().adjoint() * B;
242 b = y;
243
244 // Solve with the triangular matrix R
245 y.resize((std::max<Index>)(cols(), y.rows()), y.cols());
246 y.topRows(rank) = this->matrixR().topLeftCorner(rank, rank).template triangularView<Upper>().solve(b.topRows(rank));
247 y.bottomRows(y.rows() - rank).setZero();
248
249 // Apply the column permutation
250 if (m_perm_c.size())
251 dest.noalias() = colsPermutation() * y.topRows(cols());
252 else
253 dest = y.topRows(cols());
254
255 m_info = Success;
256 return true;
257 }
258
266 void setPivotThreshold(const RealScalar& threshold) {
267 m_useDefaultThreshold = false;
268 m_threshold = threshold;
269 }
270
275 template <typename Rhs>
277 eigen_assert(m_isInitialized && "The factorization should be called first, use compute()");
278 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, B, false,
279 "SparseQR::solve() : invalid number of rows in the right hand side matrix");
280 return Solve<SparseQR, Rhs>(*this, B.derived());
281 }
282 template <typename Rhs>
283 inline Solve<SparseQR, Rhs> solve(const SparseMatrixBase<Rhs>& B) const {
284 eigen_assert(m_isInitialized && "The factorization should be called first, use compute()");
285 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, B, false,
286 "SparseQR::solve() : invalid number of rows in the right hand side matrix");
287 return Solve<SparseQR, Rhs>(*this, B.derived());
288 }
289
297 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
298 return m_info;
299 }
300
302 inline void _sort_matrix_Q() {
303 if (this->m_isQSorted) return;
304 // The matrix Q is sorted during the transposition
306 this->m_Q = mQrm;
307 this->m_isQSorted = true;
308 }
309
310 protected:
311 bool m_analysisIsok;
312 bool m_factorizationIsok;
313 mutable ComputationInfo m_info;
314 std::string m_lastError;
315 QRMatrixType m_pmat; // Temporary matrix
316 QRMatrixType m_R; // The triangular factor matrix
317 QRMatrixType m_Q; // The orthogonal reflectors
318 ScalarVector m_hcoeffs; // The Householder coefficients
319 PermutationType m_perm_c; // Fill-reducing Column permutation
320 PermutationType m_pivotperm; // The permutation for rank revealing
321 PermutationType m_outputPerm_c; // The final column permutation
322 RealScalar m_threshold; // Threshold to determine null Householder reflections
323 bool m_useDefaultThreshold; // Use default threshold
324 bool m_lastPivotLookAheadSkipped;
325 Index m_nonzeropivots; // Number of non zero pivots found
326 IndexVector m_etree; // Column elimination tree
327 IndexVector m_firstRowElt; // First element in each row
328 bool m_isQSorted; // whether Q is sorted or not
329 bool m_isEtreeOk; // whether the elimination tree match the initial input matrix
330
331 // Bound the temporary dense replacement basis in bytes. The entry count is scaled by sizeof(Scalar), so wider scalar
332 // types inspect fewer replacement directions before keeping the usual default-threshold behavior for the pivot.
333 static constexpr Index PivotLookAheadMaxBasisBytes = Index(32) * Index(1024) * Index(1024);
334 static constexpr Index PivotLookAheadMaxExtraCandidateColumns = 64;
335
336 template <typename, typename>
337 friend struct SparseQR_QProduct;
338};
339
349template <typename MatrixType, typename OrderingType>
351 eigen_assert(
352 mat.isCompressed() &&
353 "SparseQR requires a sparse matrix in compressed mode. Call .makeCompressed() before passing it to SparseQR");
354 // Copy to a column major matrix if the input is rowmajor
355 std::conditional_t<MatrixType::IsRowMajor, QRMatrixType, const MatrixType&> matCpy(mat);
356 // Compute the column fill reducing ordering
357 OrderingType ord;
358 ord(matCpy, m_perm_c);
359 Index n = mat.cols();
360 Index m = mat.rows();
361 Index diagSize = (std::min)(m, n);
362
363 if (!m_perm_c.size()) {
364 m_perm_c.resize(n);
365 m_perm_c.indices().setLinSpaced(n, 0, StorageIndex(n - 1));
366 }
367
368 // Compute the column elimination tree of the permuted matrix
369 m_outputPerm_c = m_perm_c.inverse();
370 internal::coletree(matCpy, m_etree, m_firstRowElt, m_outputPerm_c.indices().data());
371 m_isEtreeOk = true;
372
373 m_R.resize(m, n);
374 m_Q.resize(m, diagSize);
375
376 // Allocate space for nonzero elements: rough estimation
377 m_R.reserve(2 * mat.nonZeros()); // FIXME: get a tighter bound via symbolic factorization using the etree.
378 m_Q.reserve(2 * mat.nonZeros());
379 m_hcoeffs.resize(diagSize);
380 m_analysisIsok = true;
381}
382
390template <typename MatrixType, typename OrderingType>
392 eigen_assert(m_analysisIsok && "analyzePattern() should be called before this step");
393
394 // Reset state from any prior factorize() so info() and lastErrorMessage()
395 // describe this call's outcome, not the previous matrix's.
396 m_info = Success;
397 m_lastError.clear();
398
399 StorageIndex m = StorageIndex(mat.rows());
400 StorageIndex n = StorageIndex(mat.cols());
401 StorageIndex diagSize = (std::min)(m, n);
402 IndexVector mark((std::max)(m, n));
403 mark.setConstant(-1); // Record the visited nodes
404 // Store temporarily the row indexes for the current column of R and Q; the first entry of Qidx is written even when
405 // m == 0.
406 IndexVector Ridx(n), Qidx((std::max)(m, StorageIndex(1)));
407 Index nzcolR, nzcolQ; // Number of nonzero for the current column of R and Q
408 ScalarVector tval(m); // The dense vector used to compute the current column
409 ScalarVector tvalLookAhead(m);
410 Matrix<Scalar, Dynamic, Dynamic> replacementBasis;
411
412 m_R.setZero();
413 m_Q.setZero();
414 m_lastPivotLookAheadSkipped = false;
415 m_pmat = mat;
416 if (!m_isEtreeOk) {
417 m_outputPerm_c = m_perm_c.inverse();
418 internal::coletree(m_pmat, m_etree, m_firstRowElt, m_outputPerm_c.indices().data());
419 m_isEtreeOk = true;
420 }
421
422 // Switch to uncompressed mode so innerNonZeroPtr() exists and can be
423 // permuted consistently with outerIndexPtr().
424 m_pmat.uncompress();
425
426 // Apply the fill-in reducing permutation lazily:
427 {
428 // A compressed column-major input already exposes valid column pointers.
429 // Otherwise snapshot the internal column-major structure before permuting in place.
430 IndexVector originalOuterIndicesCpy;
431 const bool useInputOuterIndices = !MatrixType::IsRowMajor && mat.isCompressed();
432 const StorageIndex* originalOuterIndices = useInputOuterIndices ? mat.outerIndexPtr() : nullptr;
433 if (!useInputOuterIndices) {
434 originalOuterIndicesCpy = IndexVector::Map(m_pmat.outerIndexPtr(), n + 1);
435 originalOuterIndices = originalOuterIndicesCpy.data();
436 }
437
438 for (int i = 0; i < n; i++) {
439 Index p = m_perm_c.size() ? m_perm_c.indices()(i) : i;
440 m_pmat.outerIndexPtr()[p] = originalOuterIndices[i];
441 m_pmat.innerNonZeroPtr()[p] = originalOuterIndices[i + 1] - originalOuterIndices[i];
442 }
443 }
444
445 /* Compute the default threshold as in MatLab, see:
446 * Tim Davis, "Algorithm 915, SuiteSparseQR: Multifrontal Multithreaded Rank-Revealing
447 * Sparse QR Factorization, ACM Trans. on Math. Soft. 38(1), 2011, Page 8:3
448 */
449 RealScalar pivotThreshold;
450 RealScalar max2Norm = RealScalar(0.0);
451 if (m_useDefaultThreshold) {
452 // For scalar types narrower than float (half, bfloat16), compute the default threshold in float:
453 // the squared column norms and the factor 20*(m+n) overflow a 16-bit type for moderate problem
454 // sizes, and 20*(m+n)*epsilon() exceeds 1 for m+n as small as 52 (half) or 7 (bfloat16), which
455 // would reject every pivot and collapse the reported rank to zero.
456 using ThresholdReal = std::conditional_t<(sizeof(RealScalar) < sizeof(float)), float, RealScalar>;
457 if (EIGEN_CONST_CONDITIONAL((std::is_same<ThresholdReal, RealScalar>::value))) {
458 // ThresholdReal == RealScalar (float and wider scalars): keep the historical computation bit-for-bit.
459 for (int j = 0; j < n; j++) max2Norm = numext::maxi(max2Norm, m_pmat.col(j).norm());
460 if (max2Norm == RealScalar(0)) max2Norm = RealScalar(1);
461 pivotThreshold = RealScalar(20 * (m + n)) * max2Norm * NumTraits<RealScalar>::epsilon();
462 } else {
463 ThresholdReal maxColNorm = ThresholdReal(0);
464 for (int j = 0; j < n; j++) {
465 ThresholdReal colSquaredNorm = ThresholdReal(0);
466 for (typename QRMatrixType::InnerIterator it(m_pmat, j); it; ++it)
467 colSquaredNorm += numext::abs2(ThresholdReal(numext::real(it.value()))) +
468 numext::abs2(ThresholdReal(numext::imag(it.value())));
469 maxColNorm = numext::maxi(maxColNorm, numext::sqrt(colSquaredNorm));
470 }
471 if (maxColNorm == ThresholdReal(0)) maxColNorm = ThresholdReal(1);
472 // Convert back to the narrow type only once, after the whole threshold has been formed in float.
473 pivotThreshold = RealScalar(ThresholdReal(20 * (m + n)) * maxColNorm * NumTraits<ThresholdReal>::epsilon());
474 max2Norm = RealScalar(maxColNorm);
475 }
476 } else {
477 pivotThreshold = m_threshold;
478 }
479
480 // Initialize the numerical permutation
481 m_pivotperm.setIdentity(n);
482
483 StorageIndex nonzeroCol = 0; // Record the number of valid pivots
484 if (diagSize > 0) m_Q.startVec(0);
485
486 // Left looking rank-revealing QR factorization: compute a column of R and Q at a time
487 for (StorageIndex col = 0; col < n; ++col) {
488 mark.setConstant(-1);
489 m_R.startVec(col);
490 mark(nonzeroCol) = col;
491 Qidx(0) = nonzeroCol;
492 nzcolR = 0;
493 nzcolQ = 1;
494 bool found_diag = nonzeroCol >= m;
495 tval.setZero();
496
497 // Symbolic factorization: find the nonzero locations of the column k of the factors R and Q, i.e.,
498 // all the nodes (with indexes lower than rank) reachable through the column elimination tree (etree) rooted at node
499 // k. Note: if the diagonal entry does not exist, then its contribution must be explicitly added, thus the trick
500 // with found_diag that permits to do one more iteration on the diagonal element if this one has not been found.
501 for (typename QRMatrixType::InnerIterator itp(m_pmat, col); itp || !found_diag; ++itp) {
502 StorageIndex curIdx = nonzeroCol;
503 if (itp) curIdx = StorageIndex(itp.row());
504 if (curIdx == nonzeroCol) found_diag = true;
505
506 // Get the nonzeros indexes of the current column of R
507 StorageIndex st = m_firstRowElt(curIdx); // The traversal of the etree starts here
508 if (st < 0) {
509 m_lastError = "Empty row found during numerical factorization";
510 m_info = InvalidInput;
511 return;
512 }
513
514 // Traverse the etree
515 Index bi = nzcolR;
516 for (; mark(st) != col; st = m_etree(st)) {
517 Ridx(nzcolR) = st; // Add this row to the list,
518 mark(st) = col; // and mark this row as visited
519 nzcolR++;
520 }
521
522 // Reverse the list to get the topological ordering
523 Index nt = nzcolR - bi;
524 for (Index i = 0; i < nt / 2; i++) std::swap(Ridx(bi + i), Ridx(nzcolR - i - 1));
525
526 // Copy the current (curIdx,pcol) value of the input matrix
527 if (itp)
528 tval(curIdx) = itp.value();
529 else
530 tval(curIdx) = Scalar(0);
531
532 // Compute the pattern of Q(:,k)
533 if (curIdx > nonzeroCol && mark(curIdx) != col) {
534 Qidx(nzcolQ) = curIdx; // Add this row to the pattern of Q,
535 mark(curIdx) = col; // and mark it as visited
536 nzcolQ++;
537 }
538 }
539
540 // Browse all the indexes of R(:,col) in reverse order
541 for (Index i = nzcolR - 1; i >= 0; i--) {
542 Index curIdx = Ridx(i);
543
544 // Apply the curIdx-th householder vector to the current column (temporarily stored into tval)
545 Scalar tdot(0);
546
547 // First compute q' * tval
548 tdot = m_Q.col(curIdx).dot(tval);
549
550 tdot *= m_hcoeffs(curIdx);
551
552 // Then update tval = tval - q * tau
553 tval -= tdot * m_Q.col(curIdx);
554
555 // Detect fill-in for the current column of Q
556 if (m_etree(Ridx(i)) == nonzeroCol) {
557 for (typename QRMatrixType::InnerIterator itq(m_Q, curIdx); itq; ++itq) {
558 StorageIndex iQ = StorageIndex(itq.row());
559 if (mark(iQ) != col) {
560 Qidx(nzcolQ++) = iQ; // Add this row to the pattern of Q,
561 mark(iQ) = col; // and mark it as visited
562 }
563 }
564 }
565 } // End update current column
566
567 Scalar tau = RealScalar(0);
568 RealScalar beta = RealScalar(0);
569
570 if (nonzeroCol < diagSize) {
571 // Compute the Householder reflection that eliminate the current column
572 // FIXME: refactor to use the Householder module's reflector computation.
573 Scalar c0 = nzcolQ ? tval(Qidx(0)) : Scalar(0);
574
575 // First, the squared norm of Q((col+1):m, col)
576 RealScalar sqrNorm = RealScalar(0.);
577 for (Index itq = 1; itq < nzcolQ; ++itq) sqrNorm += numext::abs2(tval(Qidx(itq)));
578 if (sqrNorm == RealScalar(0) && numext::imag(c0) == RealScalar(0)) {
579 beta = numext::real(c0);
580 tval(Qidx(0)) = Scalar(1);
581 } else {
582 beta = numext::sqrt<RealScalar>(numext::abs2(c0) + sqrNorm);
583 if (numext::real(c0) >= RealScalar(0)) beta = -beta;
584 tval(Qidx(0)) = Scalar(1);
585 for (Index itq = 1; itq < nzcolQ; ++itq) tval(Qidx(itq)) /= (c0 - beta);
586 tau = numext::conj((beta - c0) / beta);
587 }
588 }
589
590 // Insert values in R
591 for (Index i = nzcolR - 1; i >= 0; i--) {
592 Index curIdx = Ridx(i);
593 if (curIdx < nonzeroCol) {
594 m_R.insertBackByOuterInnerUnordered(col, curIdx) = tval(curIdx);
595 tval(curIdx) = Scalar(0.);
596 }
597 }
598
599 const RealScalar absBeta = numext::abs(beta);
600 bool hasReplacement = false;
601 const bool canRejectColumn = nonzeroCol + (n - col - 1) >= diagSize;
602 // Gate for examining a pivot as replaceable. The Householder pivot `beta` of a
603 // (nearly) dependent column is a catastrophic-cancellation residual whose exact
604 // magnitude is not reproducible across compilers or FMA-contraction settings, so
605 // this examination gate uses a generous sqrt(epsilon) tolerance rather than
606 // dummy_precision. The rejection below still requires a strictly stronger,
607 // independent replacement set, so a wider gate only changes which pivots are
608 // *examined* (and never rejects a pivot that lacks a replacement). A threshold at
609 // the residual's noise floor would otherwise make the pivoting decision -- and
610 // hence the result -- depend on floating-point contraction.
611 const RealScalar weakPivotTolerance = numext::sqrt(NumTraits<RealScalar>::epsilon());
612 const RealScalar maxReplaceablePivotThreshold = max2Norm * weakPivotTolerance;
613 if (nonzeroCol < diagSize && canRejectColumn && m_useDefaultThreshold && absBeta >= pivotThreshold &&
614 absBeta < maxReplaceablePivotThreshold) {
615 const RealScalar colNorm = m_pmat.col(col).norm();
616 // Per-column replacement gate, mirroring the global max2Norm * weakPivotTolerance threshold.
617 const RealScalar replaceablePivotThreshold = colNorm * weakPivotTolerance;
618 if (absBeta < replaceablePivotThreshold) {
619 const StorageIndex requiredReplacementCount = diagSize - nonzeroCol;
620 const StorageIndex activeRows = m - nonzeroCol;
621 const Index maxReplacementBasisEntries = Index(PivotLookAheadMaxBasisBytes) / Index(sizeof(Scalar));
622 const bool canStoreReplacementBasis =
623 Index(activeRows) <= maxReplacementBasisEntries / Index(requiredReplacementCount);
624 if (canStoreReplacementBasis) {
625 replacementBasis.resize(activeRows, requiredReplacementCount);
626 StorageIndex replacementCount = 0;
627 const StorageIndex maxLookAheadCandidateColumns =
628 (std::min)(n - col - 1, requiredReplacementCount + StorageIndex(PivotLookAheadMaxExtraCandidateColumns));
629 StorageIndex inspectedCandidateCount = 0;
630 StorageIndex candidateCol = col + 1;
631
632 // A small pivot is safe to skip only if later columns can still
633 // provide enough independent replacement pivots after the previously
634 // computed reflectors. Keep this dense look-ahead bounded so sparse
635 // inputs cannot trigger unbounded dense work.
636 for (; candidateCol < n && !hasReplacement && inspectedCandidateCount < maxLookAheadCandidateColumns;
637 ++candidateCol, ++inspectedCandidateCount) {
638 if (m_pmat.col(candidateCol).norm() < replaceablePivotThreshold) continue;
639 tvalLookAhead.setZero();
640 for (typename QRMatrixType::InnerIterator itp(m_pmat, candidateCol); itp; ++itp) {
641 tvalLookAhead(itp.row()) = itp.value();
642 }
643 for (StorageIndex previousCol = 0; previousCol < nonzeroCol; ++previousCol) {
644 Scalar tdot = m_Q.col(previousCol).dot(tvalLookAhead);
645 tdot *= m_hcoeffs(previousCol);
646 tvalLookAhead -= tdot * m_Q.col(previousCol);
647 }
648
649 typename ScalarVector::SegmentReturnType candidateTail = tvalLookAhead.segment(nonzeroCol, activeRows);
650 for (StorageIndex replacement = 0; replacement < replacementCount; ++replacement) {
651 candidateTail -= replacementBasis.col(replacement).dot(candidateTail) * replacementBasis.col(replacement);
652 }
653
654 const RealScalar candidateNorm = candidateTail.norm();
655 if (candidateNorm >= replaceablePivotThreshold) {
656 replacementBasis.col(replacementCount) = candidateTail * (RealScalar(1) / candidateNorm);
657 ++replacementCount;
658 hasReplacement = replacementCount >= requiredReplacementCount;
659 }
660 }
661 if (!hasReplacement && candidateCol < n) m_lastPivotLookAheadSkipped = true;
662 } else {
663 // Retain this fallback for very large problems and wide/custom Scalar types where the best-effort dense
664 // look-ahead would exceed its storage budget.
665 m_lastPivotLookAheadSkipped = true;
666 }
667 }
668 }
669 // If a replacement set was found, the pivot is genuinely replaceable: reject it
670 // (defer the column to the end) independently of `beta`'s exact magnitude.
671 if (nonzeroCol < diagSize && absBeta >= pivotThreshold && !hasReplacement) {
672 m_R.insertBackByOuterInner(col, nonzeroCol) = beta;
673 // The householder coefficient
674 m_hcoeffs(nonzeroCol) = tau;
675 // Record the householder reflections
676 for (Index itq = 0; itq < nzcolQ; ++itq) {
677 Index iQ = Qidx(itq);
678 m_Q.insertBackByOuterInnerUnordered(nonzeroCol, iQ) = tval(iQ);
679 tval(iQ) = Scalar(0.);
680 }
681 nonzeroCol++;
682 if (nonzeroCol < diagSize) m_Q.startVec(nonzeroCol);
683 } else {
684 // Zero pivot found: move implicitly this column to the end
685 for (Index j = nonzeroCol; j < n - 1; j++) std::swap(m_pivotperm.indices()(j), m_pivotperm.indices()[j + 1]);
686
687 // Recompute the column elimination tree
688 internal::coletree(m_pmat, m_etree, m_firstRowElt, m_pivotperm.indices().data());
689 m_isEtreeOk = false;
690 }
691 }
692
693 m_hcoeffs.tail(diagSize - nonzeroCol).setZero();
694
695 // Finalize the column pointers of the sparse matrices R and Q
696 m_Q.finalize();
697 m_Q.makeCompressed();
698 m_R.finalize();
699 m_R.makeCompressed();
700 m_isQSorted = false;
701
702 m_nonzeropivots = nonzeroCol;
703
704 if (nonzeroCol < n) {
705 // Permute the triangular factor to put the 'dead' columns to the end
706 QRMatrixType tempR(m_R);
707 m_R = tempR * m_pivotperm;
708
709 // Update the column permutation
710 m_outputPerm_c = m_outputPerm_c * m_pivotperm;
711 }
712
713 m_isInitialized = true;
714 m_factorizationIsok = true;
715 m_info = Success;
716}
717
718template <typename SparseQRType, typename Derived>
719struct SparseQR_QProduct : ReturnByValue<SparseQR_QProduct<SparseQRType, Derived> > {
720 using MatrixType = typename SparseQRType::QRMatrixType;
721 using Scalar = typename SparseQRType::Scalar;
722 // Get the references
723 SparseQR_QProduct(const SparseQRType& qr, const Derived& other, bool transpose)
724 : m_qr(qr), m_other(other), m_transpose(transpose) {}
725 inline Index rows() const { return m_qr.matrixQ().rows(); }
726 inline Index cols() const { return m_other.cols(); }
727
728 // Assign to a vector
729 template <typename DesType>
730 void evalTo(DesType& res) const {
731 Index m = m_qr.rows();
732 Index n = m_qr.cols();
733 Index diagSize = (std::min)(m, n);
734 res = m_other;
735 if (m_transpose) {
736 EIGEN_INTERNAL_ASSERT_SAME_ROWS_MSG(m_qr.m_Q, m_other, "Non conforming object sizes");
737 // Compute res = Q' * other column by column
738 for (Index j = 0; j < res.cols(); j++) {
739 for (Index k = 0; k < diagSize; k++) {
740 Scalar tau = Scalar(0);
741 tau = m_qr.m_Q.col(k).dot(res.col(j));
742 if (tau == Scalar(0)) continue;
743 tau = tau * m_qr.m_hcoeffs(k);
744 res.col(j) -= tau * m_qr.m_Q.col(k);
745 }
746 }
747 } else {
748 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(m_qr.matrixQ(), m_other, "Non conforming object sizes");
749
750 res.conservativeResize(rows(), cols());
751
752 // Compute res = Q * other column by column
753 for (Index j = 0; j < res.cols(); j++) {
754 Index start_k = internal::is_identity<Derived>::value ? numext::mini(j, diagSize - 1) : diagSize - 1;
755 for (Index k = start_k; k >= 0; k--) {
756 Scalar tau = Scalar(0);
757 tau = m_qr.m_Q.col(k).dot(res.col(j));
758 if (tau == Scalar(0)) continue;
759 tau = tau * numext::conj(m_qr.m_hcoeffs(k));
760 res.col(j) -= tau * m_qr.m_Q.col(k);
761 }
762 }
763 }
764 }
765
766 const SparseQRType& m_qr;
767 const Derived& m_other;
768 bool m_transpose; // TODO: rename to m_adjoint; this flag controls adjoint application.
769};
770
771template <typename SparseQRType>
772struct SparseQRMatrixQReturnType : public EigenBase<SparseQRMatrixQReturnType<SparseQRType> > {
773 using Scalar = typename SparseQRType::Scalar;
774 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic>;
775 enum { RowsAtCompileTime = Dynamic, ColsAtCompileTime = Dynamic };
776 explicit SparseQRMatrixQReturnType(const SparseQRType& qr) : m_qr(qr) {}
777 template <typename Derived>
778 SparseQR_QProduct<SparseQRType, Derived> operator*(const MatrixBase<Derived>& other) {
779 return SparseQR_QProduct<SparseQRType, Derived>(m_qr, other.derived(), false);
780 }
781 // To use for operations with the adjoint of Q
782 SparseQRMatrixQTransposeReturnType<SparseQRType> adjoint() const {
783 return SparseQRMatrixQTransposeReturnType<SparseQRType>(m_qr);
784 }
785 inline Index rows() const { return m_qr.rows(); }
786 inline Index cols() const { return m_qr.rows(); }
787 // To use for operations with the transpose of Q. FIXME: currently identical to adjoint(); specialize for complex.
788 SparseQRMatrixQTransposeReturnType<SparseQRType> transpose() const {
789 return SparseQRMatrixQTransposeReturnType<SparseQRType>(m_qr);
790 }
791 const SparseQRType& m_qr;
792};
793
794// TODO: rename to SparseQRMatrixQAdjointReturnType; this represents the adjoint of Q.
795template <typename SparseQRType>
796struct SparseQRMatrixQTransposeReturnType {
797 explicit SparseQRMatrixQTransposeReturnType(const SparseQRType& qr) : m_qr(qr) {}
798 template <typename Derived>
799 SparseQR_QProduct<SparseQRType, Derived> operator*(const MatrixBase<Derived>& other) {
800 return SparseQR_QProduct<SparseQRType, Derived>(m_qr, other.derived(), true);
801 }
802 const SparseQRType& m_qr;
803};
804
805namespace internal {
806
807template <typename SparseQRType>
808struct evaluator_traits<SparseQRMatrixQReturnType<SparseQRType> > {
809 using MatrixType = typename SparseQRType::MatrixType;
810 using Kind = typename storage_kind_to_evaluator_kind<typename MatrixType::StorageKind>::Kind;
811 using Shape = SparseShape;
812};
813
814template <typename DstXprType, typename SparseQRType>
815struct Assignment<DstXprType, SparseQRMatrixQReturnType<SparseQRType>,
816 internal::assign_op<typename DstXprType::Scalar, typename DstXprType::Scalar>, Sparse2Sparse> {
817 using SrcXprType = SparseQRMatrixQReturnType<SparseQRType>;
818 using Scalar = typename DstXprType::Scalar;
819 using StorageIndex = typename DstXprType::StorageIndex;
820 static void run(DstXprType& dst, const SrcXprType& src, const internal::assign_op<Scalar, Scalar>& /*func*/) {
821 typename DstXprType::PlainObject idMat(src.rows(), src.cols());
822 idMat.setIdentity();
823 // Sort the sparse householder reflectors if needed
824 const_cast<SparseQRType*>(&src.m_qr)->_sort_matrix_Q();
825 dst = SparseQR_QProduct<SparseQRType, DstXprType>(src.m_qr, idMat, false);
826 }
827};
828
829template <typename DstXprType, typename SparseQRType>
830struct Assignment<DstXprType, SparseQRMatrixQReturnType<SparseQRType>,
831 internal::assign_op<typename DstXprType::Scalar, typename DstXprType::Scalar>, Sparse2Dense> {
832 using SrcXprType = SparseQRMatrixQReturnType<SparseQRType>;
833 using Scalar = typename DstXprType::Scalar;
834 using StorageIndex = typename DstXprType::StorageIndex;
835 static void run(DstXprType& dst, const SrcXprType& src, const internal::assign_op<Scalar, Scalar>& /*func*/) {
836 dst = src.m_qr.matrixQ() * DstXprType::Identity(src.m_qr.rows(), src.m_qr.rows());
837 }
838};
839
840} // end namespace internal
841
842} // end namespace Eigen
843
844#endif
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
NoAlias< Derived, Eigen::MatrixBase > noalias()
Definition NoAlias.h:97
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
Index size() const
Definition PermutationMatrix.h:140
Permutation matrix.
Definition PermutationMatrix.h:346
Derived & setConstant(Index size, const Scalar &val)
Definition CwiseNullaryOp.h:349
constexpr const Scalar * data() const
Definition PlainObjectBase.h:261
Derived & setZero(Index size)
Definition CwiseNullaryOp.h:536
constexpr void resize(Index rows, Index cols)
Definition PlainObjectBase.h:282
Pseudo expression representing a solving operation.
Definition Solve.h:63
Base class of any sparse matrices or sparse expressions.
Definition SparseMatrixBase.h:31
constexpr FixedBlockXpr<...,... >::Type topLeftCorner(NRowsType cRows, NColsType cCols)
Definition SparseMatrixBase.h:287
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
Sparse left-looking QR factorization with numerical column pivoting.
Definition SparseQR.h:95
const PermutationType & colsPermutation() const
Definition SparseQR.h:207
void setPivotThreshold(const RealScalar &threshold)
Definition SparseQR.h:266
void analyzePattern(const MatrixType &mat)
Preprocessing step of a QR factorization.
Definition SparseQR.h:350
void factorize(const MatrixType &mat)
Performs the numerical QR factorization of the input matrix.
Definition SparseQR.h:391
SparseQR(const MatrixType &mat)
Definition SparseQR.h:129
Index cols() const
Definition SparseQR.h:158
const QRMatrixType & matrixR() const
Definition SparseQR.h:173
SparseQRMatrixQReturnType< SparseQR > matrixQ() const
Definition SparseQR.h:202
Index rows() const
Definition SparseQR.h:154
std::string lastErrorMessage() const
Definition SparseQR.h:228
void compute(const MatrixType &mat)
Definition SparseQR.h:145
Solve< SparseQR, Rhs > solve(const MatrixBase< Rhs > &B) const
Definition SparseQR.h:276
bool lastPivotLookAheadSkipped() const
Definition SparseQR.h:220
ComputationInfo info() const
Reports whether previous computation was successful.
Definition SparseQR.h:296
Index rank() const
Definition SparseQR.h:179
ComputationInfo
Definition Constants.h:455
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457
Definition EigenBase.h:34
constexpr Derived & derived()
Definition EigenBase.h:50