387 EIGEN_DEVICE_FUNC
constexpr Index rows() const noexcept {
return m_matrix.rows(); }
388 EIGEN_DEVICE_FUNC
constexpr Index cols() const noexcept {
return m_matrix.cols(); }
399 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
403#ifndef EIGEN_PARSED_BY_DOXYGEN
404 template <
typename RhsType,
typename DstType>
405 void _solve_impl(
const RhsType& rhs, DstType& dst)
const;
407 template <
bool Conjugate,
typename RhsType,
typename DstType>
408 void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const;
412 EIGEN_STATIC_ASSERT_NON_INTEGER(Scalar)
415 template <
typename Derived>
420 template <
bool Conjugate,
typename Derived>
426 void computeInertia();
430 static RealScalar scaledBlockDeterminant(
const RealScalar& d11,
const RealScalar& d22,
const RealScalar& d21);
436 using DeterminantProduct =
437 std::conditional_t<internal::has_scaled_product<RealScalar>::value, internal::scaled_product<RealScalar>,
438 internal::bunch_kaufman_balanced_product<RealScalar>>;
439 DeterminantProduct determinantD()
const;
442 RealScalar m_l1_norm;
443 TranspositionType m_transpositions;
444 TmpVectorType m_subdiag;
445 WorkspaceType m_workspace;
449 bool m_isInitialized;
458template <
typename RealScalar>
459EIGEN_DEVICE_FUNC
inline RealScalar bunch_kaufman_alpha() {
460 return (RealScalar(1) + numext::sqrt(RealScalar(17))) / RealScalar(8);
465template <
typename Scalar>
466inline Index bunch_kaufman_blocksize() {
467#ifdef EIGEN_BUNCHKAUFMAN_BLOCKSIZE
468 return Index(EIGEN_BUNCHKAUFMAN_BLOCKSIZE);
477template <
bool IsComplex>
478struct bunch_kaufman_magnitude {
479 template <
typename VectorType>
480 static auto run(
const VectorType& v) ->
decltype(v.cwiseAbs()) {
485struct bunch_kaufman_magnitude<true> {
486 template <
typename VectorType>
487 static auto run(
const VectorType& v) ->
decltype(v.real().cwiseAbs() + v.imag().cwiseAbs()) {
488 return v.real().cwiseAbs() + v.imag().cwiseAbs();
495template <
bool LastOnTies = false,
typename VectorType>
496typename NumTraits<typename VectorType::Scalar>::Real bunch_kaufman_max(
const VectorType& v, Index* index =
nullptr) {
497 using Magnitude = bunch_kaufman_magnitude<NumTraits<typename VectorType::Scalar>::IsComplex>;
498 if (index ==
nullptr)
return Magnitude::run(v).maxCoeff();
499 EIGEN_IF_CONSTEXPR (LastOnTies) {
500 const typename NumTraits<typename VectorType::Scalar>::Real m = Magnitude::run(v.reverse()).maxCoeff(index);
501 *index = v.size() - 1 - *index;
504 return Magnitude::run(v).maxCoeff(index);
511struct bunch_kaufman<
Lower> {
521 template <
bool LastOnTies = false,
typename MatrixType,
typename TranspositionType,
typename SubDiagType>
522 static Index unblocked(MatrixType& mat, TranspositionType& transpositions, SubDiagType& subdiag, Index k0 = 0) {
523 using Scalar =
typename MatrixType::Scalar;
524 using RealScalar =
typename MatrixType::RealScalar;
525 using StorageIndex =
typename TranspositionType::StorageIndex;
526 const Index n = mat.rows();
527 const RealScalar alpha = bunch_kaufman_alpha<RealScalar>();
534 const RealScalar absakk = numext::abs(numext::real(mat.coeff(k, k)));
538 RealScalar colmax(0);
541 colmax = bunch_kaufman_max<LastOnTies>(mat.col(k).tail(n - k - 1), &rel);
545 if (numext::is_exactly_zero((numext::maxi)(absakk, colmax)) || (numext::isnan)(absakk)) {
548 if (info == 0) info = k + 1;
549 mat.coeffRef(k, k) = Scalar(numext::real(mat.coeff(k, k)));
550 }
else if (absakk >= alpha * colmax) {
555 RealScalar rowmax = bunch_kaufman_max(mat.row(imax).segment(k, imax - k));
557 RealScalar rowmax2 = bunch_kaufman_max(mat.col(imax).tail(n - imax - 1));
558 rowmax = (numext::maxi)(rowmax, rowmax2);
560 if (absakk >= alpha * colmax * (colmax / rowmax)) {
563 }
else if (numext::abs(numext::real(mat.coeff(imax, imax))) >= alpha * rowmax) {
573 const Index kk = k + kstep - 1;
574 if (kp != kk) selfadjoint_swap_lower(mat, kk, kp);
577 transpositions.coeffRef(k) = StorageIndex(kp);
578 subdiag.coeffRef(k) = Scalar(0);
580 const RealScalar dkk = numext::real(mat.coeff(k, k));
581 mat.coeffRef(k, k) = Scalar(dkk);
582 const Index rs = n - k - 1;
584 if (!numext::is_exactly_zero(dkk)) {
586 auto w = mat.col(k).tail(rs);
587 mat.block(k + 1, k + 1, rs, rs).template selfadjointView<Lower>().rankUpdate(w, RealScalar(-1) / dkk);
589 }
else if (info == 0) {
595 transpositions.coeffRef(k) = StorageIndex(k);
596 transpositions.coeffRef(k + 1) = StorageIndex(kp);
598 const RealScalar d11 = numext::real(mat.coeff(k, k));
599 const RealScalar d22 = numext::real(mat.coeff(k + 1, k + 1));
600 const Scalar d21 = mat.coeff(k + 1, k);
601 mat.coeffRef(k, k) = Scalar(d11);
602 mat.coeffRef(k + 1, k + 1) = Scalar(d22);
610 const Scalar cjd = numext::conj(d21);
611 const Scalar ak = numext::divide(d22, d21);
612 const Scalar akm1 = numext::divide(d11, cjd);
613 const RealScalar denom = numext::real(ak * akm1) - RealScalar(1);
619 if (info == 0 && !(denom < RealScalar(0) && denom > RealScalar(-2))) info = k + 1;
621 const Index rs = n - k - 2;
636 const RealScalar t = RealScalar(1) / denom;
637 auto c0 = mat.col(k).tail(rs);
638 auto c1 = mat.col(k + 1).tail(rs);
639 for (Index j = 0; j < rs; ++j) {
640 const Scalar u0 = c0.coeff(j);
641 const Scalar u1 = c1.coeff(j);
642 const Scalar l0 = t * numext::divide(ak * u0 - u1, cjd);
643 const Scalar l1 = t * numext::divide(akm1 * u1 - u0, d21);
644 const Index len = rs - j;
645 mat.col(k + 2 + j).tail(len) -= numext::conj(l0) * c0.tail(len) + numext::conj(l1) * c1.tail(len);
650 EIGEN_IF_CONSTEXPR (NumTraits<Scalar>::IsComplex) {
651 mat.coeffRef(k + 2 + j, k + 2 + j) = Scalar(numext::real(mat.coeff(k + 2 + j, k + 2 + j)));
656 subdiag.coeffRef(k) = d21;
657 subdiag.coeffRef(k + 1) = Scalar(0);
658 mat.coeffRef(k + 1, k) = Scalar(0);
671 template <
bool LastOnTies =
false,
typename MatrixType,
typename WorkspaceType,
typename TranspositionType,
672 typename SubDiagType>
673 static Index partial_factor(MatrixType& mat, Index k0, Index nb, WorkspaceType& W, TranspositionType& transpositions,
674 SubDiagType& subdiag, Index& info) {
675 using Scalar =
typename MatrixType::Scalar;
676 using RealScalar =
typename MatrixType::RealScalar;
677 using StorageIndex =
typename TranspositionType::StorageIndex;
678 const Index n = mat.rows();
679 const RealScalar alpha = bunch_kaufman_alpha<RealScalar>();
680 constexpr bool is_complex = NumTraits<Scalar>::IsComplex;
684 const Index jc = k0 + j;
685 const Index h = n - jc;
689 W.col(j).segment(jc, h) = mat.col(jc).segment(jc, h);
690 EIGEN_IF_CONSTEXPR (is_complex) W.coeffRef(jc, j) = Scalar(numext::real(W.coeff(jc, j)));
692 W.col(j).segment(jc, h).noalias() -= mat.block(jc, k0, h, j) * W.row(jc).head(j).adjoint();
693 EIGEN_IF_CONSTEXPR (is_complex) W.coeffRef(jc, j) = Scalar(numext::real(W.coeff(jc, j)));
698 const RealScalar absakk = numext::abs(numext::real(W.coeff(jc, j)));
700 RealScalar colmax(0);
703 colmax = bunch_kaufman_max<LastOnTies>(W.col(j).segment(jc + 1, n - jc - 1), &rel);
707 if (numext::is_exactly_zero((numext::maxi)(absakk, colmax)) || (numext::isnan)(absakk)) {
709 if (info == 0) info = jc + 1;
710 }
else if (absakk >= alpha * colmax) {
715 const Index hr = imax - jc;
716 if (hr > 0) W.col(j + 1).segment(jc, hr) = mat.row(imax).segment(jc, hr).adjoint();
717 W.col(j + 1).segment(imax, n - imax) = mat.col(imax).segment(imax, n - imax);
718 EIGEN_IF_CONSTEXPR (is_complex) W.coeffRef(imax, j + 1) = Scalar(numext::real(W.coeff(imax, j + 1)));
720 W.col(j + 1).segment(jc, n - jc).noalias() -= mat.block(jc, k0, n - jc, j) * W.row(imax).head(j).adjoint();
721 EIGEN_IF_CONSTEXPR (is_complex) W.coeffRef(imax, j + 1) = Scalar(numext::real(W.coeff(imax, j + 1)));
724 RealScalar rowmax(0);
725 if (imax > jc) rowmax = bunch_kaufman_max(W.col(j + 1).segment(jc, imax - jc));
727 RealScalar rowmax2 = bunch_kaufman_max(W.col(j + 1).segment(imax + 1, n - imax - 1));
728 rowmax = (numext::maxi)(rowmax, rowmax2);
730 if (absakk >= alpha * colmax * (colmax / rowmax)) {
732 }
else if (numext::abs(numext::real(W.coeff(imax, j + 1))) >= alpha * rowmax) {
735 W.col(j).segment(jc, n - jc) = W.col(j + 1).segment(jc, n - jc);
743 if (kstep == 2 && j + 1 >= nb)
break;
745 const Index kk = jc + kstep - 1;
747 selfadjoint_swap_lower(mat, kk, kp);
748 const Index nwc = j + kstep;
749 W.row(kk).head(nwc).swap(W.row(kp).head(nwc));
753 transpositions.coeffRef(jc) = StorageIndex(kp);
754 subdiag.coeffRef(jc) = Scalar(0);
755 const RealScalar dval = numext::real(W.coeff(jc, j));
756 mat.coeffRef(jc, jc) = Scalar(dval);
757 const Index rs = n - jc - 1;
759 if (!numext::is_exactly_zero(dval)) {
760 mat.col(jc).tail(rs) = W.col(j).segment(jc + 1, rs) / dval;
765 mat.col(jc).tail(rs).setZero();
766 if (info == 0) info = jc + 1;
771 transpositions.coeffRef(jc) = StorageIndex(jc);
772 transpositions.coeffRef(jc + 1) = StorageIndex(kp);
773 const RealScalar d11 = numext::real(W.coeff(jc, j));
774 const Scalar d21 = W.coeff(jc + 1, j);
775 const RealScalar d22 = numext::real(W.coeff(jc + 1, j + 1));
776 mat.coeffRef(jc, jc) = Scalar(d11);
777 mat.coeffRef(jc + 1, jc + 1) = Scalar(d22);
782 const Scalar cjd = numext::conj(d21);
783 const Scalar ak = numext::divide(d22, d21);
784 const Scalar akm1 = numext::divide(d11, cjd);
785 const RealScalar denom = numext::real(ak * akm1) - RealScalar(1);
786 if (info == 0 && !(denom < RealScalar(0) && denom > RealScalar(-2))) info = jc + 1;
787 const Index rs = n - jc - 2;
792 const RealScalar t = RealScalar(1) / denom;
793 auto w0 = W.col(j).segment(jc + 2, rs);
794 auto w1 = W.col(j + 1).segment(jc + 2, rs);
795 mat.col(jc).tail(rs) = t * ((ak * w0 - w1) / cjd);
796 mat.col(jc + 1).tail(rs) = t * ((akm1 * w1 - w0) / d21);
798 subdiag.coeffRef(jc) = d21;
799 subdiag.coeffRef(jc + 1) = Scalar(0);
800 mat.coeffRef(jc + 1, jc) = Scalar(0);
808 template <
bool LastOnTies =
false,
typename MatrixType,
typename TranspositionType,
typename SubDiagType,
809 typename WorkspaceType>
810 static Index blocked(MatrixType& mat, TranspositionType& transpositions, SubDiagType& subdiag,
811 WorkspaceType& workspace) {
812 const Index n = mat.rows();
813 const Index nb = bunch_kaufman_blocksize<typename MatrixType::Scalar>();
814 if (nb < 2 || n <= nb)
return unblocked<LastOnTies>(mat, transpositions, subdiag, 0);
817 workspace.resize(n, nb + 1);
822 const Index kb = partial_factor<LastOnTies>(mat, k, nb, workspace, transpositions, subdiag, info);
823 const Index rs = n - k - kb;
826 mat.block(k + kb, k + kb, rs, rs).template triangularView<Lower>() -=
827 mat.block(k + kb, k, rs, kb) * workspace.block(k + kb, 0, rs, kb).adjoint();
830 info = (info == 0) ? unblocked<LastOnTies>(mat, transpositions, subdiag, k) : info;
835 const Index info2 = unblocked<LastOnTies>(mat, transpositions, subdiag, k);
836 if (info == 0) info = info2;
845struct bunch_kaufman<
Upper> {
846 template <
typename MatrixType,
typename TranspositionType,
typename SubDiagType>
847 static EIGEN_STRONG_INLINE Index unblocked(MatrixType& mat, TranspositionType& transpositions, SubDiagType& subdiag,
849 Transpose<MatrixType> matt(mat);
850 return bunch_kaufman<Lower>::unblocked(matt, transpositions, subdiag, k0);
853 template <
typename MatrixType,
typename TranspositionType,
typename SubDiagType,
typename WorkspaceType>
854 static EIGEN_STRONG_INLINE Index blocked(MatrixType& mat, TranspositionType& transpositions, SubDiagType& subdiag,
855 WorkspaceType& workspace) {
856 Transpose<MatrixType> matt(mat);
857 return bunch_kaufman<Lower>::blocked(matt, transpositions, subdiag, workspace);
861template <
typename MatrixType>
862struct BunchKaufman_Traits<MatrixType,
Lower> {
863 using MatrixL =
const TriangularView<const MatrixType, UnitLower>;
864 using MatrixU =
const TriangularView<const typename MatrixType::AdjointReturnType, UnitUpper>;
865 static inline MatrixL getL(
const MatrixType& m) {
return MatrixL(m); }
866 static inline MatrixU getU(
const MatrixType& m) {
return MatrixU(m.adjoint()); }
869template <
typename MatrixType>
870struct BunchKaufman_Traits<MatrixType,
Upper> {
871 using MatrixL =
const TriangularView<const typename MatrixType::AdjointReturnType, UnitLower>;
872 using MatrixU =
const TriangularView<const MatrixType, UnitUpper>;
873 static inline MatrixL getL(
const MatrixType& m) {
return MatrixL(m.adjoint()); }
874 static inline MatrixU getU(
const MatrixType& m) {
return MatrixU(m); }
879template <
typename MatrixType,
int UpLo_>
880template <
typename Derived>
882 const Index n = m_matrix.rows();
885 if (k + 1 < n && !numext::is_exactly_zero(m_subdiag.coeff(k))) {
886 const RealScalar d11 = numext::real(m_matrix.coeff(k, k));
887 const RealScalar d22 = numext::real(m_matrix.coeff(k + 1, k + 1));
888 const Scalar d21 = m_subdiag.coeff(k);
889 for (Index j = 0; j < x.cols(); ++j) {
890 const Scalar x0 = x.coeff(k, j);
891 const Scalar x1 = x.coeff(k + 1, j);
892 x.coeffRef(k, j) = d11 * x0 + numext::conj(d21) * x1;
893 x.coeffRef(k + 1, j) = d21 * x0 + d22 * x1;
897 x.row(k) *= numext::real(m_matrix.coeff(k, k));
903template <
typename MatrixType,
int UpLo_>
904template <
bool Conjugate,
typename Derived>
906 const Index n = m_matrix.rows();
909 const RealScalar tol = (std::numeric_limits<RealScalar>::min)();
912 if (k + 1 < n && !numext::is_exactly_zero(m_subdiag.coeff(k))) {
913 const RealScalar d11 = numext::real(m_matrix.coeff(k, k));
914 const RealScalar d22 = numext::real(m_matrix.coeff(k + 1, k + 1));
916 const Scalar d21 = Conjugate ? m_subdiag.coeff(k) : numext::conj(m_subdiag.coeff(k));
921 const Scalar cjd = numext::conj(d21);
922 const Scalar ak = numext::divide(d22, d21);
923 const Scalar akm1 = numext::divide(d11, cjd);
924 const RealScalar t = RealScalar(1) / (numext::real(ak * akm1) - RealScalar(1));
925 for (Index j = 0; j < x.cols(); ++j) {
926 const Scalar bk = numext::divide(x.coeff(k + 1, j), d21);
927 const Scalar bkm1 = numext::divide(x.coeff(k, j), cjd);
928 x.coeffRef(k, j) = t * (ak * bkm1 - bk);
929 x.coeffRef(k + 1, j) = t * (akm1 * bk - bkm1);
933 const RealScalar dk = numext::real(m_matrix.coeff(k, k));
934 if (numext::abs(dk) > tol)
948template <
typename MatrixType,
int UpLo_>
950 const RealScalar& d11,
const RealScalar& d22,
const RealScalar& d21) {
951 const RealScalar q = (d11 / d21) * (d22 / d21);
952 return (q > RealScalar(-1) && q < RealScalar(1)) ? q - RealScalar(1) : RealScalar(-1);
955template <
typename MatrixType,
int UpLo_>
956void BunchKaufman<MatrixType, UpLo_>::computeInertia() {
957 const Index n = m_matrix.rows();
958 m_n_pos = m_n_neg = m_n_zero = 0;
961 if (k + 1 < n && !numext::is_exactly_zero(m_subdiag.coeff(k))) {
962 const RealScalar d11 = numext::real(m_matrix.coeff(k, k));
963 const RealScalar d22 = numext::real(m_matrix.coeff(k + 1, k + 1));
964 const RealScalar d21 = numext::abs(m_subdiag.coeff(k));
966 if ((numext::isfinite)(d11) && (numext::isfinite)(d22) && (numext::isfinite)(d21)) {
972 const RealScalar dk = numext::real(m_matrix.coeff(k, k));
973 if (!(numext::isfinite)(dk)) {
975 }
else if (dk > RealScalar(0))
977 else if (dk < RealScalar(0))
988template <
typename MatrixType,
int UpLo_>
989template <
typename InputType>
991 EIGEN_INTERNAL_ASSERT_SQUARE(a);
992 m_matrix = a.derived();
993 return computeInPlace();
997template <
typename MatrixType,
int UpLo_>
999 EIGEN_INTERNAL_ASSERT_SQUARE(m_matrix);
1000 const Index size = m_matrix.rows();
1003 m_l1_norm = m_matrix.template selfadjointView<UpLo_>().l1Norm();
1005 m_transpositions.resize(size);
1006 m_subdiag.resize(size);
1007 m_isInitialized =
false;
1009 Index info = internal::bunch_kaufman<UpLo>::blocked(m_matrix, m_transpositions, m_subdiag, m_workspace);
1015 EIGEN_IF_CONSTEXPR (
int(UpLo) ==
int(
Upper) && NumTraits<Scalar>::IsComplex) {
1016 m_subdiag = m_subdiag.conjugate();
1022 if (m_n_pos + m_n_neg + m_n_zero < size) m_info =
NumericalIssue;
1024 m_isInitialized =
true;
1028#ifndef EIGEN_PARSED_BY_DOXYGEN
1029template <
typename MatrixType_,
int UpLo_>
1030template <
typename RhsType,
typename DstType>
1032 _solve_impl_transposed<true>(rhs, dst);
1035template <
typename MatrixType_,
int UpLo_>
1036template <
bool Conjugate,
typename RhsType,
typename DstType>
1039 dst = m_transpositions * rhs;
1040 matrixL().template conjugateIf<!Conjugate>().solveInPlace(dst);
1041 solveInPlaceD<Conjugate>(dst);
1042 matrixL().transpose().template conjugateIf<Conjugate>().solveInPlace(dst);
1043 dst = m_transpositions.transpose() * dst;
1053template <
typename MatrixType,
int UpLo_>
1054template <
typename Derived>
1056 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1057 EIGEN_INTERNAL_ASSERT_SAME_ROWS(m_matrix, bAndX);
1058 bAndX = this->solve(bAndX);
1062template <
typename MatrixType,
int UpLo_>
1063typename BunchKaufman<MatrixType, UpLo_>::DeterminantProduct BunchKaufman<MatrixType, UpLo_>::determinantD()
const {
1064 const Index n = m_matrix.rows();
1065 DeterminantProduct product;
1068 if (k + 1 < n && !numext::is_exactly_zero(m_subdiag.coeff(k))) {
1069 const RealScalar d11 = numext::real(m_matrix.coeff(k, k));
1070 const RealScalar d22 = numext::real(m_matrix.coeff(k + 1, k + 1));
1071 const RealScalar d21 = numext::abs(m_subdiag.coeff(k));
1073 product.multiply(d21);
1074 product.multiply(d21);
1075 product.multiply(scaledBlockDeterminant(d11, d22, d21));
1078 product.multiply(numext::real(m_matrix.coeff(k, k)));
1087template <
typename MatrixType,
int UpLo_>
1089 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1090 return Scalar(determinantD().value());
1093template <
typename MatrixType,
int UpLo_>
1095 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1096 return determinantD().abs();
1099template <
typename MatrixType,
int UpLo_>
1101 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1102 EIGEN_IF_CONSTEXPR (internal::has_scaled_product<RealScalar>::value)
return determinantD().logAbs();
1103 const Index n = m_matrix.rows();
1104 RealScalar result(0);
1107 if (k + 1 < n && !numext::is_exactly_zero(m_subdiag.coeff(k))) {
1109 const RealScalar d11 = numext::real(m_matrix.coeff(k, k));
1110 const RealScalar d22 = numext::real(m_matrix.coeff(k + 1, k + 1));
1111 const RealScalar d21 = numext::abs(m_subdiag.coeff(k));
1112 const RealScalar scaled = scaledBlockDeterminant(d11, d22, d21);
1113 result += RealScalar(2) * numext::log(d21) + numext::log(numext::abs(scaled));
1116 result += numext::log(numext::abs(numext::real(m_matrix.coeff(k, k))));
1123template <
typename MatrixType,
int UpLo_>
1125 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1126 if (m_n_zero > 0 || m_n_pos + m_n_neg + m_n_zero < rows())
return Scalar(0);
1127 return Scalar((m_n_neg % 2 == 0) ? 1 : -1);
1132template <
typename MatrixType,
int UpLo_>
1134 eigen_assert(m_isInitialized &&
"BunchKaufman is not initialized.");
1139 auto lower_triangle = res.template selfadjointView<Lower>();
1140 for (Index k = m_matrix.rows() - 1; k >= 0; --k) lower_triangle.applyTransposition(k, m_transpositions.coeff(k));
1141 res.template triangularView<StrictlyUpper>() = res.adjoint();
1150template <
typename MatrixType,
unsigned int UpLo>
1160template <
typename Derived>