12#ifndef EIGEN_PARTIALLU_H
13#define EIGEN_PARTIALLU_H
16#include "./InternalHeaderCheck.h"
21template <
typename MatrixType_,
typename PermutationIndex_>
22struct traits<PartialPivLU<MatrixType_, PermutationIndex_> > : traits<MatrixType_> {
23 using XprKind = MatrixXpr;
24 using StorageKind = SolverStorage;
25 using StorageIndex = PermutationIndex_;
26 using BaseTraits = traits<MatrixType_>;
27 enum { Flags = BaseTraits::Flags &
RowMajorBit, CoeffReadCost = Dynamic };
66template <
typename MatrixType_,
typename PermutationIndex_>
69 using MatrixType = MatrixType_;
75 MaxRowsAtCompileTime = MatrixType::MaxRowsAtCompileTime,
76 MaxColsAtCompileTime = MatrixType::MaxColsAtCompileTime
78 using PermutationIndex = PermutationIndex_;
81 using PlainObject =
typename MatrixType::PlainObject;
90 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
117 template <
typename InputType>
127 template <
typename InputType>
130 template <
typename InputType>
132 m_lu.resize(matrix.
rows(), matrix.
cols());
145 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
152 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
156#ifdef EIGEN_PARSED_BY_DOXYGEN
174 template <
typename Rhs>
182 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
183 return internal::rcond_estimate_helper(m_l1_norm, *
this);
194 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
263 constexpr Index rows() const noexcept {
return m_lu.rows(); }
264 constexpr Index cols() const noexcept {
return m_lu.cols(); }
266#ifndef EIGEN_PARSED_BY_DOXYGEN
267 template <
typename RhsType,
typename DstType>
268 EIGEN_DEVICE_FUNC
void _solve_impl(
const RhsType& rhs, DstType& dst)
const {
280 m_lu.template triangularView<UnitLower>().solveInPlace(dst);
283 m_lu.template triangularView<Upper>().solveInPlace(dst);
286 template <
bool Conjugate,
typename RhsType,
typename DstType>
287 EIGEN_DEVICE_FUNC
void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const {
295 EIGEN_INTERNAL_ASSERT_SOLVER_RHS(m_lu, rhs,
true);
298 dst = m_lu.template triangularView<Upper>().transpose().template conjugateIf<Conjugate>().solve(rhs);
300 m_lu.template triangularView<UnitLower>().transpose().template conjugateIf<Conjugate>().solveInPlace(dst);
307 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
313 TranspositionType m_rowsTranspositions;
314 RealScalar m_l1_norm;
316 bool m_isInitialized;
319template <
typename MatrixType,
typename PermutationIndex>
321 : m_lu(), m_p(), m_rowsTranspositions(), m_l1_norm(0), m_det_p(0), m_isInitialized(false) {}
323template <
typename MatrixType,
typename PermutationIndex>
325 : m_lu(
size,
size), m_p(
size), m_rowsTranspositions(
size), m_l1_norm(0), m_det_p(0), m_isInitialized(false) {}
327template <
typename MatrixType,
typename PermutationIndex>
328template <
typename InputType>
330 : m_lu(matrix.rows(), matrix.cols()),
332 m_rowsTranspositions(matrix.rows()),
335 m_isInitialized(false) {
339template <
typename MatrixType,
typename PermutationIndex>
340template <
typename InputType>
344 m_rowsTranspositions(matrix.rows()),
347 m_isInitialized(false) {
355template <
int K,
int Size,
bool Last = (K == Size - 1)>
356struct unrolled_partial_lu_step {
357 template <
typename MatrixTypeRef,
typename PivIndex>
358 static EIGEN_STRONG_INLINE
void run(MatrixTypeRef& lu, PivIndex* row_transpositions, PivIndex& nb_transpositions,
359 Index& first_zero_pivot) {
360 using Scalar =
typename MatrixTypeRef::Scalar;
361 using Scoring = scalar_score_coeff_op<Scalar>;
362 using Score =
typename Scoring::result_type;
363 constexpr int Remaining = Size - K - 1;
365 Index row_of_biggest_in_col;
366 const Score biggest_in_corner =
367 lu.col(K).template tail<Size - K>().unaryExpr(Scoring()).maxCoeff(&row_of_biggest_in_col);
368 row_of_biggest_in_col += K;
369 row_transpositions[K] = PivIndex(row_of_biggest_in_col);
370 if (!numext::is_exactly_zero(biggest_in_corner)) {
371 if (K != row_of_biggest_in_col) {
372 lu.row(K).swap(lu.row(row_of_biggest_in_col));
375 lu.col(K).template tail<Remaining>() /= lu.coeff(K, K);
376 }
else if (first_zero_pivot == -1) {
377 first_zero_pivot = K;
379 lu.template bottomRightCorner<Remaining, Remaining>().noalias() -=
380 lu.col(K).template tail<Remaining>() * lu.row(K).template tail<Remaining>();
381 unrolled_partial_lu_step<K + 1, Size>::run(lu, row_transpositions, nb_transpositions, first_zero_pivot);
385template <
int K,
int Size>
386struct unrolled_partial_lu_step<K, Size, true> {
387 template <
typename MatrixTypeRef,
typename PivIndex>
388 static EIGEN_STRONG_INLINE
void run(MatrixTypeRef& lu, PivIndex* row_transpositions, PivIndex&,
389 Index& first_zero_pivot) {
390 using Scoring = scalar_score_coeff_op<typename MatrixTypeRef::Scalar>;
391 row_transpositions[K] = PivIndex(K);
392 if (numext::is_exactly_zero(Scoring()(lu.coeff(K, K))) && first_zero_pivot == -1) first_zero_pivot = K;
397template <
bool Unroll,
int Size>
398struct unrolled_partial_lu {
399 template <
typename MatrixTypeRef,
typename PivIndex>
400 static EIGEN_STRONG_INLINE
bool run(MatrixTypeRef&, PivIndex*, PivIndex&, Index&) {
406struct unrolled_partial_lu<true, Size> {
407 template <
typename MatrixTypeRef,
typename PivIndex>
408 static EIGEN_STRONG_INLINE
bool run(MatrixTypeRef& lu, PivIndex* row_transpositions, PivIndex& nb_transpositions,
409 Index& first_zero_pivot) {
410 nb_transpositions = 0;
411 first_zero_pivot = -1;
412 unrolled_partial_lu_step<0, Size>::run(lu, row_transpositions, nb_transpositions, first_zero_pivot);
418template <
typename Scalar,
int StorageOrder,
typename PivIndex,
int SizeAtCompileTime = Dynamic>
419struct generic_partial_lu_impl {
420 static constexpr int UnBlockedBound = 16;
421 static constexpr bool UnBlockedAtCompileTime = SizeAtCompileTime != Dynamic && SizeAtCompileTime <= UnBlockedBound;
422 static constexpr int ActualSizeAtCompileTime = UnBlockedAtCompileTime ? SizeAtCompileTime : Dynamic;
426 static constexpr int UnrolledBound = 12;
427 static constexpr bool UnrolledAtCompileTime = UnBlockedAtCompileTime && SizeAtCompileTime <= UnrolledBound;
429 static constexpr int RRows = SizeAtCompileTime == 2 ? 1 : Dynamic;
430 static constexpr int RCols = SizeAtCompileTime == 2 ? 1 : Dynamic;
431 using MatrixType = Matrix<Scalar, ActualSizeAtCompileTime, ActualSizeAtCompileTime, StorageOrder>;
432 using MatrixTypeRef = Ref<MatrixType>;
433 using BlockType = Ref<Matrix<Scalar, Dynamic, Dynamic, StorageOrder>>;
434 using RealScalar =
typename MatrixType::RealScalar;
436 static void apply_row_transpositions(BlockType& matrix, Index first, Index count,
const PivIndex* transpositions) {
437 EIGEN_IF_CONSTEXPR (StorageOrder ==
ColMajor) {
439 for (Index j = 0; j < matrix.cols(); ++j)
440 for (Index i = first; i < first + count; ++i)
441 numext::swap(matrix.coeffRef(i, j), matrix.coeffRef(transpositions[i], j));
443 for (Index i = first; i < first + count; ++i) matrix.row(i).swap(matrix.row(transpositions[i]));
457 static Index unblocked_lu(MatrixTypeRef& lu, PivIndex* row_transpositions, PivIndex& nb_transpositions) {
458 using Scoring = scalar_score_coeff_op<Scalar>;
459 using Score =
typename Scoring::result_type;
461 Index first_zero_pivot;
462 if (unrolled_partial_lu<UnrolledAtCompileTime, SizeAtCompileTime>::run(lu, row_transpositions, nb_transpositions,
464 return first_zero_pivot;
466 const Index rows = lu.rows();
467 const Index cols = lu.cols();
468 const Index size = (std::min)(rows, cols);
471 const bool process_last_row_separately = UnBlockedAtCompileTime || rows == cols;
472 const Index endk = process_last_row_separately ? size - 1 : size;
473 nb_transpositions = 0;
474 Index first_zero_pivot = -1;
475 for (Index k = 0; k < endk; ++k) {
476 int rrows = internal::convert_index<int>(rows - k - 1);
477 int rcols = internal::convert_index<int>(cols - k - 1);
479 Index row_of_biggest_in_col;
480 Score biggest_in_corner = lu.col(k).tail(rows - k).unaryExpr(Scoring()).maxCoeff(&row_of_biggest_in_col);
481 row_of_biggest_in_col += k;
483 row_transpositions[k] = PivIndex(row_of_biggest_in_col);
485 if (!numext::is_exactly_zero(biggest_in_corner)) {
486 if (k != row_of_biggest_in_col) {
487 lu.row(k).swap(lu.row(row_of_biggest_in_col));
491 lu.col(k).tail(
fix<RRows>(rrows)) /= lu.coeff(k, k);
492 }
else if (first_zero_pivot == -1) {
495 first_zero_pivot = k;
499 if (rrows > 0 && rcols > 0)
505 if (process_last_row_separately) {
507 row_transpositions[k] = PivIndex(k);
508 if (numext::is_exactly_zero(Scoring()(lu(k, k))) && first_zero_pivot == -1) first_zero_pivot = k;
511 return first_zero_pivot;
529 static Index blocked_lu(Index rows, Index cols, Scalar* lu_data, Index luStride, PivIndex* row_transpositions,
530 PivIndex& nb_transpositions, Index maxBlockSize = 256) {
531 MatrixTypeRef lu = MatrixType::Map(lu_data, rows, cols, OuterStride<>(luStride));
533 const Index size = (std::min)(rows, cols);
536 EIGEN_IF_CONSTEXPR (UnBlockedAtCompileTime) {
537 return unblocked_lu(lu, row_transpositions, nb_transpositions);
538 }
else if (size <= UnBlockedBound) {
539 return unblocked_lu(lu, row_transpositions, nb_transpositions);
546 blockSize = size / 8;
547 blockSize = (blockSize / 16) * 16;
548 blockSize = (std::min)((std::max)(blockSize, Index(8)), maxBlockSize);
551 nb_transpositions = 0;
552 Index first_zero_pivot = -1;
553 for (Index k = 0; k < size; k += blockSize) {
554 Index bs = (std::min)(size - k, blockSize);
555 Index trows = rows - k - bs;
556 Index tsize = cols - k - bs;
562 BlockType A_2 = lu.block(0, k + bs, rows, tsize);
563 BlockType A11 = lu.block(k, k, bs, bs);
564 BlockType A12 = lu.block(k, k + bs, bs, tsize);
565 BlockType A21 = lu.block(k + bs, k, trows, bs);
566 BlockType A22 = lu.block(k + bs, k + bs, trows, tsize);
568 PivIndex nb_transpositions_in_panel;
571 Index ret = blocked_lu(trows + bs, bs, &lu.coeffRef(k, k), luStride, row_transpositions + k,
572 nb_transpositions_in_panel, 16);
573 if (ret >= 0 && first_zero_pivot == -1) first_zero_pivot = k + ret;
575 nb_transpositions += nb_transpositions_in_panel;
578 BlockType A_0 = lu.block(0, 0, rows, k);
579 for (Index i = k; i < k + bs; ++i) row_transpositions[i] += internal::convert_index<PivIndex>(k);
580 apply_row_transpositions(A_0, k, bs, row_transpositions);
585 apply_row_transpositions(A_2, k, bs, row_transpositions);
588 A11.template triangularView<UnitLower>().solveInPlace(A12);
590 A22.noalias() -= A21 * A12;
593 return first_zero_pivot;
597template <
typename Scalar,
int StorageOrder,
typename PivIndex,
int SizeAtCompileTime = Dynamic>
598struct partial_lu_impl : generic_partial_lu_impl<Scalar, StorageOrder, PivIndex, SizeAtCompileTime> {};
602template <
typename MatrixType,
typename TranspositionType>
603void partial_lu_inplace(MatrixType& lu, TranspositionType& row_transpositions,
604 typename TranspositionType::StorageIndex& nb_transpositions) {
606 if (lu.rows() == 0 || lu.cols() == 0) {
607 nb_transpositions = 0;
610 EIGEN_INTERNAL_ASSERT_SIZE_MATCHES_COLS(row_transpositions.indices(), lu);
611 eigen_assert(row_transpositions.size() < 2 ||
612 (&row_transpositions.coeffRef(1) - &row_transpositions.coeffRef(0)) == 1);
614 if (EIGEN_PREDICT_FALSE(MatrixType::InnerStrideAtCompileTime != 1 && lu.innerStride() != 1)) {
616 typename plain_matrix_type<MatrixType>::type contiguous = lu;
617 partial_lu_inplace(contiguous, row_transpositions, nb_transpositions);
623 typename TranspositionType::StorageIndex,
624 internal::min_size_prefer_fixed(MatrixType::RowsAtCompileTime, MatrixType::ColsAtCompileTime)>::
625 blocked_lu(lu.rows(), lu.cols(), &lu.coeffRef(0, 0), lu.outerStride(), &row_transpositions.coeffRef(0),
632template <
typename Derived>
633typename traits<Derived>::Scalar partial_lu_determinant(
const Derived& m) {
634 using Scalar =
typename traits<Derived>::Scalar;
635 if (m.rows() == 0)
return Scalar(1);
636 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
638 using PlainObject =
typename plain_matrix_type<Derived>::type;
639 using TranspositionType =
640 Transpositions<PlainObject::RowsAtCompileTime, PlainObject::MaxRowsAtCompileTime, DefaultPermutationIndex>;
642 eigen_assert(m.rows() < NumTraits<DefaultPermutationIndex>::highest());
645 TranspositionType row_transpositions(lu.rows());
646 typename TranspositionType::StorageIndex nb_transpositions;
647 partial_lu_inplace(lu, row_transpositions, nb_transpositions);
649 return Scalar((nb_transpositions % 2) ? -1 : 1) * internal::scaled_prod(lu.diagonal()).value();
654template <
typename MatrixType,
typename PermutationIndex>
655void PartialPivLU<MatrixType, PermutationIndex>::compute() {
656 eigen_assert(m_lu.rows() < NumTraits<PermutationIndex>::highest());
659 m_l1_norm = m_lu.cwiseAbs().colwise().sum().maxCoeff();
661 m_l1_norm = RealScalar(0);
663 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_lu,
"PartialPivLU is only for square (and moreover invertible) matrices");
664 const Index size = m_lu.rows();
666 m_rowsTranspositions.resize(size);
668 typename TranspositionType::StorageIndex nb_transpositions;
669 internal::partial_lu_inplace(m_lu, m_rowsTranspositions, nb_transpositions);
670 m_det_p = (nb_transpositions % 2) ? -1 : 1;
672 m_p = m_rowsTranspositions;
674 m_isInitialized =
true;
677template <
typename MatrixType,
typename PermutationIndex>
680 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
681 return Scalar(m_det_p) * internal::scaled_prod(m_lu.diagonal()).value();
684template <
typename MatrixType,
typename PermutationIndex>
687 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
688 return internal::scaled_prod(m_lu.diagonal()).abs();
691template <
typename MatrixType,
typename PermutationIndex>
694 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
695 return internal::log_abs_prod(m_lu.diagonal());
698template <
typename MatrixType,
typename PermutationIndex>
699typename PartialPivLU<MatrixType, PermutationIndex>::Scalar
701 eigen_assert(m_isInitialized &&
"PartialPivLU is not initialized.");
702 return Scalar(m_det_p) * m_lu.diagonal().array().sign().prod();
708template <
typename MatrixType,
typename PermutationIndex>
710 eigen_assert(m_isInitialized &&
"LU is not initialized.");
712 MatrixType res = m_lu.template triangularView<UnitLower>().toDenseMatrix() * m_lu.template triangularView<Upper>();
715 res = m_p.inverse() * res;
725template <
typename DstXprType,
typename MatrixType,
typename PermutationIndex>
728 internal::assign_op<typename DstXprType::Scalar, typename PartialPivLU<MatrixType, PermutationIndex>::Scalar>,
732 static void run(DstXprType& dst,
const SrcXprType& src,
733 const internal::assign_op<typename DstXprType::Scalar, typename LuType::Scalar>&) {
734 dst = src.nestedExpression().solve(MatrixType::Identity(src.rows(), src.cols()));
747template <
typename Derived>
748template <
typename PermutationIndex>
762template <
typename Derived>
763template <
typename PermutationIndex>
EvalReturnType eval() const
Definition DenseBase.h:389
Expression of the inverse of another expression.
Definition Inverse.h:44
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
LU decomposition of a matrix with partial pivoting, and related features.
Definition PartialPivLU.h:67
PartialPivLU(Index size)
Default Constructor with memory preallocation.
Definition PartialPivLU.h:324
RealScalar logAbsDeterminant() const
Definition PartialPivLU.h:693
Solve< PartialPivLU, Rhs > solve(const MatrixBase< Rhs > &b) const
MatrixType reconstructedMatrix() const
Definition PartialPivLU.h:709
Scalar signDeterminant() const
Definition PartialPivLU.h:700
const MatrixType & matrixLU() const
Definition PartialPivLU.h:144
ComputationInfo info() const
Reports whether the LU factorization was successful.
Definition PartialPivLU.h:89
RealScalar rcond() const
Definition PartialPivLU.h:181
PartialPivLU(const EigenBase< InputType > &matrix)
Definition PartialPivLU.h:329
PartialPivLU()
Default Constructor.
Definition PartialPivLU.h:320
const PermutationType & permutationP() const
Definition PartialPivLU.h:151
PartialPivLU(EigenBase< InputType > &matrix)
Definition PartialPivLU.h:341
Inverse< PartialPivLU > inverse() const
Definition PartialPivLU.h:193
Scalar determinant() const
Definition PartialPivLU.h:678
RealScalar absDeterminant() const
Definition PartialPivLU.h:686
InverseReturnType transpose() const
Definition PermutationMatrix.h:234
Permutation matrix.
Definition PermutationMatrix.h:346
Pseudo expression representing a solving operation.
Definition Solve.h:63
constexpr PartialPivLU< MatrixType_, PermutationIndex_ > & derived()
Represents a sequence of transpositions (row/column interchange)
Definition Transpositions.h:144
ComputationInfo
Definition Constants.h:455
@ Success
Definition Constants.h:457
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int RowMajorBit
Definition Constants.h:71
Definition EigenBase.h:34
constexpr Index cols() const noexcept
Definition EigenBase.h:62
constexpr Derived & derived()
Definition EigenBase.h:50
constexpr Index rows() const noexcept
Definition EigenBase.h:60
constexpr Index size() const noexcept
Definition EigenBase.h:65
Eigen::Index Index
The interface type of indices.
Definition EigenBase.h:44