10#ifndef EIGEN_MULTIFRONTAL_LDLT_H
11#define EIGEN_MULTIFRONTAL_LDLT_H
14#include "./InternalHeaderCheck.h"
77template <
typename MatrixType_,
int UpLo_ = Lower,
typename Ordering_ = AMDOrdering<
typename MatrixType_::StorageIndex>>
80 using Base::m_isInitialized;
83 using Base::_solve_impl;
85 using MatrixType = MatrixType_;
86 using OrderingType = Ordering_;
87 using Scalar =
typename MatrixType::Scalar;
88 using RealScalar =
typename NumTraits<Scalar>::Real;
89 using StorageIndex =
typename MatrixType::StorageIndex;
95 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
96 EIGEN_STATIC_ASSERT(UpLo_ ==
Lower || UpLo_ ==
Upper, MULTIFRONTALLDLT_ACCEPTS_UPPER_AND_LOWER_MODE_ONLY)
98 static constexpr int UpLo = UpLo_;
99 static constexpr int ColsAtCompileTime = Dynamic;
100 static constexpr int MaxColsAtCompileTime = Dynamic;
115 eigen_assert(threshold > RealScalar(0) && threshold <= RealScalar(0.5));
116 m_threshold = threshold;
143 void factorize(
const MatrixType& matrix);
155 eigen_assert(m_isInitialized &&
"Decomposition is not initialized.");
159 Index rows()
const {
return m_P.
rows(); }
160 Index cols()
const {
return m_P.
cols(); }
164 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading D.");
171 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading D.");
172 return m_subdiagonal;
198 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the permutation.");
208 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the permutation.");
259 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the inertia.");
260 return m_numPositive;
265 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the inertia.");
266 return m_numNegative;
277 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the inertia.");
291 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading the size of L.");
295#ifndef EIGEN_PARSED_BY_DOXYGEN
297 template <
typename Rhs,
typename Dest>
311 static constexpr Index kPanelWidth = 32;
313 static constexpr Index kBlockedFrontMinOrder = 32;
316 static constexpr Index kVectorizedMinLength = 16;
318 static constexpr Index kSmallFrontMaxOrder = 8;
321 static constexpr Index kExtendAddMinRunLength = 4;
324 static constexpr Index kDenseSolveMinSize = 4096;
330 template <
typename T>
332 std::vector<T, aligned_allocator<T>> storage;
333 std::size_t size = 0;
336 T* push(std::size_t count) {
337 if (storage.size() < size + count) storage.
resize(numext::maxi(size + count, 2 * storage.size()));
338 T* end = storage.data() + size;
344 T* top(std::size_t count) {
return storage.data() + (size - count); }
346 void pop(std::size_t count) { size -= count; }
347 void reserve(std::size_t count) {
348 if (storage.size() < count) storage.resize(count);
350 void clear() { size = 0; }
364 struct FactoredFront {
365 StorageIndex numPivots;
374 static std::size_t rectangleSize(Index rows, Index cols) {
375 return static_cast<std::size_t
>(rows) *
static_cast<std::size_t
>(cols);
379 static std::size_t packedSize(Index n) {
return static_cast<std::size_t
>(n) * (
static_cast<std::size_t
>(n) + 1) / 2; }
382 static std::size_t factorSize(Index numPivots, Index order) {
383 return rectangleSize(numPivots, order) - packedSize(numPivots);
387 static void subtractScaled(Scalar* EIGEN_RESTRICT dst,
const Scalar* EIGEN_RESTRICT src,
const Scalar& alpha,
389 if (length < kVectorizedMinLength) {
390 for (Index i = 0; i < length; ++i) dst[i] -= src[i] * alpha;
392 VectorMap(dst, length).noalias() -= ConstVectorMap(src, length) * alpha;
397 static void subtractScaled(Scalar* EIGEN_RESTRICT dst,
const Scalar* EIGEN_RESTRICT src1,
const Scalar& alpha1,
398 const Scalar* EIGEN_RESTRICT src2,
const Scalar& alpha2, Index length) {
399 if (length < kVectorizedMinLength) {
400 for (Index i = 0; i < length; ++i) dst[i] -= src1[i] * alpha1 + src2[i] * alpha2;
402 VectorMap(dst, length).noalias() -= ConstVectorMap(src1, length) * alpha1 + ConstVectorMap(src2, length) * alpha2;
407 static void addTo(Scalar* EIGEN_RESTRICT dst,
const Scalar* EIGEN_RESTRICT src, Index length) {
408 if (length < kVectorizedMinLength) {
409 for (Index i = 0; i < length; ++i) dst[i] += src[i];
411 VectorMap(dst, length).noalias() += ConstVectorMap(src, length);
416 static RealScalar largestMagnitude(
const Scalar* column, Index length) {
417 if (length >= kVectorizedMinLength)
return ConstVectorMap(column, length).cwiseAbs().maxCoeff();
418 RealScalar result(0);
419 for (Index i = 0; i < length; ++i) result = numext::maxi(result, RealScalar(numext::abs(column[i])));
424 StorageIndex* frontRows(Index order) {
return m_factorRows.top(
static_cast<std::size_t
>(order)); }
435 ScaledBlock(
const RealScalar& d1,
const RealScalar& d2,
const RealScalar& absD21)
436 : scale(numext::maxi(numext::maxi(RealScalar(numext::abs(d1)), RealScalar(numext::abs(d2))), absD21)),
439 absB(absD21 / scale),
440 det(a * c - absB * absB) {}
446 template <
typename Function>
447 static void visitTriangle(
const MatrixType& matrix, Function&& function) {
449 const Index outerSize = matrix.outerSize();
450 for (Index outer = 0; outer < outerSize; ++outer) {
451 for (
typename MatrixType::InnerIterator it(matrix, outer); it; ++it, ++position) {
452 const Index row = it.row();
453 const Index col = it.col();
454 if (UpLo_ ==
Lower ? row >= col : row <= col) function(row, col, position);
462 static double maxExplicitZeroFraction(Index pivots) {
return pivots < 4 ? 0.3 : (pivots < 32 ? 0.1 : 0.02); }
468 void mergeRelaxedFronts(
const std::vector<StorageIndex>& frontParent,
const std::vector<StorageIndex>& frontBelow,
469 std::vector<StorageIndex>& columnFront, std::vector<StorageIndex>& newColumn);
472 Scalar* appendFactor(Index s, Index numPivots, Index order);
480 RealScalar frontColumnMax(Index order, Index active, Index j, Index skip)
const;
484 bool frontColumnIsZero(Index order, Index active, Index j)
const;
488 Index largestFullySummed(Index order, Index active, Index fullySummed, Index j, RealScalar& rest)
const;
493 EIGEN_ALWAYS_INLINE
void scatterAdd(Index order,
const Scalar* block,
const StorageIndex* map, Index childOrder) {
494 FrontMap front(m_front.data(), order, order);
495 for (Index j = 0; j < childOrder; ++j) {
496 Scalar* column = &front.coeffRef(0, map[j]);
497 for (Index i = j; i < childOrder; ++i) column[map[i]] += *block++;
500 void extendAdd(Index order,
const Scalar* block,
const StorageIndex* map, Index childOrder);
504 Index factorFront(Index order, Index fullySummed,
bool isRoot);
509 EIGEN_ALWAYS_INLINE
bool factorOnePivotFront(Index s, Index order,
bool isRoot);
514 void pushToParent(Index s, Index order, Index fullySummed, Index numPivots);
517 void swapFront(Index order, Index a, Index b);
520 void eliminate1x1(Index order, Index k, Index panelEnd);
521 void eliminate2x2(Index order, Index k, Index panelEnd);
524 void updateTrailing(Index order, Index firstPivot, Index numPivots, Index panelEnd);
527 RealScalar m_threshold = RealScalar(0.01);
534 std::vector<StorageIndex> m_perm;
535 std::vector<StorageIndex> m_invPerm;
537 std::vector<StorageIndex> m_frontColumns;
539 std::vector<StorageIndex> m_frontParent;
541 std::vector<std::size_t> m_belowStart;
543 std::vector<StorageIndex> m_frontRowList;
546 std::vector<StorageIndex> m_belowToParent;
548 std::vector<std::size_t> m_childStart;
549 std::vector<StorageIndex> m_children;
551 std::vector<std::size_t> m_assemblyStart;
552 std::vector<Assembly> m_assembly;
554 std::size_t m_numValues = 0;
556 std::size_t m_symbolicFactorSize = 0;
557 std::size_t m_symbolicStackSize = 0;
558 Index m_symbolicFrontOrder = 0;
563 std::vector<Scalar> m_values;
565 std::vector<Scalar, aligned_allocator<Scalar>> m_front;
567 std::vector<Scalar, aligned_allocator<Scalar>> m_pivotScratch;
569 std::vector<StorageIndex> m_childMap;
571 std::vector<StorageIndex> m_childRunEnd;
573 WorkStack<Scalar> m_stack;
575 std::vector<StorageIndex> m_numDelayed;
577 WorkStack<Scalar> m_L;
580 WorkStack<StorageIndex> m_factorRows;
581 std::vector<FactoredFront> m_factoredFronts;
583 std::vector<ScaledBlock> m_blocks;
585 VectorType m_subdiagonal;
587 PermutationType m_Pinv;
589 std::vector<StorageIndex> m_pivots;
590 Index m_LNonZeros = 0;
591 Index m_numPivots = 0;
592 Index m_numPositive = 0;
593 Index m_numNegative = 0;
595 Index m_maxFrontOrder = 0;
596 bool m_hasZeroPivot =
false;
599template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
600constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::UpLo;
601template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
602constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::ColsAtCompileTime;
603template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
604constexpr int MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::MaxColsAtCompileTime;
606template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
607void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::mergeRelaxedFronts(
const std::vector<StorageIndex>& frontParent,
608 const std::vector<StorageIndex>& frontBelow,
609 std::vector<StorageIndex>& columnFront,
610 std::vector<StorageIndex>& newColumn) {
611 const auto toStorageIndex = [](
auto value) {
return internal::convert_index<StorageIndex>(value); };
612 constexpr StorageIndex none(-1);
613 const Index size =
static_cast<Index
>(columnFront.size());
614 const Index numFronts =
static_cast<Index
>(m_frontColumns.size()) - 1;
615 newColumn.resize(size);
616 std::iota(newColumn.begin(), newColumn.end(), StorageIndex(0));
618 const auto storedEntries = [](Index pivots, Index below) {
619 return factorSize(pivots, pivots + below) +
static_cast<std::size_t
>(pivots);
624 std::vector<StorageIndex> mergedInto(numFronts, none);
625 std::vector<StorageIndex> numPivots(numFronts);
627 std::vector<std::size_t> numEntries(numFronts);
628 for (Index s = 0; s < numFronts; ++s) {
629 numPivots[s] = m_frontColumns[s + 1] - m_frontColumns[s];
630 numEntries[s] = storedEntries(numPivots[s], frontBelow[s]);
633 for (Index s = 0; s < numFronts; ++s) {
634 const StorageIndex p = frontParent[s];
635 if (p == none)
continue;
636 const Index pivots = numPivots[s] + numPivots[p];
637 const std::size_t stored = storedEntries(pivots, frontBelow[p]);
638 const std::size_t entries = numEntries[s] + numEntries[p];
639 if (
double(stored - entries) <= maxExplicitZeroFraction(pivots) *
double(stored)) {
641 numPivots[p] = toStorageIndex(pivots);
642 numEntries[p] = entries;
646 if (numMerged == 0)
return;
649 std::vector<StorageIndex> merged(numFronts);
650 const StorageIndex numMergedFronts = toStorageIndex(numFronts - numMerged);
652 StorageIndex next = numMergedFronts;
653 for (Index s = numFronts - 1; s >= 0; --s) {
654 merged[s] = mergedInto[s] == none ? --next : merged[mergedInto[s]];
661 IndexVectorType rootedParent(numMergedFronts);
662 for (Index s = 0; s < numFronts; ++s) {
663 if (mergedInto[s] == none) {
664 rootedParent[merged[s]] = frontParent[s] == none ? numMergedFronts : merged[frontParent[s]];
667 IndexVectorType postorder;
668 internal::treePostorder(numMergedFronts, rootedParent, postorder);
670 std::vector<StorageIndex> firstColumn(numMergedFronts + 1, 0);
671 for (Index s = 0; s < numFronts; ++s) {
672 if (mergedInto[s] == none) firstColumn[postorder[merged[s]] + 1] = numPivots[s];
674 for (Index s = 0; s < numMergedFronts; ++s) firstColumn[s + 1] += firstColumn[s];
677 std::vector<StorageIndex> newColumnFront(size);
679 std::vector<StorageIndex> next(firstColumn.begin(), firstColumn.end() - 1);
680 for (Index s = 0; s < numFronts; ++s) {
681 const StorageIndex front = postorder[merged[s]];
682 const Index end = m_frontColumns[s + 1];
683 for (Index j = m_frontColumns[s]; j < end; ++j) {
684 newColumn[j] = next[front]++;
685 newColumnFront[newColumn[j]] = front;
690 columnFront.swap(newColumnFront);
691 m_frontColumns.swap(firstColumn);
692 for (Index i = 0; i < size; ++i) {
693 m_perm[i] = newColumn[m_perm[i]];
694 m_invPerm[m_perm[i]] = toStorageIndex(i);
698template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
700 eigen_assert(matrix.rows() == matrix.cols() &&
"The matrix must be square.");
702 const Index size = matrix.rows();
708 constexpr bool kUseAMDFastPath = std::is_same<OrderingType, AMDOrdering<StorageIndex>>::value;
709 internal::simplicial_cholesky_amd_dispatch<kUseAMDFastPath>::template run<UpLo_, false, OrderingType>(matrix, C,
712 const auto toStorageIndex = [](
auto value) {
return internal::convert_index<StorageIndex>(value); };
713 std::vector<StorageIndex> ordered(size);
714 for (Index i = 0; i < size; ++i) ordered[Pinv.
size() > 0 ? Index(Pinv.
indices()(i)) : i] = toStorageIndex(i);
718 internal::permute_symm_to_symm<UpLo_, Upper, false>(matrix, upper, Pinv.
size() > 0 ? ordered.data() :
nullptr);
721 constexpr StorageIndex none(-1);
722 std::vector<StorageIndex> parent(size);
724 std::vector<StorageIndex> ancestors(size);
725 internal::simpl_chol_helper<Scalar, StorageIndex>::calc_etree(toStorageIndex(size), upper, parent.data(),
730 IndexVectorType rootedParent(size);
731 for (Index j = 0; j < size; ++j) rootedParent[j] = parent[j] == none ? toStorageIndex(size) : parent[j];
736 IndexVectorType postorder;
737 internal::treePostorder(toStorageIndex(size), rootedParent, postorder, internal::PostorderChildren::Decreasing);
740 m_invPerm.resize(size);
741 for (Index i = 0; i < size; ++i) {
742 m_perm[i] = postorder[ordered[i]];
743 m_invPerm[m_perm[i]] = toStorageIndex(i);
748 using SymbolicHelper = internal::simpl_chol_helper<Scalar, StorageIndex>;
749 const StorageIndex n = toStorageIndex(size);
750 std::vector<StorageIndex> rowStart(size + 1, 0);
751 SymbolicHelper::calc_hadj_outer(n, upper, rowStart.data());
752 std::vector<StorageIndex> rowColumns(rowStart[size]);
753 std::vector<StorageIndex> count(size);
755 std::vector<StorageIndex> work(size);
756 IndexVectorType previousLeaf = IndexVectorType::Constant(size, none);
757 SymbolicHelper::calc_hadj_inner(n, upper, rowStart.data(), rowColumns.data(), work.data());
758 IndexVectorType inPostorder(size);
759 for (Index j = 0; j < size; ++j) inPostorder[postorder[j]] = toStorageIndex(j);
760 SymbolicHelper::calc_colcount(n, rowStart.data(), rowColumns.data(), parent.data(), previousLeaf.
data(),
761 work.data(), inPostorder.
data(), count.data(),
true);
767 std::vector<StorageIndex> columnParent(size, none);
768 std::vector<StorageIndex> columnBelow(size);
769 std::vector<StorageIndex> numChildren(size, 0);
770 for (Index j = 0; j < size; ++j) {
771 columnBelow[postorder[j]] = count[j];
772 if (parent[j] != none) {
773 columnParent[postorder[j]] = postorder[parent[j]];
774 ++numChildren[postorder[parent[j]]];
777 m_frontColumns.clear();
778 std::vector<StorageIndex> columnFront(size);
779 for (Index j = 0; j < size; ++j) {
781 j > 0 && columnParent[j - 1] == j && numChildren[j] == 1 && columnBelow[j - 1] == columnBelow[j] + 1;
782 if (!extends) m_frontColumns.push_back(toStorageIndex(j));
783 columnFront[j] = toStorageIndex(m_frontColumns.size() - 1);
785 m_frontColumns.push_back(n);
787 const Index numFundamental =
static_cast<Index
>(m_frontColumns.size()) - 1;
788 std::vector<StorageIndex> frontParent(numFundamental);
789 std::vector<StorageIndex> frontBelow(numFundamental);
790 for (Index s = 0; s < numFundamental; ++s) {
791 const StorageIndex last = m_frontColumns[s + 1] - 1;
792 frontParent[s] = columnParent[last] == none ? none : columnFront[columnParent[last]];
793 frontBelow[s] = columnBelow[last];
795 std::vector<StorageIndex> newColumn;
796 mergeRelaxedFronts(frontParent, frontBelow, columnFront, newColumn);
797 for (Index j = 0; j < size; ++j) postorder[j] = newColumn[postorder[j]];
799 const Index numFronts =
static_cast<Index
>(m_frontColumns.size()) - 1;
801 const IndexVectorType& columnOf = postorder;
802 std::vector<StorageIndex> orderedColumn(size);
803 for (Index j = 0; j < size; ++j) orderedColumn[columnOf[j]] = toStorageIndex(j);
806 m_frontParent.assign(numFronts, none);
807 m_childStart.assign(numFronts + 1, 0);
808 for (Index s = 0; s < numFronts; ++s) {
809 const StorageIndex last = orderedColumn[m_frontColumns[s + 1] - 1];
810 if (parent[last] != none) {
811 m_frontParent[s] = columnFront[columnOf[parent[last]]];
812 ++m_childStart[m_frontParent[s] + 1];
815 for (Index s = 0; s < numFronts; ++s) m_childStart[s + 1] += m_childStart[s];
816 m_children.resize(m_childStart[numFronts]);
818 std::vector<std::size_t> next(m_childStart.begin(), m_childStart.end() - 1);
819 for (Index s = 0; s < numFronts; ++s) {
820 if (m_frontParent[s] != none) m_children[next[m_frontParent[s]]++] = toStorageIndex(s);
826 m_belowStart.assign(numFronts + 1, 0);
827 m_frontRowList.clear();
829 std::size_t numRows =
static_cast<std::size_t
>(size);
830 for (Index s = 0; s < numFronts; ++s) {
831 numRows +=
static_cast<std::size_t
>(count[orderedColumn[m_frontColumns[s + 1] - 1]]);
833 m_frontRowList.reserve(numRows);
836 std::vector<StorageIndex> mark(size, none);
837 for (Index s = 0; s < numFronts; ++s) {
838 const StorageIndex front = toStorageIndex(s);
839 const StorageIndex end = m_frontColumns[s + 1];
840 for (StorageIndex j = m_frontColumns[s]; j < end; ++j) m_frontRowList.push_back(j);
841 const std::size_t first = m_frontRowList.size();
842 const auto add = [&](StorageIndex row) {
843 if (row >= end && mark[row] != front) {
845 m_frontRowList.push_back(row);
848 for (StorageIndex j = m_frontColumns[s]; j < end; ++j) {
849 const StorageIndex column = orderedColumn[j];
850 const StorageIndex rowEnd = rowStart[column + 1];
851 for (StorageIndex k = rowStart[column]; k < rowEnd; ++k) add(columnOf[rowColumns[k]]);
853 const std::size_t childEnd = m_childStart[s + 1];
854 for (std::size_t c = m_childStart[s]; c < childEnd; ++c) {
855 const StorageIndex child = m_children[c];
856 const std::size_t childFirst = m_belowStart[child] +
static_cast<std::size_t
>(m_frontColumns[child + 1]);
857 const std::size_t childLast = m_belowStart[child + 1] +
static_cast<std::size_t
>(m_frontColumns[child + 1]);
858 for (std::size_t k = childFirst; k < childLast; ++k) add(m_frontRowList[k]);
860 m_belowStart[s + 1] = m_belowStart[s] + (m_frontRowList.size() - first);
861 eigen_internal_assert(m_belowStart[s + 1] - m_belowStart[s] ==
862 static_cast<std::size_t
>(count[orderedColumn[end - 1]]));
868 const auto belowRows = [&](Index s) {
869 return m_frontRowList.begin() +
static_cast<std::ptrdiff_t
>(m_belowStart[s] + m_frontColumns[s + 1]);
871 std::vector<std::size_t> rowFrontStart(size + 1, 0);
872 for (Index s = 0; s < numFronts; ++s) {
873 const auto end = belowRows(s) +
static_cast<std::ptrdiff_t
>(m_belowStart[s + 1] - m_belowStart[s]);
874 for (
auto row = belowRows(s); row != end; ++row) {
875 ++rowFrontStart[*row + 1];
878 for (Index i = 0; i < size; ++i) rowFrontStart[i + 1] += rowFrontStart[i];
879 std::vector<StorageIndex> rowFronts(rowFrontStart[size]);
881 std::vector<std::size_t> next(rowFrontStart.begin(), rowFrontStart.end() - 1);
882 for (Index s = 0; s < numFronts; ++s) {
883 const auto end = belowRows(s) +
static_cast<std::ptrdiff_t
>(m_belowStart[s + 1] - m_belowStart[s]);
884 for (
auto row = belowRows(s); row != end; ++row) {
885 rowFronts[next[*row]++] = toStorageIndex(s);
889 std::vector<std::size_t> next(numFronts);
890 for (Index s = 0; s < numFronts; ++s) next[s] = m_belowStart[s] + static_cast<std::size_t>(m_frontColumns[s + 1]);
891 for (Index i = 0; i < size; ++i) {
892 const std::size_t end = rowFrontStart[i + 1];
893 for (std::size_t k = rowFrontStart[i]; k < end; ++k) {
894 m_frontRowList[next[rowFronts[k]]++] = toStorageIndex(i);
900 m_assemblyStart.assign(numFronts + 1, 0);
901 m_numValues =
static_cast<std::size_t
>(matrix.nonZeros());
902 visitTriangle(matrix, [&](Index row, Index col, Index) {
903 ++m_assemblyStart[columnFront[numext::mini(m_perm[row], m_perm[col])] + 1];
905 for (Index s = 0; s < numFronts; ++s) m_assemblyStart[s + 1] += m_assemblyStart[s];
906 m_assembly.resize(m_assemblyStart[numFronts]);
908 std::vector<std::size_t> next(m_assemblyStart.begin(), m_assemblyStart.end() - 1);
909 visitTriangle(matrix, [&](Index row, Index col, Index value) {
910 const StorageIndex i = m_perm[row];
911 const StorageIndex j = m_perm[col];
912 const StorageIndex s = columnFront[numext::mini(i, j)];
913 m_assembly[next[s]++] = Assembly{toStorageIndex(value), numext::maxi(i, j),
914 toStorageIndex(numext::mini(i, j) - m_frontColumns[s]), i < j};
920 m_belowToParent.resize(m_belowStart[numFronts]);
922 std::vector<StorageIndex> position(size);
923 for (Index s = 0; s < numFronts; ++s) {
924 const StorageIndex first = m_frontColumns[s];
925 const StorageIndex end = m_frontColumns[s + 1];
926 for (StorageIndex j = first; j < end; ++j) position[j] = j - first;
927 const std::size_t rows = m_belowStart[s] +
static_cast<std::size_t
>(end);
928 for (std::size_t k = 0; k < m_belowStart[s + 1] - m_belowStart[s]; ++k) {
929 position[m_frontRowList[rows + k]] = toStorageIndex(Index(end - first) + Index(k));
931 for (std::size_t c = m_childStart[s]; c < m_childStart[s + 1]; ++c) {
932 const StorageIndex child = m_children[c];
933 for (std::size_t k = m_belowStart[child]; k < m_belowStart[child + 1]; ++k) {
934 m_belowToParent[k] = position[m_frontRowList[k +
static_cast<std::size_t
>(m_frontColumns[child + 1])]];
937 for (std::size_t k = m_assemblyStart[s]; k < m_assemblyStart[s + 1]; ++k) {
938 m_assembly[k].row = position[m_assembly[k].row];
943 m_symbolicFactorSize = 0;
944 m_symbolicStackSize = 0;
945 m_symbolicFrontOrder = 0;
947 std::size_t stack = 0;
948 for (Index s = 0; s < numFronts; ++s) {
949 const Index numColumns = m_frontColumns[s + 1] - m_frontColumns[s];
950 const Index numBelow =
static_cast<Index
>(m_belowStart[s + 1] - m_belowStart[s]);
951 m_symbolicFactorSize += rectangleSize(numColumns + numBelow, numColumns);
952 m_symbolicFrontOrder = numext::maxi(m_symbolicFrontOrder, numColumns + numBelow);
953 for (std::size_t c = m_childStart[s]; c < m_childStart[s + 1]; ++c) {
954 const StorageIndex child = m_children[c];
955 stack -= packedSize(
static_cast<Index
>(m_belowStart[child + 1] - m_belowStart[child]));
957 stack += packedSize(numBelow);
958 m_symbolicStackSize = numext::maxi(m_symbolicStackSize, stack);
962 m_numDelayed.resize(numFronts);
963 m_factoredFronts.resize(numFronts);
964 m_pivots.resize(size);
966 m_subdiagonal.resize(size);
971 m_isInitialized =
true;
974template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
976 eigen_assert(m_isInitialized &&
"analyzePattern() must be called first.");
977 eigen_assert(matrix.rows() == rows() && matrix.cols() == rows());
979 eigen_assert(
static_cast<std::size_t
>(matrix.nonZeros()) == m_numValues &&
980 "The matrix must have the analyzed sparsity pattern.");
982 const Scalar* values = matrix.valuePtr();
983 if (!matrix.isCompressed()) {
984 m_values.resize(m_numValues);
985 std::size_t value = 0;
986 for (Index outer = 0; outer < matrix.outerSize(); ++outer) {
987 for (
typename MatrixType::InnerIterator it(matrix, outer); it; ++it) m_values[value++] = it.value();
989 values = m_values.data();
993 m_L.reserve(m_symbolicFactorSize);
994 m_stack.reserve(m_symbolicStackSize);
995 m_factorRows.reserve(m_frontRowList.size());
996 if (m_front.size() < rectangleSize(m_symbolicFrontOrder, m_symbolicFrontOrder)) {
997 m_front.resize(rectangleSize(m_symbolicFrontOrder, m_symbolicFrontOrder));
1002 m_factorRows.clear();
1008 m_maxFrontOrder = 0;
1009 m_hasZeroPivot =
false;
1011 const Index numFronts =
static_cast<Index
>(m_frontColumns.size()) - 1;
1013 const StorageIndex*
const frontColumns = m_frontColumns.data();
1014 const std::size_t*
const belowStart = m_belowStart.data();
1015 const std::size_t*
const childStart = m_childStart.data();
1016 const StorageIndex*
const children = m_children.data();
1017 const StorageIndex*
const numDelayed = m_numDelayed.data();
1018 const std::size_t*
const assemblyStart = m_assemblyStart.data();
1019 const Assembly*
const assembly = m_assembly.data();
1020 const StorageIndex*
const frontRowList = m_frontRowList.data();
1021 const StorageIndex*
const belowToParent = m_belowToParent.data();
1022 const StorageIndex*
const frontParent = m_frontParent.data();
1023 for (Index s = 0; s < numFronts; ++s) {
1024 const Index firstColumn = frontColumns[s];
1025 const Index numColumns = frontColumns[s + 1] - firstColumn;
1026 const Index numBelow =
static_cast<Index
>(belowStart[s + 1] - belowStart[s]);
1028 Index delayedIn = 0;
1029 for (std::size_t c = childStart[s]; c < childStart[s + 1]; ++c) delayedIn += numDelayed[children[c]];
1031 const Index fullySummed = delayedIn + numColumns;
1032 const Index order = fullySummed + numBelow;
1033 m_maxFrontOrder = numext::maxi(m_maxFrontOrder, order);
1035 const std::size_t frontSize = rectangleSize(order, order);
1036 if (m_front.size() < frontSize) m_front.resize(frontSize);
1037 StorageIndex* rows = m_factorRows.push(
static_cast<std::size_t
>(order));
1038 FrontMap front(m_front.data(), order, order);
1041 if (order < kBlockedFrontMinOrder) {
1044 for (Index j = 0; j < order; ++j) front.col(j).tail(order - j).setZero();
1047 for (std::size_t k = assemblyStart[s]; k < assemblyStart[s + 1]; ++k) {
1048 const Assembly& entry = assembly[k];
1049 const Scalar& value = values[entry.value];
1050 front(entry.row + delayedIn, entry.col + delayedIn) += entry.conjugate ? Scalar(numext::conj(value)) : value;
1054 const StorageIndex* rowList = frontRowList + belowStart[s] + firstColumn;
1055 internal::smart_copy(rowList, rowList + numColumns + numBelow, rows + delayedIn);
1058 Index delayedSlot = delayedIn;
1059 const std::size_t childBegin = childStart[s];
1060 for (std::size_t c = childStart[s + 1]; c > childBegin; --c) {
1061 const Index child = children[c - 1];
1062 const Index delayed = numDelayed[child];
1063 const Index childBelow =
static_cast<Index
>(belowStart[child + 1] - belowStart[child]);
1064 const Index childOrder = delayed + childBelow;
1065 delayedSlot -= delayed;
1068 const StorageIndex* childMap = belowToParent + belowStart[child];
1069 if (delayedIn > 0) {
1070 if (m_childMap.size() <
static_cast<std::size_t
>(childOrder)) m_childMap.resize(childOrder);
1071 const FactoredFront& factored = m_factoredFronts[child];
1072 const StorageIndex* delayedRows = m_factorRows.storage.data() + factored.rows + factored.numPivots;
1073 for (Index i = 0; i < delayed; ++i) {
1074 m_childMap[i] = internal::convert_index<StorageIndex>(delayedSlot + i);
1075 rows[delayedSlot + i] = delayedRows[i];
1077 for (Index i = 0; i < childBelow; ++i) {
1078 m_childMap[delayed + i] = internal::convert_index<StorageIndex>(delayedIn + childMap[i]);
1080 childMap = m_childMap.data();
1085 const std::size_t blockSize = packedSize(childOrder);
1086 const Scalar* block = m_stack.top(blockSize);
1087 if (childOrder < kVectorizedMinLength) {
1088 scatterAdd(order, block, childMap, childOrder);
1090 extendAdd(order, block, childMap, childOrder);
1092 m_stack.pop(blockSize);
1095 const bool isRoot = frontParent[s] == -1;
1096 if (fullySummed == 1 && factorOnePivotFront(s, order, isRoot))
continue;
1098 const Index numPivots = factorFront(order, fullySummed, isRoot);
1100 Scalar* factor = appendFactor(s, numPivots, order);
1101 internal::smart_copy(m_front.data(), m_front.data() + rectangleSize(order, numPivots), factor);
1103 pushToParent(s, order, fullySummed, numPivots);
1107 const Index size = rows();
1108 eigen_internal_assert(m_numPivots == size);
1110 for (Index k = 0; k < size; ++k) {
1111 const StorageIndex row = m_invPerm[m_pivots[k]];
1112 m_Pinv.indices()[k] = row;
1113 m_P.indices()[row] = internal::convert_index<StorageIndex>(k);
1120 for (Index k = 0; k < size; ++k) {
1121 const RealScalar d1 = m_D[k];
1122 const RealScalar sub = numext::abs(m_subdiagonal[k]);
1123 if (sub != RealScalar(0)) {
1124 const RealScalar d2 = m_D[k + 1];
1125 m_blocks.emplace_back(d1, d2, sub);
1126 if (!(numext::isfinite)(d1) || !(numext::isfinite)(sub) || !(numext::isfinite)(d2)) {
1128 }
else if (m_blocks.back().det < RealScalar(0)) {
1131 }
else if (d1 + d2 > RealScalar(0)) {
1137 }
else if (!(numext::isfinite)(d1)) {
1139 }
else if (d1 > RealScalar(0)) {
1141 }
else if (d1 < RealScalar(0)) {
1151template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1152typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::RealScalar
1154 eigen_assert(m_isInitialized &&
"Decomposition is not initialized.");
1155 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before logAbsDeterminant().");
1157 RealScalar result(0);
1158 for (Index k = 0; k < rows(); ++k) {
1159 const RealScalar sub = numext::abs(m_subdiagonal[k]);
1160 if (sub != RealScalar(0)) {
1161 const ScaledBlock block(m_D[k], m_D[k + 1], sub);
1162 result += RealScalar(2) * numext::log(block.scale) + numext::log(numext::abs(block.det));
1165 result += numext::log(numext::abs(m_D[k]));
1171template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1172typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::Scalar*
1173MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::appendFactor(Index s, Index numPivots, Index order) {
1174 m_factoredFronts[s] =
1175 FactoredFront{internal::convert_index<StorageIndex>(numPivots), internal::convert_index<StorageIndex>(order),
1176 m_factorRows.size - order, m_L.size};
1177 m_LNonZeros +=
static_cast<Index
>(factorSize(numPivots, order));
1178 return m_L.push(rectangleSize(order, numPivots));
1181template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1182void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::extendAdd(Index order,
const Scalar* block,
1183 const StorageIndex* map, Index childOrder) {
1184 if (m_childRunEnd.size() <
static_cast<std::size_t
>(childOrder)) m_childRunEnd.resize(childOrder);
1186 Index runEnd = childOrder;
1187 m_childRunEnd[childOrder - 1] = internal::convert_index<StorageIndex>(runEnd);
1188 for (Index i = childOrder - 2; i >= 0; --i) {
1189 if (map[i + 1] != map[i] + 1) {
1193 m_childRunEnd[i] = internal::convert_index<StorageIndex>(runEnd);
1196 if (childOrder < kExtendAddMinRunLength * numRuns) {
1197 scatterAdd(order, block, map, childOrder);
1201 FrontMap front(m_front.data(), order, order);
1202 for (Index j = 0; j < childOrder; ++j) {
1203 Scalar* column = &front.coeffRef(0, map[j]);
1204 for (Index i = j; i < childOrder;) {
1205 const Index end = m_childRunEnd[i];
1206 addTo(column + map[i], block, end - i);
1213template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1214typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::RealScalar
1215MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::frontColumnMax(Index order, Index active, Index j, Index skip)
const {
1216 ConstFrontMap front(m_front.data(), order, order);
1217 RealScalar result(0);
1218 for (Index i = active; i < j; ++i) {
1219 if (i != skip) result = numext::maxi(result, RealScalar(numext::abs(front(j, i))));
1221 const Scalar* column = &front.coeffRef(0, j);
1222 const Index split = skip > j ? skip : order;
1223 result = numext::maxi(result, largestMagnitude(column + j + 1, split - j - 1));
1224 if (order > split + 1) result = numext::maxi(result, largestMagnitude(column + split + 1, order - split - 1));
1228template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1229bool MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::frontColumnIsZero(Index order, Index active, Index j)
const {
1230 ConstFrontMap front(m_front.data(), order, order);
1231 return (front.row(j).segment(active, j - active).array() == Scalar(0)).all() &&
1232 (front.col(j).tail(order - j - 1).array() == Scalar(0)).all();
1235template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1236Index MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::largestFullySummed(Index order, Index active, Index fullySummed,
1237 Index j, RealScalar& rest)
const {
1238 ConstFrontMap front(m_front.data(), order, order);
1240 RealScalar largest(0);
1241 rest = RealScalar(0);
1242 const auto visit = [&](Index i,
const RealScalar& magnitude) {
1243 if (magnitude > largest) {
1245 largest = magnitude;
1248 rest = numext::maxi(rest, magnitude);
1251 for (Index i = active; i < j; ++i) visit(i, numext::abs(front(j, i)));
1252 for (Index i = j + 1; i < fullySummed; ++i) visit(i, numext::abs(front(i, j)));
1253 rest = numext::maxi(rest, largestMagnitude(&front.coeffRef(0, j) + fullySummed, order - fullySummed));
1257template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1258EIGEN_ALWAYS_INLINE
bool MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorOnePivotFront(Index s, Index order,
1260 ConstFrontMap front(m_front.data(), order, order);
1261 const RealScalar d = numext::real(front(0, 0));
1262 if (d == RealScalar(0))
return false;
1266 if (!isRoot && !(numext::abs(d) >= m_threshold * frontColumnMax(order, 0, 0, -1))) {
1267 appendFactor(s, 0, order);
1268 pushToParent(s, order, 1, 0);
1272 m_D[m_numPivots] = d;
1273 m_subdiagonal[m_numPivots] = Scalar(0);
1274 m_pivots[m_numPivots] = frontRows(order)[0];
1276 m_numDelayed[s] = 0;
1278 const Index numBelow = order - 1;
1279 Scalar* L = appendFactor(s, 1, order);
1280 Scalar* contribution = m_stack.push(packedSize(numBelow));
1281 const Scalar* u = &front.coeffRef(0, 0);
1282 for (Index j = 1; j < order; ++j) {
1283 const Index length = order - j;
1284 const Scalar lj = numext::conj(u[j]) / d;
1285 const Scalar* column = &front.coeffRef(j, j);
1286 if (length < kVectorizedMinLength) {
1287 for (Index i = 0; i < length; ++i) contribution[i] = column[i] - u[j + i] * lj;
1289 VectorMap(contribution, length) = ConstVectorMap(column, length) - ConstVectorMap(u + j, length) * lj;
1291 contribution += length;
1292 L[j] = numext::conj(lj);
1298template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1299void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::pushToParent(Index s, Index order, Index fullySummed,
1301 const Index numDelayed = fullySummed - numPivots;
1302 m_numDelayed[s] = internal::convert_index<StorageIndex>(numDelayed);
1304 ConstFrontMap front(m_front.data(), order, order);
1305 Scalar* contribution = m_stack.push(packedSize(order - numPivots));
1306 if (order <= kSmallFrontMaxOrder) {
1307 const Index end = numext::mini(order, Index(kSmallFrontMaxOrder));
1308 for (Index j = numPivots; j < end; ++j) {
1309 for (Index i = j; i < end; ++i) *contribution++ = front(i, j);
1313 for (Index j = numPivots; j < order; ++j) {
1314 internal::smart_copy(&front.coeffRef(j, j), &front.coeffRef(j, j) + (order - j), contribution);
1315 contribution += order - j;
1319template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1320void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::swapFront(Index order, Index a, Index b) {
1322 if (a > b) std::swap(a, b);
1324 FrontMap front(m_front.data(), order, order);
1325 internal::selfadjoint_swap_lower(front, a, b);
1326 std::swap(frontRows(order)[a], frontRows(order)[b]);
1329template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1330void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::eliminate1x1(Index order, Index k, Index panelEnd) {
1331 FrontMap front(m_front.data(), order, order);
1332 const RealScalar d = numext::real(front(k, k));
1333 m_D[m_numPivots] = d;
1334 m_subdiagonal[m_numPivots] = Scalar(0);
1335 m_pivots[m_numPivots] = frontRows(order)[k];
1338 if (d == RealScalar(0)) {
1340 m_hasZeroPivot =
true;
1346 if (order <= kSmallFrontMaxOrder) {
1348 const Index end = numext::mini(order, Index(kSmallFrontMaxOrder));
1349 for (Index j = k + 1; j < end; ++j) {
1350 const Scalar lj = numext::conj(front(j, k)) / d;
1351 for (Index i = j; i < end; ++i) front(i, j) -= front(i, k) * lj;
1352 front(j, k) = numext::conj(lj);
1356 for (Index j = k + 1; j < panelEnd; ++j) {
1357 const Scalar lj = numext::conj(front(j, k)) / d;
1358 subtractScaled(&front.coeffRef(j, j), &front.coeffRef(j, k), lj, order - j);
1359 front(j, k) = numext::conj(lj);
1361 front.col(k).tail(order - panelEnd) = front.col(k).tail(order - panelEnd) / d;
1364template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1365void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::eliminate2x2(Index order, Index k, Index panelEnd) {
1366 FrontMap front(m_front.data(), order, order);
1367 const RealScalar d11 = numext::real(front(k, k));
1368 const Scalar d21 = front(k + 1, k);
1369 const RealScalar d22 = numext::real(front(k + 1, k + 1));
1370 m_D[m_numPivots] = d11;
1371 m_D[m_numPivots + 1] = d22;
1372 m_subdiagonal[m_numPivots] = d21;
1373 m_subdiagonal[m_numPivots + 1] = Scalar(0);
1374 m_pivots[m_numPivots] = frontRows(order)[k];
1375 m_pivots[m_numPivots + 1] = frontRows(order)[k + 1];
1379 const ScaledBlock block(d11, d22, numext::abs(d21));
1380 const Scalar b = d21 / block.scale;
1381 const Scalar conjB = numext::conj(b);
1383 const Index numRows = order - k - 2;
1385 Scalar* u1 = front.data() + rectangleSize(order, k) + (k + 2);
1386 Scalar* u2 = u1 + order;
1387 if (order <= kSmallFrontMaxOrder) {
1389 constexpr Index kMaxRows = kSmallFrontMaxOrder - 2;
1390 Scalar l1[kMaxRows], l2[kMaxRows];
1391 const Index smallRows = numext::mini(numRows, kMaxRows);
1392 for (Index i = 0; i < smallRows; ++i) {
1393 l1[i] = ((u1[i] * block.c - u2[i] * b) / block.scale) / block.det;
1394 l2[i] = ((u2[i] * block.a - u1[i] * conjB) / block.scale) / block.det;
1396 for (Index j = 0; j < smallRows; ++j) {
1397 const Scalar alpha1 = numext::conj(u1[j]);
1398 const Scalar alpha2 = numext::conj(u2[j]);
1399 Scalar* column = &front.coeffRef(k + 2, k + 2 + j);
1400 for (Index i = j; i < smallRows; ++i) column[i] -= l1[i] * alpha1 + l2[i] * alpha2;
1402 for (Index i = 0; i < smallRows; ++i) {
1406 front(k + 1, k) = Scalar(0);
1409 if (m_pivotScratch.size() < rectangleSize(2, numRows)) m_pivotScratch.resize(rectangleSize(2, numRows));
1410 Scalar* l1 = m_pivotScratch.data();
1411 Scalar* l2 = l1 + numRows;
1412 if (numRows < kVectorizedMinLength) {
1413 for (Index i = 0; i < numRows; ++i) {
1414 l1[i] = ((u1[i] * block.c - u2[i] * b) / block.scale) / block.det;
1415 l2[i] = ((u2[i] * block.a - u1[i] * conjB) / block.scale) / block.det;
1418 const ConstVectorMap mapU1(u1, numRows);
1419 const ConstVectorMap mapU2(u2, numRows);
1420 VectorMap(l1, numRows) = ((mapU1 * block.c - mapU2 * b) / block.scale) / block.det;
1421 VectorMap(l2, numRows) = ((mapU2 * block.a - mapU1 * conjB) / block.scale) / block.det;
1424 for (Index j = k + 2; j < panelEnd; ++j) {
1425 const Index offset = j - k - 2;
1426 subtractScaled(&front.coeffRef(j, j), l1 + offset, numext::conj(u1[offset]), l2 + offset, numext::conj(u2[offset]),
1430 front(k + 1, k) = Scalar(0);
1431 internal::smart_copy(l1, l1 + numRows, u1);
1432 internal::smart_copy(l2, l2 + numRows, u2);
1435template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1436void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::updateTrailing(Index order, Index firstPivot, Index numPivots,
1438 const Index trailing = order - panelEnd;
1439 if (trailing == 0 || numPivots == 0)
return;
1441 FrontMap front(m_front.data(), order, order);
1442 if (m_pivotScratch.size() < rectangleSize(trailing, numPivots)) {
1443 m_pivotScratch.resize(rectangleSize(trailing, numPivots));
1445 FrontMap W(m_pivotScratch.data(), trailing, numPivots);
1446 const auto L21 = front.block(panelEnd, firstPivot, trailing, numPivots);
1449 Index p = m_numPivots - numPivots;
1450 for (Index c = 0; c < numPivots; ++c, ++p) {
1451 if (m_subdiagonal[p] != Scalar(0)) {
1452 W.col(c) = L21.col(c) * m_D[p] + L21.col(c + 1) * m_subdiagonal[p];
1453 W.col(c + 1) = L21.col(c) * numext::conj(m_subdiagonal[p]) + L21.col(c + 1) * m_D[p + 1];
1457 W.col(c) = L21.col(c) * m_D[p];
1461 front.bottomRightCorner(trailing, trailing).template triangularView<Lower>() -= W * L21.adjoint();
1464template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1465Index MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorFront(Index order, Index fullySummed,
bool isRoot) {
1466 FrontMap front(m_front.data(), order, order);
1473 Index panelEnd = order < kBlockedFrontMinOrder ? order : numext::mini(Index(kPanelWidth), fullySummed);
1474 const auto flush = [&] {
1475 updateTrailing(order, applied, k - applied, panelEnd);
1477 panelEnd = numext::mini(k + kPanelWidth, fullySummed);
1485 Index tail = fullySummed;
1486 bool acceptedPivot =
false;
1488 Index lastPivotEnd = 0;
1490 while (k < fullySummed) {
1491 if (k >= panelEnd) flush();
1495 if (acceptedPivot) {
1496 tail = tail == fullySummed ? lastPivotEnd : fullySummed;
1497 acceptedPivot =
false;
1503 if (applied < k) flush();
1508 front.diagonal().segment(k, fullySummed - k).real().cwiseAbs().template maxCoeff<PropagateNumbers>(&largest);
1510 swapFront(order, k, largest);
1514 if (numext::real(front(k, k)) == RealScalar(0)) {
1515 RealScalar nan = NumTraits<RealScalar>::quiet_NaN();
1516 EIGEN_FAST_MATH_CONSTANT_BARRIER(nan);
1517 front(k, k) = Scalar(nan);
1520 eliminate1x1(order, k, panelEnd);
1526 if (next >= panelEnd) {
1531 const Index numUntested = tail - next;
1532 const Index numMoved = numext::mini(next - k, numUntested);
1533 for (Index i = 0; i < numMoved; ++i) swapFront(order, k + i, tail - 1 - i);
1535 tail = k + numUntested;
1538 const Index j = next;
1539 const RealScalar djj = numext::real(front(j, j));
1540 const RealScalar absDjj = numext::abs(djj);
1543 if (djj != RealScalar(0) ? absDjj >= m_threshold * frontColumnMax(order, k, j, -1)
1544 : frontColumnIsZero(order, k, j)) {
1545 swapFront(order, k, j);
1546 eliminate1x1(order, k, panelEnd);
1549 lastPivotEnd = next;
1550 acceptedPivot =
true;
1556 const Index r = largestFullySummed(order, k, fullySummed, j, columnJ);
1561 if (r >= panelEnd && applied < k) flush();
1568 const RealScalar drr = numext::real(front(r, r));
1569 const ScaledBlock block(djj, drr, numext::abs(r > j ? front(r, j) : front(j, r)));
1570 const RealScalar a = numext::abs(block.a);
1571 const RealScalar b = block.absB;
1572 const RealScalar c = numext::abs(block.c);
1573 const RealScalar absDet = numext::abs(block.det);
1574 const RealScalar bound = absDet * block.scale / m_threshold;
1575 const RealScalar columnR = frontColumnMax(order, k, r, j);
1576 if (block.det != RealScalar(0) && absDet >= b * b / RealScalar(2) && c * columnJ + b * columnR <= bound &&
1577 b * columnJ + a * columnR <= bound) {
1578 swapFront(order, k, j);
1580 swapFront(order, k + 1, r == k ? j : r);
1581 eliminate2x2(order, k, panelEnd);
1583 next = numext::maxi(j + 1, k);
1584 lastPivotEnd = next;
1585 acceptedPivot =
true;
1595template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1596typename MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::FactorType
1598 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before reading L.");
1601 std::vector<StorageIndex> pivotOf(rows());
1602 for (Index k = 0; k < rows(); ++k) pivotOf[m_pivots[k]] = internal::convert_index<StorageIndex>(k);
1604 std::vector<Triplet<Scalar, StorageIndex>> entries;
1605 entries.reserve(
static_cast<std::size_t
>(m_LNonZeros) +
static_cast<std::size_t
>(rows()));
1606 for (
const FactoredFront& factored : m_factoredFronts) {
1607 const Index order = factored.order;
1608 const StorageIndex* rows = m_factorRows.storage.data() + factored.rows;
1609 const Index numPivots = factored.numPivots;
1610 ConstFrontMap L(m_L.storage.data() + factored.values, order, numPivots);
1611 for (Index j = 0; j < numPivots; ++j) {
1612 const StorageIndex col = pivotOf[rows[j]];
1613 entries.emplace_back(col, col, Scalar(1));
1614 for (Index i = j + 1; i < order; ++i) entries.emplace_back(pivotOf[rows[i]], col, L(i, j));
1618 FactorType result(rows(), cols());
1623#ifndef EIGEN_PARSED_BY_DOXYGEN
1624template <
typename MatrixType_,
int UpLo_,
typename Ordering_>
1625template <
typename Rhs,
typename Dest>
1628 eigen_assert(m_isInitialized &&
"Decomposition is not initialized.");
1629 eigen_assert(m_info !=
InvalidInput &&
"factorize() must be called before solve().");
1630 eigen_assert(rhs.rows() == rows());
1632 const typename internal::nested_eval<Rhs, Dynamic>::type actualRhs(rhs.derived());
1633 const Index numRhs = rhs.cols();
1634 FrontMatrix X(rows(), numRhs);
1635 for (Index col = 0; col < numRhs; ++col) {
1636 for (Index i = 0; i < rows(); ++i) X(m_perm[i], col) = actualRhs.coeff(i, col);
1640 FrontMatrix Y(m_maxFrontOrder, numRhs);
1641 const auto gather = [&](
const StorageIndex* rows, Index count) {
1642 for (Index col = 0; col < numRhs; ++col) {
1643 for (Index i = 0; i < count; ++i) Y(i, col) = X(rows[i], col);
1646 const auto scatter = [&](
const StorageIndex* rows, Index count) {
1647 for (Index col = 0; col < numRhs; ++col) {
1648 for (Index i = 0; i < count; ++i) X(rows[i], col) = Y(i, col);
1653 for (
const FactoredFront& factored : m_factoredFronts) {
1654 const Index order = factored.order;
1655 const Index numPivots = factored.numPivots;
1656 const StorageIndex* rows = m_factorRows.storage.data() + factored.rows;
1657 ConstFrontMap L(m_L.storage.data() + factored.values, order, numPivots);
1658 if (order * numPivots < kDenseSolveMinSize) {
1659 for (Index col = 0; col < numRhs; ++col) {
1660 Scalar* x = X.col(col).data();
1661 for (Index j = 0; j < numPivots; ++j) {
1662 const Scalar value = x[rows[j]];
1663 const Scalar* column = &L.coeffRef(0, j);
1664 for (Index i = j + 1; i < order; ++i) x[rows[i]] -= column[i] * value;
1668 const Index numBelow = order - numPivots;
1669 gather(rows, order);
1673 L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(y.head(numPivots));
1674 y.segment(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * y.head(numPivots);
1676 L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(Y.topRows(numPivots));
1677 Y.middleRows(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * Y.topRows(numPivots);
1679 scatter(rows, order);
1684 for (Index col = 0; col < numRhs; ++col) {
1685 Scalar* x = X.col(col).data();
1686 auto block = m_blocks.cbegin();
1687 for (Index k = 0; k < rows(); ++k) {
1688 const Index row = m_pivots[k];
1689 if (m_subdiagonal[k] != Scalar(0)) {
1690 const Index nextRow = m_pivots[k + 1];
1691 const Scalar b = m_subdiagonal[k] / block->scale;
1692 const Scalar y1 = x[row];
1693 const Scalar y2 = x[nextRow];
1694 x[row] = ((y1 * block->c - y2 * numext::conj(b)) / block->scale) / block->det;
1695 x[nextRow] = ((y2 * block->a - y1 * b) / block->scale) / block->det;
1698 }
else if (m_D[k] != RealScalar(0)) {
1707 for (
auto factored = m_factoredFronts.rbegin(); factored != m_factoredFronts.rend(); ++factored) {
1708 const Index order = factored->order;
1709 const Index numPivots = factored->numPivots;
1710 const StorageIndex* rows = m_factorRows.storage.data() + factored->rows;
1711 ConstFrontMap L(m_L.storage.data() + factored->values, order, numPivots);
1712 if (order * numPivots < kDenseSolveMinSize) {
1713 for (Index col = 0; col < numRhs; ++col) {
1714 Scalar* x = X.col(col).data();
1715 for (Index j = numPivots - 1; j >= 0; --j) {
1716 Scalar value = x[rows[j]];
1717 const Scalar* column = &L.coeffRef(0, j);
1718 for (Index i = order - 1; i > j; --i) value -= numext::conj(column[i]) * x[rows[i]];
1723 const Index numBelow = order - numPivots;
1724 gather(rows, order);
1727 y.head(numPivots).noalias() -= L.bottomRows(numBelow).adjoint() * y.segment(numPivots, numBelow);
1728 L.topRows(numPivots).adjoint().template triangularView<UnitUpper>().solveInPlace(y.head(numPivots));
1730 Y.topRows(numPivots).noalias() -= L.bottomRows(numBelow).adjoint() * Y.middleRows(numPivots, numBelow);
1731 L.topRows(numPivots).adjoint().template triangularView<UnitUpper>().solveInPlace(Y.topRows(numPivots));
1733 scatter(rows, numPivots);
1737 for (Index col = 0; col < numRhs; ++col) {
1738 for (Index i = 0; i < rows(); ++i) dest.coeffRef(i, col) = X(m_perm[i], col);
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
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
Sparse multifrontal LDL^* factorization of a symmetric or Hermitian indefinite matrix.
Definition MultifrontalLDLT.h:78
RealScalar logAbsDeterminant() const
Definition MultifrontalLDLT.h:1153
FactorType matrixU() const
Definition MultifrontalLDLT.h:189
const PermutationType & permutationPinv() const
Definition MultifrontalLDLT.h:207
Scalar determinant() const
Definition MultifrontalLDLT.h:221
void factorize(const MatrixType &matrix)
Definition MultifrontalLDLT.h:975
MultifrontalLDLT & setPivotThreshold(const RealScalar &threshold)
Definition MultifrontalLDLT.h:114
bool isPositive() const
Definition MultifrontalLDLT.h:282
Scalar signDeterminant() const
Definition MultifrontalLDLT.h:245
Index numZero() const
Definition MultifrontalLDLT.h:276
MultifrontalLDLT()=default
const PermutationType & permutationP() const
Definition MultifrontalLDLT.h:197
bool isNegative() const
Definition MultifrontalLDLT.h:285
void analyzePattern(const MatrixType &matrix)
Definition MultifrontalLDLT.h:699
Index nonZeros() const
Definition MultifrontalLDLT.h:290
Index numPositive() const
Definition MultifrontalLDLT.h:258
RealScalar absDeterminant() const
Definition MultifrontalLDLT.h:229
Index numNegative() const
Definition MultifrontalLDLT.h:264
const RealScalar & pivotThreshold() const
Definition MultifrontalLDLT.h:121
MultifrontalLDLT(const MatrixType &matrix)
Definition MultifrontalLDLT.h:106
const RealVectorType & vectorD() const
Definition MultifrontalLDLT.h:163
ComputationInfo info() const
Reports whether the previous factorization was successful.
Definition MultifrontalLDLT.h:154
FactorType matrixL() const
Definition MultifrontalLDLT.h:1597
const VectorType & subDiagonal() const
Definition MultifrontalLDLT.h:170
MultifrontalLDLT & compute(const MatrixType &matrix)
Definition MultifrontalLDLT.h:127
Index size() const
Definition PermutationMatrix.h:140
Index cols() const
Definition PermutationMatrix.h:137
Index rows() const
Definition PermutationMatrix.h:134
Permutation matrix.
Definition PermutationMatrix.h:346
constexpr const IndicesType & indices() const
Definition PermutationMatrix.h:400
constexpr const Scalar * data() const
Definition PlainObjectBase.h:261
constexpr void resize(Index rows, Index cols)
Definition PlainObjectBase.h:282
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
void setFromTriplets(const InputIterators &begin, const InputIterators &end)
Definition SparseMatrix.h:1376
SparseSolverBase()=default
ComputationInfo
Definition Constants.h:455
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ NumericalIssue
Definition Constants.h:459
@ InvalidInput
Definition Constants.h:464
@ Success
Definition Constants.h:457