245 using Scalar =
typename LhsMatrix::Scalar;
247 using StorageIndex = int;
249 static_assert(std::is_same<Scalar, typename RhsMatrix::Scalar>::value,
250 "KroneckerSum requires both factors to have the same scalar type");
251 static_assert((internal::kron_factor_is_dense_matrix<LhsMatrix>::value ||
252 internal::kron_factor_kind<LhsMatrix>() != internal::kKronDenseFactor) &&
253 (internal::kron_factor_is_dense_matrix<RhsMatrix>::value ||
254 internal::kron_factor_kind<RhsMatrix>() != internal::kKronDenseFactor),
255 "KroneckerSum factors must be plain Matrix, DiagonalMatrix or SparseMatrix types, identity factors "
256 "(makeKroneckerSum stores an Identity() expression as one), KroneckerOperators or KroneckerSums "
257 "(owning their storage)");
260 using LhsOps = internal::kron_factor_ops<LhsMatrix>;
261 using RhsOps = internal::kron_factor_ops<RhsMatrix>;
262 using LhsSpectrum = internal::kron_factor_spectrum<LhsMatrix>;
263 using RhsSpectrum = internal::kron_factor_spectrum<RhsMatrix>;
266 using ComplexScalar = std::complex<RealScalar>;
270 static constexpr int RowsAtCompileTime =
271 internal::size_at_compile_time(LhsMatrix::RowsAtCompileTime, RhsMatrix::RowsAtCompileTime);
272 static constexpr int ColsAtCompileTime = RowsAtCompileTime;
273 static constexpr int MaxRowsAtCompileTime = RowsAtCompileTime;
274 static constexpr int MaxColsAtCompileTime = RowsAtCompileTime;
275 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(RowsAtCompileTime, ColsAtCompileTime);
276 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
277 static constexpr bool IsRowMajor =
false;
282 template <
typename LhsDerived,
typename RhsDerived>
284 eigen_assert(m_A.size() > 0 && m_B.size() > 0 &&
"KroneckerSum factors must be non-empty");
285 eigen_assert(m_A.rows() == m_A.cols() && m_B.rows() == m_B.cols() &&
"KroneckerSum factors must be square");
286 LhsOps::prepare(m_A);
287 RhsOps::prepare(m_B);
290 EIGEN_DEVICE_FUNC Index rows()
const {
return m_A.rows() * m_B.rows(); }
291 EIGEN_DEVICE_FUNC Index cols()
const {
return rows(); }
295 template <
int Options = ColMajor>
301 const LhsMatrix&
lhs()
const {
return m_A; }
303 const RhsMatrix&
rhs()
const {
return m_B; }
309 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
311 return internal::kron_factor_ops<KroneckerSum>::coeffIfStored(*
this, row, col, value) ? value : Scalar(0);
316 return {LhsOps::transposed(m_A), RhsOps::transposed(m_B)};
324 return {LhsOps::adjointed(m_A), RhsOps::adjointed(m_B)};
330 template <
typename Rhs>
333 return solver.
solve(b);
351 const ComplexVector lambda = LhsSpectrum::eigenvalues(m_A), mu = RhsSpectrum::eigenvalues(m_B);
352 return (mu.replicate(
fix<1>, lambda.size()) + lambda.transpose().replicate(mu.size(),
fix<1>)).reshaped();
361 return {LhsSpectrum::eigenvectors(m_A), RhsSpectrum::eigenvectors(m_B)};
366 template <
typename Rhs>
368 EIGEN_STATIC_ASSERT(ColsAtCompileTime == Dynamic || Rhs::RowsAtCompileTime == Dynamic ||
369 int(ColsAtCompileTime) ==
int(Rhs::RowsAtCompileTime),
370 INVALID_MATRIX_PRODUCT)
371 eigen_assert(x.rows() == cols() &&
"invalid product: dimensions do not match");
379 template <
typename Dest,
typename Rhs,
typename ProductScalar>
380 void addProduct(Dest& dst,
const Rhs&
rhs,
const ProductScalar& alpha)
const {
382 const Index n1 = m_A.rows(), n2 = m_B.rows(), r =
rhs.cols();
383 eigen_assert(
rhs.rows() == n1 * n2 &&
"invalid product: dimensions do not match");
384 typename internal::nested_eval<Rhs, 1>::type actualRhs(
rhs);
385 ProductMatrix X, Y, work;
386 const Index chunk = internal::kron_rhs_chunk<ProductScalar>(2 * n1 * n2);
387 for (Index k0 = 0; k0 < r; k0 += chunk) {
388 const Index c = numext::mini(chunk, r - k0);
390 const auto Xk = actualRhs.col(k0).reshaped(n2, n1);
391 auto Yk = dst.col(k0).reshaped(n2, n1);
392 RhsOps::addLeftProduct(Yk, alpha, m_B, Xk);
393 LhsOps::addRightProduct(Yk, alpha, Xk, m_A, work);
396 internal::kron_stack_columns(X, actualRhs.middleCols(k0, c), n2, n1);
397 Y.setZero(n2 * c, n1);
398 auto Yflat = Y.reshaped(n2, c * n1);
399 RhsOps::addLeftProduct(Yflat, ProductScalar(1), m_B, X.reshaped(n2, c * n1));
400 LhsOps::addRightProduct(Y, ProductScalar(1), X, m_A, work);
401 for (Index k = 0; k < c; ++k) dst.col(k0 + k).reshaped(n2, n1) += alpha * Y.middleRows(k * n2, n2);
408 template <
typename Dest>
409 void evalTo(Dest& dst)
const {
410 evalToImpl(dst, IsSparseDestination<Dest>());
414 template <
typename Dest>
415 void addTo(Dest& dst)
const {
416 addToImpl(dst, Scalar(1), IsSparseDestination<Dest>());
420 template <
typename Dest>
421 void subTo(Dest& dst)
const {
422 addToImpl(dst, Scalar(-1), IsSparseDestination<Dest>());
426 template <
typename Dest>
427 using IsSparseDestination = std::is_same<typename internal::traits<Dest>::StorageKind, Sparse>;
429 template <
typename Dest>
430 void evalToImpl(Dest& dst, std::false_type)
const {
432 addToImpl(dst, Scalar(1), std::false_type());
437 template <
typename Dest>
438 void addToImpl(Dest& dst,
const Scalar& s, std::false_type)
const {
439 const Index n1 = m_A.rows(), n2 = m_B.rows();
440 LhsOps::forEachNonZero(m_A, [&dst, &s, n2](
Index i,
Index j,
const Scalar& a) {
441 dst.block(i * n2, j * n2, n2, n2).diagonal().array() += s * a;
443 const auto& B = RhsOps::blockOperand(m_B);
444 for (
Index k = 0; k < n1; ++k) dst.block(k * n2, k * n2, n2, n2) += s * B;
452 template <
typename Dest>
453 void evalToImpl(Dest& S, std::true_type)
const {
454 using IndexVector = Matrix<Index, Dynamic, 1>;
455 using LhsVisitable = internal::kron_factor_visitable<LhsMatrix>;
456 using RhsVisitable = internal::kron_factor_visitable<RhsMatrix>;
457 using VisitedLhsOps = internal::kron_factor_ops<typename LhsVisitable::type>;
458 using VisitedRhsOps = internal::kron_factor_ops<typename RhsVisitable::type>;
459 const Index n1 = m_A.rows(), n2 = m_B.rows();
460 const auto& A = LhsVisitable::get(m_A);
461 const auto& B = RhsVisitable::get(m_B);
462 const IndexVector nnzA = VisitedLhsOps::innerNonZeros(A, Dest::IsRowMajor);
463 const IndexVector nnzB = VisitedRhsOps::innerNonZeros(B, Dest::IsRowMajor);
464 Dest SA(rows(), cols()), SB(rows(), cols());
465 SA.reserve(IndexVector(nnzA.transpose().replicate(n2,
fix<1>).reshaped()));
466 VisitedLhsOps::forEachNonZero(A, [&SA, n2](
Index i,
Index j,
const Scalar& a) {
467 for (
Index k = 0; k < n2; ++k) SA.insert(i * n2 + k, j * n2 + k) = a;
469 SB.reserve(IndexVector(nnzB.replicate(n1,
fix<1>)));
470 for (
Index k = 0; k < n1; ++k)
471 VisitedRhsOps::forEachNonZero(
472 B, [&SB, n2, k](
Index i,
Index j,
const Scalar& b) { SB.insert(k * n2 + i, k * n2 + j) = b; });
476 template <
typename Dest>
477 void addToImpl(Dest& dst,
const Scalar& s, std::true_type)
const {
478 typename Dest::PlainObject sum;
583 EIGEN_STATIC_ASSERT_NON_INTEGER(RealScalar)
584 using MatrixType = KroneckerSumType;
585 using ComplexScalar = std::complex<RealScalar>;
599 std::vector<DenseMatrix> leaves;
600 collectLeaves(op, leaves);
601 const std::size_t d = leaves.size();
605 m_triangular.clear();
606 m_triangularAdjoint.clear();
608 m_quasiTriangular.clear();
610 bool hermitian =
true;
611 for (std::size_t k = 0; k < d; ++k) {
612 m_sizes[k] = leaves[k].rows();
614 hermitian = hermitian && leaves[k] == leaves[k].adjoint();
617 m_path = Path::Diagonal;
619 m_path = Path::RealSchur;
621 m_path = Path::ComplexSchur;
623 for (std::size_t k = d; k-- > 0;) {
625 m_size *= m_sizes[k];
627 m_isInitialized =
true;
628 if (m_info !=
Success)
return *
this;
630 case Path::Diagonal: {
631 m_spectrum = RealVector::Zero(1);
633 for (std::size_t k = 0; k < d; ++k) {
639 const RealVector previous = m_spectrum;
641 (lambda.replicate(
fix<1>, previous.size()) + previous.transpose().replicate(lambda.size(),
fix<1>))
646 case Path::RealSchur:
649 case Path::ComplexSchur: {
650 ComplexSchur<ComplexMatrix> schur;
651 for (std::size_t k = 0; k < d; ++k) {
652 schur.
compute(leaves[k].
template cast<ComplexScalar>());
654 m_unitary.push_back(schur.
matrixU());
655 m_triangular.push_back(schur.
matrixT());
656 m_triangularAdjoint.emplace_back(m_triangular.back().adjoint());
664 Index rows() const noexcept {
return m_size; }
665 Index cols() const noexcept {
return m_size; }
670 eigen_assert(m_isInitialized &&
"BartelsStewart is not initialized.");
677 eigen_assert(m_isInitialized &&
"BartelsStewart is not initialized.");
678 return m_path == Path::Diagonal;
681#ifdef EIGEN_PARSED_BY_DOXYGEN
685 template <
typename Rhs>
689#ifndef EIGEN_PARSED_BY_DOXYGEN
690 template <
typename RhsType,
typename DstType>
691 void _solve_impl(
const RhsType& rhs, DstType& dst)
const {
692 solveImpl(rhs, dst,
false);
696 template <
bool Conjugate,
typename RhsType,
typename DstType>
697 void _solve_impl_transposed(
const RhsType& rhs, DstType& dst)
const {
699 solveImpl(rhs.template conjugateIf<ConjugateRhs>(), dst,
true);
700 if (ConjugateRhs) dst = dst.conjugate();
707 template <
typename RhsType,
typename DstType>
708 void solveImpl(
const RhsType& rhs, DstType& dst,
bool adjoint)
const {
711 dst.setConstant(Scalar(NumTraits<RealScalar>::quiet_NaN()));
715 case Path::Diagonal: {
717 applyBasis(W, m_basis,
true);
718 W.array().colwise() /= m_spectrum.array();
719 applyBasis(W, m_basis,
false);
723 case Path::RealSchur: {
725 solveRealSchur(W,
adjoint, internal::bool_constant<!NumTraits<Scalar>::IsComplex>());
729 case Path::ComplexSchur: {
730 ComplexMatrix W = rhs.template cast<ComplexScalar>();
731 applyBasis(W, m_unitary,
true);
732 for (
Index j = 0; j < W.cols(); ++j) {
734 adjointTriangularSolve(0, ComplexScalar(0), W.col(j).data());
736 triangularSolve(0, ComplexScalar(0), W.col(j).data());
738 applyBasis(W, m_unitary,
false);
739 dst = internal::structured_scalar_part_impl<Scalar>::run(W);
745 template <
typename Factor>
746 static void collectLeaves(
const Factor& f, std::vector<DenseMatrix>& leaves) {
747 collectLeaves(f, leaves, internal::kron_factor_is_kronecker_sum<Factor>());
749 template <
typename Factor>
750 static void collectLeaves(
const Factor& f, std::vector<DenseMatrix>& leaves, std::true_type) {
751 collectLeaves(f.lhs(), leaves);
752 collectLeaves(f.rhs(), leaves);
754 template <
typename Factor>
755 static void collectLeaves(
const Factor& f, std::vector<DenseMatrix>& leaves, std::false_type) {
756 leaves.push_back(DenseMatrix(internal::kron_factor_ops<Factor>::denseFactor(f)));
764 template <
typename Work,
typename Basis>
765 void applyBasis(Work& W,
const std::vector<Basis>& Q,
bool adjoint)
const {
766 using WorkMatrix = Matrix<typename Work::Scalar, Dynamic, Dynamic, ColMajor>;
768 for (std::size_t k = 0; k < Q.size(); ++k) {
769 const Index n = m_sizes[k], s = m_inner[k], blocks = W.size() / (n * s);
771 Map<WorkMatrix> U(W.data(), n, blocks);
773 T.noalias() = Q[k].adjoint() * U;
775 T.noalias() = Q[k] * U;
779 for (
Index b = 0; b < blocks; ++b) {
780 Map<WorkMatrix> V(W.data() + b * n * s, s, n);
782 T.noalias() = V * Q[k].conjugate();
784 T.noalias() = V * Q[k].transpose();
794 void triangularSolve(std::size_t k,
const ComplexScalar& sigma, ComplexScalar* y)
const {
795 const Index n = m_sizes[k], s = m_inner[k];
796 const TriangularMatrix& T = m_triangular[k];
797 if (k + 1 == m_sizes.size()) {
799 Map<Matrix<ComplexScalar, 1, Dynamic>> Y(y, n);
800 for (
Index i = n - 1; i >= 0; --i) {
801 const Index tail = n - 1 - i;
802 Y(i) = (Y(i) - Y.tail(tail).cwiseProduct(T.row(i).tail(tail)).sum()) / (sigma + T(i, i));
806 Map<ComplexMatrix> Y(y, s, n);
807 for (
Index i = n - 1; i >= 0; --i) {
808 const Index tail = n - 1 - i;
809 if (tail > 0) Y.col(i).noalias() -= Y.rightCols(tail) * T.row(i).tail(tail).transpose();
810 triangularSolve(k + 1, sigma + T(i, i), Y.col(i).data());
817 void adjointTriangularSolve(std::size_t k,
const ComplexScalar& sigma, ComplexScalar* y)
const {
818 const Index n = m_sizes[k], s = m_inner[k];
819 const TriangularMatrix& L = m_triangularAdjoint[k];
820 if (k + 1 == m_sizes.size()) {
822 Map<Matrix<ComplexScalar, 1, Dynamic>> Y(y, n);
823 for (
Index i = 0; i < n; ++i) Y(i) = (Y(i) - Y.head(i).cwiseProduct(L.row(i).head(i)).sum()) / (sigma + L(i, i));
826 Map<ComplexMatrix> Y(y, s, n);
827 for (
Index i = 0; i < n; ++i) {
828 if (i > 0) Y.col(i).noalias() -= Y.leftCols(i) * L.row(i).head(i).transpose();
829 adjointTriangularSolve(k + 1, sigma + L(i, i), Y.col(i).data());
834 static constexpr int kMaxRealFactors = 4;
835 static constexpr int kMaxCoupling = 1 << kMaxRealFactors;
836 using CouplingMatrix = Matrix<RealScalar, Dynamic, Dynamic, ColMajor, kMaxCoupling, kMaxCoupling>;
837 using CouplingVector = Matrix<RealScalar, Dynamic, 1, ColMajor, kMaxCoupling, 1>;
838 using RealMatrix = Matrix<RealScalar, Dynamic, Dynamic, ColMajor>;
840 void computeRealSchur(
const std::vector<DenseMatrix>& leaves, std::true_type) {
841 RealSchur<DenseMatrix> schur;
842 for (
const DenseMatrix& leaf : leaves) {
845 m_basis.push_back(schur.matrixU());
846 m_quasiTriangular.push_back(schur.matrixT());
849 void computeRealSchur(
const std::vector<DenseMatrix>&, std::false_type) {}
851 void solveRealSchur(DenseMatrix& W,
bool adjoint, std::true_type)
const {
852 applyBasis(W, m_basis,
true);
853 std::vector<RealMatrix> work(m_sizes.size());
854 const CouplingMatrix outer = CouplingMatrix::Zero(1, 1);
855 for (
Index j = 0; j < W.cols(); ++j)
856 quasiTriangularSolve(0, outer, Map<RealMatrix>(W.col(j).data(), W.rows(), 1), work,
adjoint);
857 applyBasis(W, m_basis,
false);
859 void solveRealSchur(DenseMatrix&,
bool, std::false_type)
const {}
867 void quasiTriangularSolve(std::size_t k,
const CouplingMatrix& Sigma, Map<RealMatrix> X,
868 std::vector<RealMatrix>& work,
bool adjoint)
const {
869 const Index n = m_sizes[k], s = m_inner[k], m = Sigma.rows();
870 const QuasiTriangularMatrix& T = m_quasiTriangular[k];
871 const bool last = k + 1 == m_sizes.size();
872 for (
Index done = 0; done < n;) {
877 p = i + 1 < n && T(i + 1, i) != RealScalar(0) ? 2 : 1;
879 const Index end = n - done;
880 p = end > 1 && T(end - 1, end - 2) != RealScalar(0) ? 2 : 1;
883 const Index tail = n - i - p;
885 const auto TII = T.block(i, i, p, p);
886 const auto colHead = T.block(0, i, i, p);
887 const auto rowTail = T.block(i, i + p, p, tail);
888 const CouplingMatrix coupled =
adjoint ? kroneckerSum(Sigma, TII.transpose()) : kroneckerSum(Sigma, TII);
891 auto XI = X.middleRows(i, p);
893 if (i > 0) XI.noalias() -= colHead.transpose().lazyProduct(X.topRows(i));
894 }
else if (tail > 0) {
895 XI.noalias() -= rowTail.lazyProduct(X.bottomRows(tail));
897 solveCoupled(coupled, XI);
899 for (
Index t = 0; t < m; ++t) {
900 auto Xt = X.col(t).reshaped(s, n);
901 auto XtI = Xt.middleCols(i, p);
903 if (i > 0) XtI.noalias() -= Xt.leftCols(i) * colHead;
904 }
else if (tail > 0) {
905 XtI.noalias() -= Xt.rightCols(tail) * rowTail.transpose();
909 quasiTriangularSolve(k + 1, coupled, Map<RealMatrix>(X.col(0).data() + i * s, s, p), work,
adjoint);
912 RealMatrix& Z = work[k];
914 Z.reshaped(p * s, m) = X.middleRows(i * s, p * s);
915 quasiTriangularSolve(k + 1, coupled, Map<RealMatrix>(Z.data(), s, m * p), work,
adjoint);
916 X.middleRows(i * s, p * s) = Z.reshaped(p * s, m);
924 template <
typename Block>
925 static CouplingMatrix kroneckerSum(
const CouplingMatrix& Sigma,
const Block& S) {
926 const Index m = Sigma.rows(), p = S.rows();
927 eigen_internal_assert(m * p <= kMaxCoupling);
928 CouplingMatrix R = CouplingMatrix::Zero(m * p, m * p);
929 for (
Index t = 0; t < m; ++t) {
930 for (
Index u = 0; u < m; ++u) R.block(t * p, u * p, p, p).diagonal().setConstant(Sigma(t, u));
931 R.block(t * p, t * p, p, p) += S;
937 template <
typename Block>
938 static void solveCoupled(
const CouplingMatrix& coupled, Block& XI) {
939 if (coupled.rows() == 1) {
940 XI(0, 0) /= coupled(0, 0);
943 CouplingVector z = XI.reshaped();
944 z = coupled.partialPivLu().solve(z);
948 std::vector<Index> m_sizes, m_inner;
950 std::vector<DenseMatrix> m_basis;
951 RealVector m_spectrum;
955 using TriangularMatrix = Matrix<ComplexScalar, Dynamic, Dynamic, RowMajor>;
956 using QuasiTriangularMatrix = Matrix<RealScalar, Dynamic, Dynamic, RowMajor>;
957 std::vector<ComplexMatrix> m_unitary;
958 std::vector<TriangularMatrix> m_triangular, m_triangularAdjoint;
959 std::vector<QuasiTriangularMatrix> m_quasiTriangular;
960 enum class Path { Diagonal, RealSchur, ComplexSchur };
961 Path m_path = Path::Diagonal;
962 bool m_isInitialized =
false;