Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
KroneckerSum.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// References:
11// [1] R. H. Bartels and G. W. Stewart, "Solution of the matrix equation
12// AX + XB = C", Communications of the ACM 15 (1972), 820-826. The Schur
13// form solve of the Sylvester equation B X + X A^T = mat(b) that
14// BartelsStewart generalizes to Kronecker sums of any number of factors.
15// [2] R. E. Lynch, J. R. Rice and D. H. Thomas, "Direct solution of partial
16// difference equations by tensor product methods", Numerische Mathematik 6
17// (1964), 185-199. The fast diagonalization method: with Hermitian factors
18// the Schur forms are diagonal and the solve is a division by the
19// eigenvalue sums.
20
21#ifndef EIGEN_STRUCTURED_KRONECKER_SUM_H
22#define EIGEN_STRUCTURED_KRONECKER_SUM_H
23
24// IWYU pragma: private
25#include "./InternalHeaderCheck.h"
26
27namespace Eigen {
28
29template <typename KroneckerSumType>
30class BartelsStewart;
31
32namespace internal {
33
34template <typename LhsMatrix, typename RhsMatrix>
35struct traits<KroneckerSum<LhsMatrix, RhsMatrix>> {
36 using Scalar = typename LhsMatrix::Scalar;
37 using StorageKind = Dense;
38 using XprKind = MatrixXpr;
39 using StorageIndex = int;
40 static constexpr int RowsAtCompileTime =
41 size_at_compile_time(traits<LhsMatrix>::RowsAtCompileTime, traits<RhsMatrix>::RowsAtCompileTime);
42 static constexpr int ColsAtCompileTime = RowsAtCompileTime;
43 static constexpr int MaxRowsAtCompileTime = RowsAtCompileTime;
44 static constexpr int MaxColsAtCompileTime = RowsAtCompileTime;
45 // No NestByRefBit, for the reason given at traits<KroneckerOperator>.
46 static constexpr unsigned int Flags = 0;
47};
48
49template <typename LhsMatrix, typename RhsMatrix>
50struct evaluator_traits<KroneckerSum<LhsMatrix, RhsMatrix>> {
51 using Kind = IndexBased;
52 using Shape = StructuredShape;
53};
54
55template <typename KroneckerSumType>
56struct traits<BartelsStewart<KroneckerSumType>> : traits<Matrix<typename KroneckerSumType::Scalar, Dynamic, Dynamic>> {
57 using XprKind = MatrixXpr;
58 using StorageKind = SolverStorage;
59 using StorageIndex = int;
60 using BaseTraits = traits<Matrix<typename KroneckerSumType::Scalar, Dynamic, Dynamic>>;
61 static constexpr unsigned int Flags = BaseTraits::Flags & RowMajorBit;
62 static constexpr int CoeffReadCost = Dynamic;
63};
64
70template <typename LhsMatrix, typename RhsMatrix>
71struct kron_factor_ops<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor> {
72 using Factor = KroneckerSum<LhsMatrix, RhsMatrix>;
73 using Scalar = typename Factor::Scalar;
74 using LhsOps = kron_factor_ops<LhsMatrix>;
75 using RhsOps = kron_factor_ops<RhsMatrix>;
76 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
77 using SparseFactor = SparseMatrix<Scalar>;
78 using TransposedFactor = KroneckerSum<typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor>;
79 using InverseFactor = DenseMatrix;
80 static constexpr bool StoresAllEntries = false;
81
82 static void prepare(Factor&) {}
83 static bool coeffIfStored(const Factor& f, Index row, Index col, Scalar& value) {
84 const Index n2 = f.rhs().rows();
85 Scalar a(0), b(0);
86 const bool storedA = row % n2 == col % n2 && LhsOps::coeffIfStored(f.lhs(), row / n2, col / n2, a);
87 const bool storedB = row / n2 == col / n2 && RhsOps::coeffIfStored(f.rhs(), row % n2, col % n2, b);
88 if (!storedA && !storedB) return false;
89 value = a + b;
90 return true;
91 }
92 template <typename Visitor>
93 static void forEachNonZero(const Factor& f, Visitor&& visit) {
94 kron_factor_ops<SparseFactor>::forEachNonZero(kron_factor_visitable<Factor>::get(f), visit);
95 }
96 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool rowMajor) {
97 return kron_factor_ops<SparseFactor>::innerNonZeros(kron_factor_visitable<Factor>::get(f), rowMajor);
98 }
99 static TransposedFactor transposed(const Factor& f) { return f.transpose(); }
100 static Factor conjugated(const Factor& f) { return f.conjugate(); }
101 static TransposedFactor adjointed(const Factor& f) { return f.adjoint(); }
102 static InverseFactor inversed(const Factor& f) { return f.solve(DenseMatrix::Identity(f.rows(), f.cols())); }
103 static DenseMatrix denseFactor(const Factor& f) { return DenseMatrix(f); }
104 static DenseMatrix blockOperand(const Factor& f) { return denseFactor(f); }
105 static bool isSquareIdentity(const Factor&) { return false; }
106 template <typename Dst, typename Alpha, typename Xpr>
107 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
108 f.addProduct(dst, X, alpha);
109 }
110 // With X_j = X(:, j n2 : (j+1) n2 - 1), j < n1, the p x n2 slices of X,
111 // X (L (+) R)^T = X (L (x) I)^T + X (I (x) R)^T = X_{[p n2 x n1]} L^T + [X_j R^T]_j.
112 template <typename Dst, typename Alpha, typename Xpr, typename Work>
113 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work& work) {
114 const Index p = X.rows(), n1 = f.lhs().rows(), n2 = f.rhs().rows();
115 auto dstL = dst.reshaped(p * n2, n1);
116 LhsOps::addRightProduct(dstL, alpha, X.reshaped(p * n2, n1), f.lhs(), work);
117 for (Index j = 0; j < n1; ++j) {
118 auto dstj = dst.middleCols(j * n2, n2);
119 RhsOps::addRightProduct(dstj, alpha, X.middleCols(j * n2, n2), f.rhs(), work);
120 }
121 }
122 // det = prod_{i,j} (lambda_i + mu_j) would cost only the factor Schur forms,
123 // but every delta lambda_i recurs in n_R factors of the product, and a shift
124 // split across L and R makes |lambda_i + mu_j| << |lambda_i| + |mu_j|. Against
125 // a 256-bit reference that product lost 1 to 6 digits to the LU of the
126 // materialized sum.
127 static Scalar balancedDet(const Factor& f, Index& exponent) {
128 return kron_factor_ops<DenseMatrix>::balancedDet(denseFactor(f), exponent);
129 }
130};
131
132template <typename LhsMatrix, typename RhsMatrix>
133struct kron_factor_visitable<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor> {
134 using Factor = KroneckerSum<LhsMatrix, RhsMatrix>;
135 using type = SparseMatrix<typename Factor::Scalar>;
136 static type get(const Factor& f) {
137 type S;
138 S = f;
139 return S;
140 }
141};
142
147template <typename LhsMatrix, typename RhsMatrix>
148struct kron_factor_spectrum<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor>
149 : kron_factor_spectrum<KroneckerSum<LhsMatrix, RhsMatrix>, kKronDenseFactor> {
150 using Factor = KroneckerSum<LhsMatrix, RhsMatrix>;
151 using Eigenvectors = KroneckerOperator<typename kron_factor_spectrum<LhsMatrix>::Eigenvectors,
152 typename kron_factor_spectrum<RhsMatrix>::Eigenvectors>;
153
154 static typename Factor::ComplexVector eigenvalues(const Factor& f) { return f.eigenvalues(); }
155 static Eigenvectors eigenvectors(const Factor& f) { return f.eigenvectors(); }
156};
157
158template <typename LhsMatrix, typename RhsMatrix>
159class kron_factor_solver<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor> {
160 public:
161 using Factor = KroneckerSum<LhsMatrix, RhsMatrix>;
162 using Scalar = typename Factor::Scalar;
163 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
164
165 explicit kron_factor_solver(const Factor& f) : m_solver(f) {}
166 template <typename Xpr>
167 DenseMatrix solveLeft(const Xpr& M) const {
168 return m_solver.solve(M);
169 }
170 // X = M S^{-T} solves S X^T = M^T, written through a transposed view of X.
171 template <typename Xpr>
172 DenseMatrix solveTransposedRight(const Xpr& M) const {
173 DenseMatrix X(M.rows(), M.cols());
174 X.transpose() = m_solver.solve(M.transpose());
175 return X;
176 }
177
178 private:
179 BartelsStewart<Factor> m_solver;
180};
181
182} // namespace internal
183
242template <typename LhsMatrix, typename RhsMatrix>
243class KroneckerSum : public EigenBase<KroneckerSum<LhsMatrix, RhsMatrix>> {
244 public:
245 using Scalar = typename LhsMatrix::Scalar;
246 using RealScalar = typename NumTraits<Scalar>::Real;
247 using StorageIndex = int;
248
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)");
258
259 private:
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>;
264
265 public:
266 using ComplexScalar = std::complex<RealScalar>;
268 using ComplexVector = Matrix<ComplexScalar, Dynamic, 1>;
269
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;
278 // Deliberately no IsVectorAtCompileTime, for the reason given in KroneckerOperator.
279
282 template <typename LhsDerived, typename RhsDerived>
283 KroneckerSum(const EigenBase<LhsDerived>& a, const EigenBase<RhsDerived>& b) : m_A(a.derived()), m_B(b.derived()) {
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);
288 }
289
290 EIGEN_DEVICE_FUNC Index rows() const { return m_A.rows() * m_B.rows(); }
291 EIGEN_DEVICE_FUNC Index cols() const { return rows(); }
292
295 template <int Options = ColMajor>
299
301 const LhsMatrix& lhs() const { return m_A; }
303 const RhsMatrix& rhs() const { return m_B; }
304
308 Scalar coeff(Index row, Index col) const {
309 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
310 Scalar value;
311 return internal::kron_factor_ops<KroneckerSum>::coeffIfStored(*this, row, col, value) ? value : Scalar(0);
312 }
313
316 return {LhsOps::transposed(m_A), RhsOps::transposed(m_B)};
317 }
318
320 KroneckerSum conjugate() const { return {LhsOps::conjugated(m_A), RhsOps::conjugated(m_B)}; }
321
324 return {LhsOps::adjointed(m_A), RhsOps::adjointed(m_B)};
325 }
326
330 template <typename Rhs>
332 const BartelsStewart<KroneckerSum> solver(*this);
333 return solver.solve(b);
334 }
335
350 ComplexVector eigenvalues() const {
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();
353 }
354
361 return {LhsSpectrum::eigenvectors(m_A), RhsSpectrum::eigenvectors(m_B)};
362 }
363
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");
372 return Product<KroneckerSum, Rhs>(*this, x.derived());
373 }
374
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);
389 if (c == 1) {
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);
394 continue;
395 }
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);
402 }
403 }
404
408 template <typename Dest>
409 void evalTo(Dest& dst) const {
410 evalToImpl(dst, IsSparseDestination<Dest>());
411 }
412
414 template <typename Dest>
415 void addTo(Dest& dst) const {
416 addToImpl(dst, Scalar(1), IsSparseDestination<Dest>());
417 }
418
420 template <typename Dest>
421 void subTo(Dest& dst) const {
422 addToImpl(dst, Scalar(-1), IsSparseDestination<Dest>());
423 }
424
425 private:
426 template <typename Dest>
427 using IsSparseDestination = std::is_same<typename internal::traits<Dest>::StorageKind, Sparse>;
428
429 template <typename Dest>
430 void evalToImpl(Dest& dst, std::false_type) const {
431 dst.setZero();
432 addToImpl(dst, Scalar(1), std::false_type());
433 }
434
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;
442 });
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;
445 }
446
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;
468 });
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; });
473 S = SA + SB;
474 }
475
476 template <typename Dest>
477 void addToImpl(Dest& dst, const Scalar& s, std::true_type) const {
478 typename Dest::PlainObject sum;
479 evalTo(sum);
480 if (s == Scalar(1))
481 dst += sum;
482 else
483 dst -= sum;
484 }
485
486 LhsMatrix m_A;
487 RhsMatrix m_B;
488};
489
493template <typename LhsDerived, typename RhsDerived>
495 typename internal::kron_factor_storage<RhsDerived>::type>
497 return {a.derived(), b.derived()};
498}
499
503template <typename D1, typename D2, typename D3, typename... Rest>
504auto makeKroneckerSum(const EigenBase<D1>& a, const EigenBase<D2>& b, const EigenBase<D3>& c, const Rest&... rest) {
505 return makeKroneckerSum(a, makeKroneckerSum(b, c, rest...));
506}
507
577template <typename KroneckerSumType>
578class BartelsStewart : public SolverBase<BartelsStewart<KroneckerSumType>> {
579 public:
580 using Base = SolverBase<BartelsStewart>;
581 friend class SolverBase<BartelsStewart>;
582 EIGEN_GENERIC_PUBLIC_INTERFACE(BartelsStewart)
583 EIGEN_STATIC_ASSERT_NON_INTEGER(RealScalar)
584 using MatrixType = KroneckerSumType;
585 using ComplexScalar = std::complex<RealScalar>;
588 using RealVector = Matrix<RealScalar, Dynamic, 1>;
589
591 BartelsStewart() = default;
592
594 explicit BartelsStewart(const KroneckerSumType& op) { compute(op); }
595
598 BartelsStewart& compute(const KroneckerSumType& op) {
599 std::vector<DenseMatrix> leaves;
600 collectLeaves(op, leaves);
601 const std::size_t d = leaves.size();
602 m_sizes.resize(d);
603 m_inner.resize(d);
604 m_unitary.clear();
605 m_triangular.clear();
606 m_triangularAdjoint.clear();
607 m_basis.clear();
608 m_quasiTriangular.clear();
609 m_info = Success;
610 bool hermitian = true;
611 for (std::size_t k = 0; k < d; ++k) {
612 m_sizes[k] = leaves[k].rows();
613 if (!leaves[k].allFinite()) m_info = InvalidInput;
614 hermitian = hermitian && leaves[k] == leaves[k].adjoint();
615 }
616 if (hermitian)
617 m_path = Path::Diagonal;
618 else if (!NumTraits<Scalar>::IsComplex && d <= std::size_t(kMaxRealFactors))
619 m_path = Path::RealSchur;
620 else
621 m_path = Path::ComplexSchur;
622 m_size = 1;
623 for (std::size_t k = d; k-- > 0;) {
624 m_inner[k] = m_size;
625 m_size *= m_sizes[k];
626 }
627 m_isInitialized = true;
628 if (m_info != Success) return *this;
629 switch (m_path) {
630 case Path::Diagonal: {
631 m_spectrum = RealVector::Zero(1);
633 for (std::size_t k = 0; k < d; ++k) {
634 es.compute(leaves[k]);
635 if (es.info() != Success) m_info = NoConvergence;
636 m_basis.push_back(es.eigenvectors());
637 // Kronecker order: the new factor's index runs fastest.
638 const RealVector& lambda = es.eigenvalues();
639 const RealVector previous = m_spectrum;
640 m_spectrum =
641 (lambda.replicate(fix<1>, previous.size()) + previous.transpose().replicate(lambda.size(), fix<1>))
642 .reshaped();
643 }
644 break;
645 }
646 case Path::RealSchur:
647 computeRealSchur(leaves, internal::bool_constant<!NumTraits<Scalar>::IsComplex>());
648 break;
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>());
653 if (schur.info() != Success) m_info = NoConvergence;
654 m_unitary.push_back(schur.matrixU());
655 m_triangular.push_back(schur.matrixT());
656 m_triangularAdjoint.emplace_back(m_triangular.back().adjoint());
657 }
658 break;
659 }
660 }
661 return *this;
662 }
663
664 Index rows() const noexcept { return m_size; }
665 Index cols() const noexcept { return m_size; }
666
670 eigen_assert(m_isInitialized && "BartelsStewart is not initialized.");
671 return m_info;
672 }
673
676 bool isHermitian() const {
677 eigen_assert(m_isInitialized && "BartelsStewart is not initialized.");
678 return m_path == Path::Diagonal;
679 }
680
681#ifdef EIGEN_PARSED_BY_DOXYGEN
685 template <typename Rhs>
687#endif
688
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, /*adjoint=*/false);
693 }
694
695 // M^T = conj(M^H): M^{-T} b = conj(M^{-H} conj(b)).
696 template <bool Conjugate, typename RhsType, typename DstType>
697 void _solve_impl_transposed(const RhsType& rhs, DstType& dst) const {
698 constexpr bool ConjugateRhs = !Conjugate && NumTraits<Scalar>::IsComplex;
699 solveImpl(rhs.template conjugateIf<ConjugateRhs>(), dst, /*adjoint=*/true);
700 if (ConjugateRhs) dst = dst.conjugate();
701 }
702#endif
703
704 private:
707 template <typename RhsType, typename DstType>
708 void solveImpl(const RhsType& rhs, DstType& dst, bool adjoint) const {
709 if (m_info != Success) {
710 // No usable decompositions; the nested solves never see info().
711 dst.setConstant(Scalar(NumTraits<RealScalar>::quiet_NaN()));
712 return;
713 }
714 switch (m_path) {
715 case Path::Diagonal: {
716 DenseMatrix W = rhs;
717 applyBasis(W, m_basis, /*adjoint=*/true);
718 W.array().colwise() /= m_spectrum.array();
719 applyBasis(W, m_basis, /*adjoint=*/false);
720 dst = W;
721 break;
722 }
723 case Path::RealSchur: {
724 DenseMatrix W = rhs;
725 solveRealSchur(W, adjoint, internal::bool_constant<!NumTraits<Scalar>::IsComplex>());
726 dst = W;
727 break;
728 }
729 case Path::ComplexSchur: {
730 ComplexMatrix W = rhs.template cast<ComplexScalar>();
731 applyBasis(W, m_unitary, /*adjoint=*/true);
732 for (Index j = 0; j < W.cols(); ++j) {
733 if (adjoint)
734 adjointTriangularSolve(0, ComplexScalar(0), W.col(j).data());
735 else
736 triangularSolve(0, ComplexScalar(0), W.col(j).data());
737 }
738 applyBasis(W, m_unitary, /*adjoint=*/false);
739 dst = internal::structured_scalar_part_impl<Scalar>::run(W);
740 break;
741 }
742 }
743 }
744
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>());
748 }
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);
753 }
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)));
757 }
758
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>;
767 WorkMatrix T;
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);
770 if (s == 1) {
771 Map<WorkMatrix> U(W.data(), n, blocks);
772 if (adjoint)
773 T.noalias() = Q[k].adjoint() * U;
774 else
775 T.noalias() = Q[k] * U;
776 U = T;
777 continue;
778 }
779 for (Index b = 0; b < blocks; ++b) {
780 Map<WorkMatrix> V(W.data() + b * n * s, s, n);
781 if (adjoint)
782 T.noalias() = V * Q[k].conjugate();
783 else
784 T.noalias() = V * Q[k].transpose();
785 V = T;
786 }
787 }
788 }
789
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()) {
798 // Last factor, s = 1: back substitution on the shifted T_d, by rows.
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));
803 }
804 return;
805 }
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());
811 }
812 }
813
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()) {
821 // Last factor, s = 1: forward substitution on the shifted L_d, by rows.
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));
824 return;
825 }
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());
830 }
831 }
832
833 // The real path's coupled systems are at most 2^d wide, see the class documentation.
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>;
839
840 void computeRealSchur(const std::vector<DenseMatrix>& leaves, std::true_type) {
841 RealSchur<DenseMatrix> schur;
842 for (const DenseMatrix& leaf : leaves) {
843 schur.compute(leaf);
844 if (schur.info() != Success) m_info = NoConvergence;
845 m_basis.push_back(schur.matrixU());
846 m_quasiTriangular.push_back(schur.matrixT());
847 }
848 }
849 void computeRealSchur(const std::vector<DenseMatrix>&, std::false_type) {}
850
851 void solveRealSchur(DenseMatrix& W, bool adjoint, std::true_type) const {
852 applyBasis(W, m_basis, /*adjoint=*/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, /*adjoint=*/false);
858 }
859 void solveRealSchur(DenseMatrix&, bool, std::false_type) const {}
860
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;) {
873 // Block I = [i, i + p): the next one up from the bottom, or down from the top when adjoint.
874 Index i, p;
875 if (adjoint) {
876 i = done;
877 p = i + 1 < n && T(i + 1, i) != RealScalar(0) ? 2 : 1;
878 } else {
879 const Index end = n - done;
880 p = end > 1 && T(end - 1, end - 2) != RealScalar(0) ? 2 : 1;
881 i = end - p;
882 }
883 const Index tail = n - i - p;
884 // T(I,I), T(J,I) for J < I, and T(I,J) for J > I.
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);
889 if (last) {
890 // s = 1: row i of X belongs to index i of the last factor.
891 auto XI = X.middleRows(i, p);
892 if (adjoint) {
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));
896 }
897 solveCoupled(coupled, XI);
898 } else {
899 for (Index t = 0; t < m; ++t) {
900 auto Xt = X.col(t).reshaped(s, n);
901 auto XtI = Xt.middleCols(i, p);
902 if (adjoint) {
903 if (i > 0) XtI.noalias() -= Xt.leftCols(i) * colHead;
904 } else if (tail > 0) {
905 XtI.noalias() -= Xt.rightCols(tail) * rowTail.transpose();
906 }
907 }
908 if (m == 1) {
909 quasiTriangularSolve(k + 1, coupled, Map<RealMatrix>(X.col(0).data() + i * s, s, p), work, adjoint);
910 } else {
911 // Columns (t, a) of Z, a fastest: column a of block I for coupling index t.
912 RealMatrix& Z = work[k];
913 Z.resize(s, m * p);
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);
917 }
918 }
919 done += p;
920 }
921 }
922
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;
932 }
933 return R;
934 }
935
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);
941 return;
942 }
943 CouplingVector z = XI.reshaped();
944 z = coupled.partialPivLu().solve(z);
945 XI.reshaped() = z;
946 }
947
948 std::vector<Index> m_sizes, m_inner;
949 Index m_size = 0;
950 std::vector<DenseMatrix> m_basis;
951 RealVector m_spectrum;
952 // Row-major: the back substitution reads T_k by rows, and the forward
953 // substitution of the adjoint solve reads T_k^H, kept as its own copy, the
954 // same way.
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;
964};
965
966namespace internal {
967
968template <typename LhsMatrix, typename RhsMatrix, typename Rhs, int ProductTag>
969struct generic_product_impl<KroneckerSum<LhsMatrix, RhsMatrix>, Rhs, StructuredShape, DenseShape, ProductTag>
970 : structured_product_impl<KroneckerSum<LhsMatrix, RhsMatrix>, Rhs> {};
971
972} // namespace internal
973
974#if EIGEN_COMP_CXXVER < 17
975template <typename LhsMatrix, typename RhsMatrix>
976constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::RowsAtCompileTime;
977template <typename LhsMatrix, typename RhsMatrix>
978constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::ColsAtCompileTime;
979template <typename LhsMatrix, typename RhsMatrix>
980constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::MaxRowsAtCompileTime;
981template <typename LhsMatrix, typename RhsMatrix>
982constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::MaxColsAtCompileTime;
983template <typename LhsMatrix, typename RhsMatrix>
984constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::SizeAtCompileTime;
985template <typename LhsMatrix, typename RhsMatrix>
986constexpr int KroneckerSum<LhsMatrix, RhsMatrix>::MaxSizeAtCompileTime;
987template <typename LhsMatrix, typename RhsMatrix>
988constexpr bool KroneckerSum<LhsMatrix, RhsMatrix>::IsRowMajor;
989#endif
990
991} // namespace Eigen
992
993#endif // EIGEN_STRUCTURED_KRONECKER_SUM_H
Direct solver for Kronecker-sum systems .
Definition KroneckerSum.h:578
bool isHermitian() const
Definition KroneckerSum.h:676
ComputationInfo info() const
Definition KroneckerSum.h:669
BartelsStewart(const KroneckerSumType &op)
Definition KroneckerSum.h:594
BartelsStewart & compute(const KroneckerSumType &op)
Definition KroneckerSum.h:598
const Solve< BartelsStewart, Rhs > solve(const MatrixBase< Rhs > &b) const
ComputationInfo info() const
const MatrixTType & matrixT() const
ComplexSchur & compute(const EigenBase< InputType > &matrix, bool computeU=true)
const ComplexMatrixType & matrixU() const
The Kronecker product as an implicit operator that is never materialized.
Definition KroneckerOperator.h:916
A KroneckerOperator or KroneckerSum as a lazy sparse expression.
Definition KroneckerSparseView.h:342
The Kronecker sum of two square matrices as an implicit operator that is never materialized.
Definition KroneckerSum.h:243
KroneckerSum conjugate() const
Definition KroneckerSum.h:320
KroneckerSum< typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor > adjoint() const
Definition KroneckerSum.h:323
KroneckerSum(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerSum.h:283
const RhsMatrix & rhs() const
Definition KroneckerSum.h:303
Matrix< Scalar, ColsAtCompileTime, Rhs::ColsAtCompileTime > solve(const MatrixBase< Rhs > &b) const
Definition KroneckerSum.h:331
KroneckerSum< typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor > transpose() const
Definition KroneckerSum.h:315
Scalar coeff(Index row, Index col) const
Definition KroneckerSum.h:308
KroneckerSparseView< KroneckerSum, Options > sparseView() const
Definition KroneckerSum.h:296
ComplexVector eigenvalues() const
Definition KroneckerSum.h:350
const LhsMatrix & lhs() const
Definition KroneckerSum.h:301
KroneckerOperator< typename LhsSpectrum::Eigenvectors, typename RhsSpectrum::Eigenvectors > eigenvectors() const
Definition KroneckerSum.h:360
Product< KroneckerSum, Rhs > operator*(const MatrixBase< Rhs > &x) const
Definition KroneckerSum.h:367
SelfAdjointEigenSolver & compute(const EigenBase< InputType > &matrix, int options=ComputeEigenvectors)
ComputationInfo info() const
const RealVectorType & eigenvalues() const
const EigenvectorsType & eigenvectors() const
static const auto fix()
KroneckerSum< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > makeKroneckerSum(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerSum.h:496
ComputationInfo
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.
constexpr Derived & derived()
Eigen::Index Index