Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
MultifrontalLDLT.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_MULTIFRONTAL_LDLT_H
11#define EIGEN_MULTIFRONTAL_LDLT_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17
77template <typename MatrixType_, int UpLo_ = Lower, typename Ordering_ = AMDOrdering<typename MatrixType_::StorageIndex>>
78class MultifrontalLDLT : public SparseSolverBase<MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>> {
80 using Base::m_isInitialized;
81
82 public:
83 using Base::_solve_impl;
84
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;
90 using VectorType = Matrix<Scalar, Dynamic, 1>;
91 using RealVectorType = Matrix<RealScalar, Dynamic, 1>;
94
95 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
96 EIGEN_STATIC_ASSERT(UpLo_ == Lower || UpLo_ == Upper, MULTIFRONTALLDLT_ACCEPTS_UPPER_AND_LOWER_MODE_ONLY)
97
98 static constexpr int UpLo = UpLo_;
99 static constexpr int ColsAtCompileTime = Dynamic;
100 static constexpr int MaxColsAtCompileTime = Dynamic;
101
103 MultifrontalLDLT() = default;
104
106 explicit MultifrontalLDLT(const MatrixType& matrix) { compute(matrix); }
107
114 MultifrontalLDLT& setPivotThreshold(const RealScalar& threshold) {
115 eigen_assert(threshold > RealScalar(0) && threshold <= RealScalar(0.5));
116 m_threshold = threshold;
117 return *this;
118 }
119
121 const RealScalar& pivotThreshold() const { return m_threshold; }
122
127 MultifrontalLDLT& compute(const MatrixType& matrix) {
128 analyzePattern(matrix);
129 factorize(matrix);
130 return *this;
131 }
132
137 void analyzePattern(const MatrixType& matrix);
138
143 void factorize(const MatrixType& matrix);
144
155 eigen_assert(m_isInitialized && "Decomposition is not initialized.");
156 return m_info;
157 }
158
159 Index rows() const { return m_P.rows(); }
160 Index cols() const { return m_P.cols(); }
161
163 const RealVectorType& vectorD() const {
164 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading D.");
165 return m_D;
166 }
167
170 const VectorType& subDiagonal() const {
171 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading D.");
172 return m_subdiagonal;
173 }
174
182 FactorType matrixL() const;
183
189 FactorType matrixU() const { return matrixL().adjoint(); }
190
197 const PermutationType& permutationP() const {
198 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the permutation.");
199 return m_P;
200 }
201
207 const PermutationType& permutationPinv() const {
208 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the permutation.");
209 return m_Pinv;
210 }
211
221 Scalar determinant() const { return Scalar(absDeterminant()) * signDeterminant(); }
222
229 RealScalar absDeterminant() const { return numext::exp(logAbsDeterminant()); }
230
238 RealScalar logAbsDeterminant() const;
239
245 Scalar signDeterminant() const {
246 if (numZero() > 0 || numPositive() + numNegative() < rows()) return Scalar(0);
247 return Scalar(numNegative() % 2 == 0 ? 1 : -1);
248 }
249
258 Index numPositive() const {
259 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia.");
260 return m_numPositive;
261 }
262
264 Index numNegative() const {
265 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia.");
266 return m_numNegative;
267 }
268
276 Index numZero() const {
277 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the inertia.");
278 return m_numZero;
279 }
280
282 bool isPositive() const { return numNegative() == 0 && numPositive() + numZero() == rows(); }
283
285 bool isNegative() const { return numPositive() == 0 && numNegative() + numZero() == rows(); }
286
290 Index nonZeros() const {
291 eigen_assert(m_info != InvalidInput && "factorize() must be called before reading the size of L.");
292 return m_LNonZeros;
293 }
294
295#ifndef EIGEN_PARSED_BY_DOXYGEN
297 template <typename Rhs, typename Dest>
298 void _solve_impl(const MatrixBase<Rhs>& rhs, MatrixBase<Dest>& dest) const;
299#endif // EIGEN_PARSED_BY_DOXYGEN
300
301 private:
303 using FrontMap = Map<FrontMatrix>;
304 using ConstFrontMap = Map<const FrontMatrix>;
305 using VectorMap = Map<VectorType>;
306 using ConstVectorMap = Map<const VectorType>;
307 using IndexVectorType = Matrix<StorageIndex, Dynamic, 1>;
308
309 // Columns of a front that a pivot updates directly. Wider panels do more of the work in level-2 updates, narrower
310 // ones pay for more calls to the level-3 product.
311 static constexpr Index kPanelWidth = 32;
312 // Below this order a front is its own panel: there's too little work to repay a level-3 product.
313 static constexpr Index kBlockedFrontMinOrder = 32;
314 // Below this length, a plain loop beats the alignment peeling of a vectorized expression. Sparse KKT matrices are
315 // dominated by fronts of a few columns, where this decides the factorization's speed.
316 static constexpr Index kVectorizedMinLength = 16;
317 // Up to this order, the loops over a front have compile-time bounds, so they unroll.
318 static constexpr Index kSmallFrontMaxOrder = 8;
319 // Below this mean length of the runs of a child's map into its parent, extend-add stays a scatter: walking short runs
320 // costs more than the additions they'd vectorize.
321 static constexpr Index kExtendAddMinRunLength = 4;
322 // Below this size of L (order * pivots), solve() applies a front's factor in place rather than through dense products
323 // on a gathered copy of its rows.
324 static constexpr Index kDenseSolveMinSize = 4096;
325
326 // An array whose storage survives popping and clearing, so refactoring doesn't reallocate or reinitialize it.
327 //
328 // This, m_front, and m_pivotScratch are aligned so that the factorization is bitwise reproducible. Vectorized kernels
329 // switch between scalar and packet code at alignment boundaries, and the two can round differently.
330 template <typename T>
331 struct WorkStack {
332 std::vector<T, aligned_allocator<T>> storage;
333 std::size_t size = 0;
334
335 // Returns where to write count new elements. This can invalidate earlier pointers into the array.
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;
339 size += count;
340 return end;
341 }
342
343 // Returns the last count elements.
344 T* top(std::size_t count) { return storage.data() + (size - count); }
345
346 void pop(std::size_t count) { size -= count; }
347 void reserve(std::size_t count) {
348 if (storage.size() < count) storage.resize(count);
349 }
350 void clear() { size = 0; }
351 };
352
353 // An entry of the input matrix and where it's assembled in its front. value is the entry's index in the values of the
354 // compressed matrix. row and col don't count delayed columns.
355 struct Assembly {
356 StorageIndex value;
357 StorageIndex row;
358 StorageIndex col;
359 // Whether the permutation moved the entry to the other triangle.
360 bool conjugate;
361 };
362
363 // Where a front's factor is stored after factorize().
364 struct FactoredFront {
365 StorageIndex numPivots;
366 StorageIndex order;
367 // Start of the front's rows in m_factorRows.
368 std::size_t rows;
369 // Start of the front's order x numPivots columns of L in m_L. Only the part below the diagonal is meaningful.
370 std::size_t values;
371 };
372
373 // The sizes are computed in std::size_t because Index can be narrower than the product.
374 static std::size_t rectangleSize(Index rows, Index cols) {
375 return static_cast<std::size_t>(rows) * static_cast<std::size_t>(cols);
376 }
377
378 // Entries in the lower triangle of an n x n matrix, including its diagonal.
379 static std::size_t packedSize(Index n) { return static_cast<std::size_t>(n) * (static_cast<std::size_t>(n) + 1) / 2; }
380
381 // Entries strictly below the diagonal in the first numPivots columns of an order x order matrix.
382 static std::size_t factorSize(Index numPivots, Index order) {
383 return rectangleSize(numPivots, order) - packedSize(numPivots);
384 }
385
386 // dst -= alpha * src, where the arrays don't overlap.
387 static void subtractScaled(Scalar* EIGEN_RESTRICT dst, const Scalar* EIGEN_RESTRICT src, const Scalar& alpha,
388 Index length) {
389 if (length < kVectorizedMinLength) {
390 for (Index i = 0; i < length; ++i) dst[i] -= src[i] * alpha;
391 } else {
392 VectorMap(dst, length).noalias() -= ConstVectorMap(src, length) * alpha;
393 }
394 }
395
396 // dst -= alpha1 * src1 + alpha2 * src2, where dst doesn't overlap the others.
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;
401 } else {
402 VectorMap(dst, length).noalias() -= ConstVectorMap(src1, length) * alpha1 + ConstVectorMap(src2, length) * alpha2;
403 }
404 }
405
406 // dst += src, where the arrays don't overlap.
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];
410 } else {
411 VectorMap(dst, length).noalias() += ConstVectorMap(src, length);
412 }
413 }
414
415 // Returns the largest magnitude of a column segment, or zero if it's empty.
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])));
420 return result;
421 }
422
423 // The rows of the order x order front being factored.
424 StorageIndex* frontRows(Index order) { return m_factorRows.top(static_cast<std::size_t>(order)); }
425
426 // The 2x2 block [d1 conj(d21); d21 d2] = scale [a conj(b); b c], where scale is its largest magnitude. det = a c -
427 // |b|^2 is in [-2, 1].
428 struct ScaledBlock {
429 RealScalar scale;
430 RealScalar a;
431 RealScalar c;
432 RealScalar absB;
433 RealScalar det;
434
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)),
437 a(d1 / scale),
438 c(d2 / scale),
439 absB(absD21 / scale),
440 det(a * c - absB * absB) {}
441 };
442
443 // Calls function(row, col, position) on the structural entries of the UpLo_ triangle in storage order, where position
444 // counts all of the matrix's entries before this one in storage order. That's the entry's index in the values of the
445 // matrix once it's compressed.
446 template <typename Function>
447 static void visitTriangle(const MatrixType& matrix, Function&& function) {
448 Index position = 0;
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);
455 }
456 }
457 }
458
459 // Largest fraction of explicit zeros allowed in a merged front's L, including its diagonal. An explicit zero costs
460 // more in a larger front, while a smaller one gains more from losing an extend-add and from gaining fully summed
461 // columns.
462 static double maxExplicitZeroFraction(Index pivots) { return pivots < 4 ? 0.3 : (pivots < 32 ? 0.1 : 0.02); }
463
464 // Merges fronts into their parents if the result has few enough explicit zeros, then renumbers the columns so that
465 // each merged front's are contiguous. frontParent and frontBelow hold each front's parent, or -1 for a root, and its
466 // number of rows below its pivots. Updates columnFront, m_frontColumns, m_perm and m_invPerm, and sets newColumn to
467 // each column's new index.
468 void mergeRelaxedFronts(const std::vector<StorageIndex>& frontParent, const std::vector<StorageIndex>& frontBelow,
469 std::vector<StorageIndex>& columnFront, std::vector<StorageIndex>& newColumn);
470
471 // Records a factored front and returns where to write its order x numPivots columns of L.
472 Scalar* appendFactor(Index s, Index numPivots, Index order);
473
474 // Returns the largest off-diagonal magnitude of column j in the front's active part, which starts at row active,
475 // leaving out row skip (or -1 for none).
476 //
477 // This, largestFullySummed() and largestMagnitude() skip NaN entries, so a pivot can pass its test against a column
478 // holding a NaN. The update carries the NaN to the diagonal of a later pivot, and factorize() reports a non-finite
479 // pivot as NumericalIssue.
480 RealScalar frontColumnMax(Index order, Index active, Index j, Index skip) const;
481
482 // Returns whether column j is exactly zero off its diagonal in the front's active part, which starts at row active. A
483 // NaN entry counts as nonzero.
484 bool frontColumnIsZero(Index order, Index active, Index j) const;
485
486 // Returns the row r in [active, fullySummed) other than j with the largest magnitude in column j, or -1 if they're
487 // all zero, and sets rest to frontColumnMax(order, active, j, r).
488 Index largestFullySummed(Index order, Index active, Index fullySummed, Index j, RealScalar& rest) const;
489
490 // These add a child's packed lower triangle to the order x order front, where map gives each of its childOrder rows'
491 // row in the front. extendAdd() adds the rows that stay adjacent in the front as vectorized segments, if there are
492 // enough of them. A call is too expensive for the short children of a tree of small fronts, so they scatter inline.
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++;
498 }
499 }
500 void extendAdd(Index order, const Scalar* block, const StorageIndex* map, Index childOrder);
501
502 // Eliminates pivots from the fully summed columns of m_front and returns how many. Pivots end up at the front's start
503 // and delayed columns between them and the rows that aren't fully summed, with the front's rows permuted to match.
504 Index factorFront(Index order, Index fullySummed, bool isRoot);
505
506 // Factors a front with one fully summed column in a single pass, without updating the front in place and then copying
507 // its results, or delays the column if it fails the 1x1 test. Returns false, leaving the front unchanged, if the
508 // pivot is zero.
509 EIGEN_ALWAYS_INLINE bool factorOnePivotFront(Index s, Index order, bool isRoot);
510
511 // Records the factored front's fullySummed - numPivots delayed columns and pushes the packed lower triangle of its
512 // trailing order - numPivots rows and columns onto m_stack, for its parent's extend-add to pop. The parent reads the
513 // delayed rows from m_factorRows, after the front's pivots.
514 void pushToParent(Index s, Index order, Index fullySummed, Index numPivots);
515
516 // Swaps two rows and columns of the front.
517 void swapFront(Index order, Index a, Index b);
518
519 // These eliminate the pivot at column k from the columns before panelEnd. updateTrailing() applies it to the others.
520 void eliminate1x1(Index order, Index k, Index panelEnd);
521 void eliminate2x2(Index order, Index k, Index panelEnd);
522
523 // Applies the last numPivots pivots to the columns from panelEnd on.
524 void updateTrailing(Index order, Index firstPivot, Index numPivots, Index panelEnd);
525
526 // The pivot tests bound |L| by 1/u, so a smaller u trades backward error for fill.
527 RealScalar m_threshold = RealScalar(0.01);
528
530
531 // Symbolic analysis
532
533 // Each input row's row in elimination order, and its inverse.
534 std::vector<StorageIndex> m_perm;
535 std::vector<StorageIndex> m_invPerm;
536 // First column of each front, with one extra element at the end.
537 std::vector<StorageIndex> m_frontColumns;
538 // Each front's parent, or -1 for a root.
539 std::vector<StorageIndex> m_frontParent;
540 // The number of rows below each front's pivots, as m_belowStart[s + 1] - m_belowStart[s].
541 std::vector<std::size_t> m_belowStart;
542 // Each front's columns followed by the rows below its pivots, starting at m_belowStart[s] + m_frontColumns[s].
543 std::vector<StorageIndex> m_frontRowList;
544 // Position in the parent front of each row below a front's pivots, from m_belowStart[s], not counting the parent's
545 // delayed columns.
546 std::vector<StorageIndex> m_belowToParent;
547 // Each front's children, in increasing order.
548 std::vector<std::size_t> m_childStart;
549 std::vector<StorageIndex> m_children;
550 // Where each input matrix entry is assembled.
551 std::vector<std::size_t> m_assemblyStart;
552 std::vector<Assembly> m_assembly;
553 // Number of entries the input matrix stores, in both triangles.
554 std::size_t m_numValues = 0;
555 // What a factorization without delayed pivots stores in m_L, and its largest m_stack and front order.
556 std::size_t m_symbolicFactorSize = 0;
557 std::size_t m_symbolicStackSize = 0;
558 Index m_symbolicFrontOrder = 0;
559
560 // Numeric factorization
561
562 // The input matrix's values in compressed order, if it isn't compressed.
563 std::vector<Scalar> m_values;
564 // The front being factored.
565 std::vector<Scalar, aligned_allocator<Scalar>> m_front;
566 // Rows of L in a 2x2 pivot.
567 std::vector<Scalar, aligned_allocator<Scalar>> m_pivotScratch;
568 // Maps a child's rows into its parent.
569 std::vector<StorageIndex> m_childMap;
570 // For each row of a child, the end of its run of rows that stay adjacent in the parent.
571 std::vector<StorageIndex> m_childRunEnd;
572 // Stack of contribution blocks. Each is a packed lower triangle.
573 WorkStack<Scalar> m_stack;
574 // Number of columns each front delayed to its parent.
575 std::vector<StorageIndex> m_numDelayed;
576 // Each front's pivot columns.
577 WorkStack<Scalar> m_L;
578 // Each front's rows after pivoting, in elimination order. The current front's are the last ones, permuted in place,
579 // so a tree of small fronts doesn't copy them from a scratch array.
580 WorkStack<StorageIndex> m_factorRows;
581 std::vector<FactoredFront> m_factoredFronts;
582 // D's 2x2 blocks, in pivot order.
583 std::vector<ScaledBlock> m_blocks;
584 RealVectorType m_D;
585 VectorType m_subdiagonal;
586 PermutationType m_P;
587 PermutationType m_Pinv;
588 // Each pivot's row in elimination order.
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;
594 Index m_numZero = 0;
595 Index m_maxFrontOrder = 0;
596 bool m_hasZeroPivot = false;
597};
598
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;
605
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));
617
618 const auto storedEntries = [](Index pivots, Index below) {
619 return factorSize(pivots, pivots + below) + static_cast<std::size_t>(pivots);
620 };
621
622 // below(child) is a subset of columns(parent) U below(parent) (Liu, 1990), so a merged front keeps its parent's rows
623 // below. Each front's descendants are final when it's visited, because the fronts are postordered.
624 std::vector<StorageIndex> mergedInto(numFronts, none);
625 std::vector<StorageIndex> numPivots(numFronts);
626 // Entries of L in a front, including its diagonal and leaving out explicit zeros.
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]);
631 }
632 Index numMerged = 0;
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)) {
640 mergedInto[s] = p;
641 numPivots[p] = toStorageIndex(pivots);
642 numEntries[p] = entries;
643 ++numMerged;
644 }
645 }
646 if (numMerged == 0) return;
647
648 // Each original front's merged front, in the order of the fronts that weren't merged into a parent.
649 std::vector<StorageIndex> merged(numFronts);
650 const StorageIndex numMergedFronts = toStorageIndex(numFronts - numMerged);
651 {
652 StorageIndex next = numMergedFronts;
653 for (Index s = numFronts - 1; s >= 0; --s) {
654 merged[s] = mergedInto[s] == none ? --next : merged[mergedInto[s]];
655 }
656 }
657
658 // A merged child generally isn't its parent's last child, so the merged tree needs a new postorder to make each
659 // front's columns contiguous and keep contribution blocks on a stack. Any postorder of a tree has the same fill.
660 // Visiting children in increasing order keeps the fronts that weren't merged in their relative order.
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]];
665 }
666 }
667 IndexVectorType postorder;
668 internal::treePostorder(numMergedFronts, rootedParent, postorder);
669
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];
673 }
674 for (Index s = 0; s < numMergedFronts; ++s) firstColumn[s + 1] += firstColumn[s];
675
676 // A front's columns keep their relative order, so every entry stays in the same triangle.
677 std::vector<StorageIndex> newColumnFront(size);
678 {
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;
686 }
687 }
688 }
689
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);
695 }
696}
697
698template <typename MatrixType_, int UpLo_, typename Ordering_>
700 eigen_assert(matrix.rows() == matrix.cols() && "The matrix must be square.");
701
702 const Index size = matrix.rows();
703
704 // Fill-reducing ordering. An empty permutation means the identity.
706 EIGEN_IF_CONSTEXPR ((!std::is_same<OrderingType, NaturalOrdering<StorageIndex>>::value)) {
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,
710 Pinv);
711 }
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);
715
716 // The upper triangle of the ordered matrix.
717 FactorType upper;
718 internal::permute_symm_to_symm<UpLo_, Upper, false>(matrix, upper, Pinv.size() > 0 ? ordered.data() : nullptr);
719
720 // Each column's parent in the elimination tree, or -1 for a root.
721 constexpr StorageIndex none(-1);
722 std::vector<StorageIndex> parent(size);
723 {
724 std::vector<StorageIndex> ancestors(size);
725 internal::simpl_chol_helper<Scalar, StorageIndex>::calc_etree(toStorageIndex(size), upper, parent.data(),
726 ancestors.data());
727 }
728
729 // A postorder doesn't change the fill and lets factorize() keep contribution blocks on a stack.
730 IndexVectorType rootedParent(size);
731 for (Index j = 0; j < size; ++j) rootedParent[j] = parent[j] == none ? toStorageIndex(size) : parent[j];
732
733 // Visiting children from largest to smallest column index places each leaf of an AMD-ordered KKT chain's tree right
734 // before its parent, not O(N) rows away, so a front's rows stay close together in the solution vectors once those
735 // vectors outgrow the cache.
736 IndexVectorType postorder;
737 internal::treePostorder(toStorageIndex(size), rootedParent, postorder, internal::PostorderChildren::Decreasing);
738
739 m_perm.resize(size);
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);
744 }
745
746 // Each column's number of rows below its diagonal in L, from the rows of the upper triangle (Gilbert, Ng and Peyton,
747 // 1994).
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);
754 {
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(), /*doLDLT=*/true);
762 }
763
764 // Fundamental supernodes: column j joins column j - 1's front if it's j - 1's parent and only child, and
765 // count(j - 1) = count(j) + 1. pattern(L_{j-1}) \ {j} is a subset of pattern(L_j), so the counts make them equal.
766 // mergeRelaxedFronts() then relaxes these fronts.
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]]];
775 }
776 }
777 m_frontColumns.clear();
778 std::vector<StorageIndex> columnFront(size);
779 for (Index j = 0; j < size; ++j) {
780 const bool extends =
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);
784 }
785 m_frontColumns.push_back(n);
786 {
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];
794 }
795 std::vector<StorageIndex> newColumn;
796 mergeRelaxedFronts(frontParent, frontBelow, columnFront, newColumn);
797 for (Index j = 0; j < size; ++j) postorder[j] = newColumn[postorder[j]];
798 }
799 const Index numFronts = static_cast<Index>(m_frontColumns.size()) - 1;
800 // Each column of the ordered matrix in m_perm's numbering, and the reverse.
801 const IndexVectorType& columnOf = postorder;
802 std::vector<StorageIndex> orderedColumn(size);
803 for (Index j = 0; j < size; ++j) orderedColumn[columnOf[j]] = toStorageIndex(j);
804
805 // Each front's parent and children. A front's parent holds the parent of its last column.
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];
813 }
814 }
815 for (Index s = 0; s < numFronts; ++s) m_childStart[s + 1] += m_childStart[s];
816 m_children.resize(m_childStart[numFronts]);
817 {
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);
821 }
822 }
823
824 // Each front's columns, then its rows below them: pattern(L_last) for its last column, which is the rows past its
825 // columns in its columns of A and in its children's rows below.
826 m_belowStart.assign(numFronts + 1, 0);
827 m_frontRowList.clear();
828 {
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]]);
832 }
833 m_frontRowList.reserve(numRows);
834 }
835 {
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) {
844 mark[row] = front;
845 m_frontRowList.push_back(row);
846 }
847 };
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]]);
852 }
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]);
859 }
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]]));
863 }
864 }
865 // Sorts each front's rows below with a counting transpose: list each row's fronts, then write the rows back to their
866 // fronts in increasing order.
867 {
868 const auto belowRows = [&](Index s) {
869 return m_frontRowList.begin() + static_cast<std::ptrdiff_t>(m_belowStart[s] + m_frontColumns[s + 1]);
870 };
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];
876 }
877 }
878 for (Index i = 0; i < size; ++i) rowFrontStart[i + 1] += rowFrontStart[i];
879 std::vector<StorageIndex> rowFronts(rowFrontStart[size]);
880 {
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);
886 }
887 }
888 }
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);
895 }
896 }
897 }
898
899 // Where each entry of the input matrix is assembled. The row is global until the loop over fronts below.
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];
904 });
905 for (Index s = 0; s < numFronts; ++s) m_assemblyStart[s + 1] += m_assemblyStart[s];
906 m_assembly.resize(m_assemblyStart[numFronts]);
907 {
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};
915 });
916 }
917
918 // The position of each row in front s, not counting delayed columns: row - first column for its columns, then the
919 // rows below them in order. Each front's children and entries of A take their positions from it.
920 m_belowToParent.resize(m_belowStart[numFronts]);
921 {
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));
930 }
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])]];
935 }
936 }
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];
939 }
940 }
941 }
942
943 m_symbolicFactorSize = 0;
944 m_symbolicStackSize = 0;
945 m_symbolicFrontOrder = 0;
946 {
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]));
956 }
957 stack += packedSize(numBelow);
958 m_symbolicStackSize = numext::maxi(m_symbolicStackSize, stack);
959 }
960 }
961
962 m_numDelayed.resize(numFronts);
963 m_factoredFronts.resize(numFronts);
964 m_pivots.resize(size);
965 m_D.resize(size);
966 m_subdiagonal.resize(size);
967 m_P.resize(size);
968 m_Pinv.resize(size);
969
970 m_info = InvalidInput;
971 m_isInitialized = true;
972}
973
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());
978
979 eigen_assert(static_cast<std::size_t>(matrix.nonZeros()) == m_numValues &&
980 "The matrix must have the analyzed sparsity pattern.");
981 // A compressed matrix is read in place.
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();
988 }
989 values = m_values.data();
990 }
991
992 // Delayed pivots can still outgrow these.
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));
998 }
999
1000 m_L.clear();
1001 m_LNonZeros = 0;
1002 m_factorRows.clear();
1003 m_stack.clear();
1004 m_numPivots = 0;
1005 m_numPositive = 0;
1006 m_numNegative = 0;
1007 m_numZero = 0;
1008 m_maxFrontOrder = 0;
1009 m_hasZeroPivot = false;
1010
1011 const Index numFronts = static_cast<Index>(m_frontColumns.size()) - 1;
1012 // None of these are reallocated during the factorization, but the calls below stop the compiler from proving it.
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]);
1027
1028 Index delayedIn = 0;
1029 for (std::size_t c = childStart[s]; c < childStart[s + 1]; ++c) delayedIn += numDelayed[children[c]];
1030
1031 const Index fullySummed = delayedIn + numColumns;
1032 const Index order = fullySummed + numBelow;
1033 m_maxFrontOrder = numext::maxi(m_maxFrontOrder, order);
1034
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);
1039 // Only the lower triangle is read, but a single fill is cheaper than one per column for a small front. Filling the
1040 // whole of a larger one would also push the working set out of the L1 cache.
1041 if (order < kBlockedFrontMinOrder) {
1042 front.setZero();
1043 } else {
1044 for (Index j = 0; j < order; ++j) front.col(j).tail(order - j).setZero();
1045 }
1046
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;
1051 }
1052
1053 // The delayed rows come first, and the children fill them in below.
1054 const StorageIndex* rowList = frontRowList + belowStart[s] + firstColumn;
1055 internal::smart_copy(rowList, rowList + numColumns + numBelow, rows + delayedIn);
1056
1057 // Extend-add the children's contribution blocks. They're on a stack, so the last child's is on top.
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;
1066
1067 // Without delayed columns on either side, the symbolic map is the map.
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];
1076 }
1077 for (Index i = 0; i < childBelow; ++i) {
1078 m_childMap[delayed + i] = internal::convert_index<StorageIndex>(delayedIn + childMap[i]);
1079 }
1080 childMap = m_childMap.data();
1081 }
1082
1083 // Delayed rows come before the rows below in both the child and the parent, and the rows below keep their
1084 // relative order. So the map is increasing and the lower triangle stays the lower triangle.
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);
1089 } else {
1090 extendAdd(order, block, childMap, childOrder);
1091 }
1092 m_stack.pop(blockSize);
1093 }
1094
1095 const bool isRoot = frontParent[s] == -1;
1096 if (fullySummed == 1 && factorOnePivotFront(s, order, isRoot)) continue;
1097
1098 const Index numPivots = factorFront(order, fullySummed, isRoot);
1099
1100 Scalar* factor = appendFactor(s, numPivots, order);
1101 internal::smart_copy(m_front.data(), m_front.data() + rectangleSize(order, numPivots), factor);
1102
1103 pushToParent(s, order, fullySummed, numPivots);
1104 }
1105
1106 // Roots can't delay, so every pivot, and with it every entry of m_D and m_subdiagonal, has been written.
1107 const Index size = rows();
1108 eigen_internal_assert(m_numPivots == size);
1109
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);
1114 }
1115
1116 // Inertia from the signs of D (Sylvester's law). A 2x2 block with det < 0 has one eigenvalue of each sign; otherwise
1117 // both eigenvalues have the sign of its trace.
1118 bool finite = true;
1119 m_blocks.clear();
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)) {
1127 finite = false;
1128 } else if (m_blocks.back().det < RealScalar(0)) {
1129 ++m_numPositive;
1130 ++m_numNegative;
1131 } else if (d1 + d2 > RealScalar(0)) {
1132 m_numPositive += 2;
1133 } else {
1134 m_numNegative += 2;
1135 }
1136 ++k;
1137 } else if (!(numext::isfinite)(d1)) {
1138 finite = false;
1139 } else if (d1 > RealScalar(0)) {
1140 ++m_numPositive;
1141 } else if (d1 < RealScalar(0)) {
1142 ++m_numNegative;
1143 } else {
1144 ++m_numZero;
1145 }
1146 }
1147
1148 m_info = finite && !m_hasZeroPivot ? Success : NumericalIssue;
1149}
1150
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().");
1156
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));
1163 ++k;
1164 } else {
1165 result += numext::log(numext::abs(m_D[k]));
1166 }
1167 }
1168 return result;
1169}
1170
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));
1179}
1180
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);
1185 Index numRuns = 1;
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) {
1190 runEnd = i + 1;
1191 ++numRuns;
1192 }
1193 m_childRunEnd[i] = internal::convert_index<StorageIndex>(runEnd);
1194 }
1195
1196 if (childOrder < kExtendAddMinRunLength * numRuns) {
1197 scatterAdd(order, block, map, childOrder);
1198 return;
1199 }
1200
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);
1207 block += end - i;
1208 i = end;
1209 }
1210 }
1211}
1212
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))));
1220 }
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));
1225 return result;
1226}
1227
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();
1233}
1234
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);
1239 Index r = -1;
1240 RealScalar largest(0);
1241 rest = RealScalar(0);
1242 const auto visit = [&](Index i, const RealScalar& magnitude) {
1243 if (magnitude > largest) {
1244 rest = largest;
1245 largest = magnitude;
1246 r = i;
1247 } else {
1248 rest = numext::maxi(rest, magnitude);
1249 }
1250 };
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));
1254 return r;
1255}
1256
1257template <typename MatrixType_, int UpLo_, typename Ordering_>
1258EIGEN_ALWAYS_INLINE bool MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::factorOnePivotFront(Index s, Index order,
1259 bool isRoot) {
1260 ConstFrontMap front(m_front.data(), order, order);
1261 const RealScalar d = numext::real(front(0, 0));
1262 if (d == RealScalar(0)) return false;
1263
1264 // The root has no parent to delay to, and has no rows below its only diagonal to bound. With one fully summed column,
1265 // there's no 2x2 pivot to try instead.
1266 if (!isRoot && !(numext::abs(d) >= m_threshold * frontColumnMax(order, 0, 0, -1))) {
1267 appendFactor(s, 0, order);
1268 pushToParent(s, order, 1, 0);
1269 return true;
1270 }
1271
1272 m_D[m_numPivots] = d;
1273 m_subdiagonal[m_numPivots] = Scalar(0);
1274 m_pivots[m_numPivots] = frontRows(order)[0];
1275 ++m_numPivots;
1276 m_numDelayed[s] = 0;
1277
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;
1288 } else {
1289 VectorMap(contribution, length) = ConstVectorMap(column, length) - ConstVectorMap(u + j, length) * lj;
1290 }
1291 contribution += length;
1292 L[j] = numext::conj(lj);
1293 }
1294
1295 return true;
1296}
1297
1298template <typename MatrixType_, int UpLo_, typename Ordering_>
1299void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::pushToParent(Index s, Index order, Index fullySummed,
1300 Index numPivots) {
1301 const Index numDelayed = fullySummed - numPivots;
1302 m_numDelayed[s] = internal::convert_index<StorageIndex>(numDelayed);
1303
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);
1310 }
1311 return;
1312 }
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;
1316 }
1317}
1318
1319template <typename MatrixType_, int UpLo_, typename Ordering_>
1320void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::swapFront(Index order, Index a, Index b) {
1321 if (a == b) return;
1322 if (a > b) std::swap(a, b);
1323
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]);
1327}
1328
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];
1336 ++m_numPivots;
1337
1338 if (d == RealScalar(0)) {
1339 // The pivot test only accepts a zero pivot if its column is zero, so L's column is already zero.
1340 m_hasZeroPivot = true;
1341 return;
1342 }
1343
1344 // Column k becomes L's column as each quotient is computed. Later columns only read the entries below their own row,
1345 // which are still unscaled.
1346 if (order <= kSmallFrontMaxOrder) {
1347 // A front this small is its own panel.
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);
1353 }
1354 return;
1355 }
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);
1360 }
1361 front.col(k).tail(order - panelEnd) = front.col(k).tail(order - panelEnd) / d;
1362}
1363
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];
1376 m_numPivots += 2;
1377
1378 // L = U D^-1, with D scaled by its largest entry to keep its determinant in range.
1379 const ScaledBlock block(d11, d22, numext::abs(d21));
1380 const Scalar b = d21 / block.scale;
1381 const Scalar conjB = numext::conj(b);
1382
1383 const Index numRows = order - k - 2;
1384 // numRows can be zero, where coeffRef() would be out of bounds.
1385 Scalar* u1 = front.data() + rectangleSize(order, k) + (k + 2);
1386 Scalar* u2 = u1 + order;
1387 if (order <= kSmallFrontMaxOrder) {
1388 // A front this small is its own panel.
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;
1395 }
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;
1401 }
1402 for (Index i = 0; i < smallRows; ++i) {
1403 u1[i] = l1[i];
1404 u2[i] = l2[i];
1405 }
1406 front(k + 1, k) = Scalar(0);
1407 return;
1408 }
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;
1416 }
1417 } else {
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;
1422 }
1423
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]),
1427 numRows - offset);
1428 }
1429
1430 front(k + 1, k) = Scalar(0);
1431 internal::smart_copy(l1, l1 + numRows, u1);
1432 internal::smart_copy(l2, l2 + numRows, u2);
1433}
1434
1435template <typename MatrixType_, int UpLo_, typename Ordering_>
1436void MultifrontalLDLT<MatrixType_, UpLo_, Ordering_>::updateTrailing(Index order, Index firstPivot, Index numPivots,
1437 Index panelEnd) {
1438 const Index trailing = order - panelEnd;
1439 if (trailing == 0 || numPivots == 0) return;
1440
1441 FrontMap front(m_front.data(), order, order);
1442 if (m_pivotScratch.size() < rectangleSize(trailing, numPivots)) {
1443 m_pivotScratch.resize(rectangleSize(trailing, numPivots));
1444 }
1445 FrontMap W(m_pivotScratch.data(), trailing, numPivots);
1446 const auto L21 = front.block(panelEnd, firstPivot, trailing, numPivots);
1447
1448 // W = L21 D
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];
1454 ++c;
1455 ++p;
1456 } else {
1457 W.col(c) = L21.col(c) * m_D[p];
1458 }
1459 }
1460
1461 front.bottomRightCorner(trailing, trailing).template triangularView<Lower>() -= W * L21.adjoint();
1462}
1463
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);
1467
1468 // Pivots [0, k) have been applied to the columns before panelEnd, and pivots [applied, k) have yet to be applied to
1469 // the others. Every pivot decision reads only current entries, so it's the one an unblocked factorization would make:
1470 // the panel is flushed before reading a column past its end. After a flush, applied == k and any column can be read.
1471 Index k = 0;
1472 Index applied = 0;
1473 Index panelEnd = order < kBlockedFrontMinOrder ? order : numext::mini(Index(kPanelWidth), fullySummed);
1474 const auto flush = [&] {
1475 updateTrailing(order, applied, k - applied, panelEnd);
1476 applied = k;
1477 panelEnd = numext::mini(k + kPanelWidth, fullySummed);
1478 };
1479
1480 // A sweep tests each active column once, continuing past accepted pivots, so a column that keeps failing costs one
1481 // test per sweep instead of one per pivot. Columns [next, tail) are untested in this sweep. The front has no
1482 // acceptable pivot once every active column has failed since the last pivot, because those tests all read the same
1483 // values.
1484 Index next = 0;
1485 Index tail = fullySummed;
1486 bool acceptedPivot = false;
1487 // Without moved columns, the columns from here to the end have failed since the last pivot.
1488 Index lastPivotEnd = 0;
1489
1490 while (k < fullySummed) {
1491 if (k >= panelEnd) flush();
1492
1493 if (next >= tail) {
1494 next = k;
1495 if (acceptedPivot) {
1496 tail = tail == fullySummed ? lastPivotEnd : fullySummed;
1497 acceptedPivot = false;
1498 continue;
1499 }
1500 tail = fullySummed;
1501 if (!isRoot) break;
1502
1503 if (applied < k) flush();
1504
1505 // The pivot tests guarantee a pivot at the root, so only rounding error or a non-finite entry gets here. Take the
1506 // largest diagonal instead of leaving the column unfactored.
1507 Index largest;
1508 front.diagonal().segment(k, fullySummed - k).real().cwiseAbs().template maxCoeff<PropagateNumbers>(&largest);
1509 largest += k;
1510 swapFront(order, k, largest);
1511
1512 // A zero here means the active diagonal is zero and every column is nonzero. The largest finite entry would pass
1513 // the 2x2 test, so some entry's magnitude isn't finite, and the pivot is NaN.
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);
1518 }
1519
1520 eliminate1x1(order, k, panelEnd);
1521 ++k;
1522 next = k;
1523 continue;
1524 }
1525
1526 if (next >= panelEnd) {
1527 flush();
1528
1529 // Move the columns that failed in [k, next) past the untested ones, which fills the panel with untested columns
1530 // and lets it accept pivots without a flush for each one.
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);
1534 next = k;
1535 tail = k + numUntested;
1536 }
1537
1538 const Index j = next;
1539 const RealScalar djj = numext::real(front(j, j));
1540 const RealScalar absDjj = numext::abs(djj);
1541
1542 // A zero pivot eliminates nothing, so it's accepted only if its column is exactly zero.
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);
1547 ++k;
1548 next = j + 1;
1549 lastPivotEnd = next;
1550 acceptedPivot = true;
1551 continue;
1552 }
1553
1554 // Try a 2x2 pivot with the largest fully summed off-diagonal in column j.
1555 RealScalar columnJ;
1556 const Index r = largestFullySummed(order, k, fullySummed, j, columnJ);
1557 if (r == -1) {
1558 ++next;
1559 continue;
1560 }
1561 if (r >= panelEnd && applied < k) flush();
1562
1563 // With D = scale [a b*; b c], |D^-1| = 1/(scale |det|) [|c| |b|; |b| |a|] where det = a c - |b|^2.
1564 //
1565 // |det| >= |b|^2 / 2 gives |a c| + |b|^2 <= 5 |det|, so det and the solves with D lose at most a few digits to
1566 // cancellation. For the pair holding a root front's largest off-diagonal, b = 1 and |a|, |c| < u <= 1/2 if neither
1567 // passes the 1x1 test, so |det| >= 1 - u^2 >= 3/4 and the root guarantee still holds.
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);
1579 // Swapping k and j moved whatever was at k to j.
1580 swapFront(order, k + 1, r == k ? j : r);
1581 eliminate2x2(order, k, panelEnd);
1582 k += 2;
1583 next = numext::maxi(j + 1, k);
1584 lastPivotEnd = next;
1585 acceptedPivot = true;
1586 } else {
1587 ++next;
1588 }
1589 }
1590
1591 flush();
1592 return k;
1593}
1594
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.");
1599
1600 // A front's rows are in elimination order, and L's rows and columns are in pivot order.
1601 std::vector<StorageIndex> pivotOf(rows());
1602 for (Index k = 0; k < rows(); ++k) pivotOf[m_pivots[k]] = internal::convert_index<StorageIndex>(k);
1603
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));
1615 }
1616 }
1617
1618 FactorType result(rows(), cols());
1619 result.setFromTriplets(entries.begin(), entries.end());
1620 return result;
1621}
1622
1623#ifndef EIGEN_PARSED_BY_DOXYGEN
1624template <typename MatrixType_, int UpLo_, typename Ordering_>
1625template <typename Rhs, typename Dest>
1627 MatrixBase<Dest>& dest) const {
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());
1631
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);
1637 }
1638
1639 // Each front's rows of X, so a large factor applies as one dense product.
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);
1644 }
1645 };
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);
1649 }
1650 };
1651
1652 // L Y = B
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;
1665 }
1666 }
1667 } else {
1668 const Index numBelow = order - numPivots;
1669 gather(rows, order);
1670 // One right-hand side takes the vector kernels, which don't pack L.
1671 if (numRhs == 1) {
1672 auto y = Y.col(0);
1673 L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(y.head(numPivots));
1674 y.segment(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * y.head(numPivots);
1675 } else {
1676 L.topRows(numPivots).template triangularView<UnitLower>().solveInPlace(Y.topRows(numPivots));
1677 Y.middleRows(numPivots, numBelow).noalias() -= L.bottomRows(numBelow) * Y.topRows(numPivots);
1678 }
1679 scatter(rows, order);
1680 }
1681 }
1682
1683 // D Z = Y. A zero pivot gets a zero solution, the minimum norm solution for that block.
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;
1696 ++block;
1697 ++k;
1698 } else if (m_D[k] != RealScalar(0)) {
1699 x[row] /= m_D[k];
1700 } else {
1701 x[row] = Scalar(0);
1702 }
1703 }
1704 }
1705
1706 // L^* W = Z
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]];
1719 x[rows[j]] = value;
1720 }
1721 }
1722 } else {
1723 const Index numBelow = order - numPivots;
1724 gather(rows, order);
1725 if (numRhs == 1) {
1726 auto y = Y.col(0);
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));
1729 } else {
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));
1732 }
1733 scatter(rows, numPivots);
1734 }
1735 }
1736
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);
1739 }
1740}
1741#endif // EIGEN_PARSED_BY_DOXYGEN
1742
1743} // end namespace Eigen
1744
1745#endif // EIGEN_MULTIFRONTAL_LDLT_H
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
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
Definition Ordering.h:80
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
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