392 eigen_assert(m_analysisIsok &&
"analyzePattern() should be called before this step");
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));
406 IndexVector Ridx(n), Qidx((std::max)(m, StorageIndex(1)));
407 Index nzcolR, nzcolQ;
408 ScalarVector tval(m);
409 ScalarVector tvalLookAhead(m);
414 m_lastPivotLookAheadSkipped =
false;
417 m_outputPerm_c = m_perm_c.inverse();
418 internal::coletree(m_pmat, m_etree, m_firstRowElt, m_outputPerm_c.indices().data());
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();
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];
449 RealScalar pivotThreshold;
450 RealScalar max2Norm = RealScalar(0.0);
451 if (m_useDefaultThreshold) {
456 using ThresholdReal = std::conditional_t<(
sizeof(RealScalar) <
sizeof(float)),
float, RealScalar>;
457 if (EIGEN_CONST_CONDITIONAL((std::is_same<ThresholdReal, RealScalar>::value))) {
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();
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));
471 if (maxColNorm == ThresholdReal(0)) maxColNorm = ThresholdReal(1);
473 pivotThreshold = RealScalar(ThresholdReal(20 * (m + n)) * maxColNorm * NumTraits<ThresholdReal>::epsilon());
474 max2Norm = RealScalar(maxColNorm);
477 pivotThreshold = m_threshold;
481 m_pivotperm.setIdentity(n);
483 StorageIndex nonzeroCol = 0;
484 if (diagSize > 0) m_Q.startVec(0);
487 for (StorageIndex col = 0; col < n; ++col) {
490 mark(nonzeroCol) = col;
491 Qidx(0) = nonzeroCol;
494 bool found_diag = nonzeroCol >= m;
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;
507 StorageIndex st = m_firstRowElt(curIdx);
509 m_lastError =
"Empty row found during numerical factorization";
516 for (; mark(st) != col; st = m_etree(st)) {
523 Index nt = nzcolR - bi;
524 for (Index i = 0; i < nt / 2; i++) std::swap(Ridx(bi + i), Ridx(nzcolR - i - 1));
528 tval(curIdx) = itp.value();
530 tval(curIdx) = Scalar(0);
533 if (curIdx > nonzeroCol && mark(curIdx) != col) {
534 Qidx(nzcolQ) = curIdx;
541 for (Index i = nzcolR - 1; i >= 0; i--) {
542 Index curIdx = Ridx(i);
548 tdot = m_Q.col(curIdx).dot(tval);
550 tdot *= m_hcoeffs(curIdx);
553 tval -= tdot * m_Q.col(curIdx);
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) {
567 Scalar tau = RealScalar(0);
568 RealScalar beta = RealScalar(0);
570 if (nonzeroCol < diagSize) {
573 Scalar c0 = nzcolQ ? tval(Qidx(0)) : Scalar(0);
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);
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);
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.);
599 const RealScalar absBeta = numext::abs(beta);
600 bool hasReplacement =
false;
601 const bool canRejectColumn = nonzeroCol + (n - col - 1) >= diagSize;
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();
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;
636 for (; candidateCol < n && !hasReplacement && inspectedCandidateCount < maxLookAheadCandidateColumns;
637 ++candidateCol, ++inspectedCandidateCount) {
638 if (m_pmat.col(candidateCol).norm() < replaceablePivotThreshold)
continue;
640 for (
typename QRMatrixType::InnerIterator itp(m_pmat, candidateCol); itp; ++itp) {
641 tvalLookAhead(itp.row()) = itp.value();
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);
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);
654 const RealScalar candidateNorm = candidateTail.norm();
655 if (candidateNorm >= replaceablePivotThreshold) {
656 replacementBasis.col(replacementCount) = candidateTail * (RealScalar(1) / candidateNorm);
658 hasReplacement = replacementCount >= requiredReplacementCount;
661 if (!hasReplacement && candidateCol < n) m_lastPivotLookAheadSkipped =
true;
665 m_lastPivotLookAheadSkipped =
true;
671 if (nonzeroCol < diagSize && absBeta >= pivotThreshold && !hasReplacement) {
672 m_R.insertBackByOuterInner(col, nonzeroCol) = beta;
674 m_hcoeffs(nonzeroCol) = tau;
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.);
682 if (nonzeroCol < diagSize) m_Q.startVec(nonzeroCol);
685 for (Index j = nonzeroCol; j < n - 1; j++) std::swap(m_pivotperm.indices()(j), m_pivotperm.indices()[j + 1]);
688 internal::coletree(m_pmat, m_etree, m_firstRowElt, m_pivotperm.indices().data());
693 m_hcoeffs.tail(diagSize - nonzeroCol).setZero();
697 m_Q.makeCompressed();
699 m_R.makeCompressed();
702 m_nonzeropivots = nonzeroCol;
704 if (nonzeroCol < n) {
706 QRMatrixType tempR(m_R);
707 m_R = tempR * m_pivotperm;
710 m_outputPerm_c = m_outputPerm_c * m_pivotperm;
713 m_isInitialized =
true;
714 m_factorizationIsok =
true;