Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
KroneckerOperator.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] C. F. Van Loan, "The ubiquitous Kronecker product", Journal of
12// Computational and Applied Mathematics 123 (2000), 85-100. The vec
13// identity, with vec stacking columns, driving every product and solve
14// below -- stated there as
15// Y = C X B^T <=> vec(Y) = (B (x) C) vec(X), i.e. with this file's
16// operand naming (A (x) B) vec(X) = vec(B X A^T) -- together with the
17// factor-wise identities for the inverse, pseudo-inverse,
18// eigendecomposition, SVD and determinant of a Kronecker product.
19// [2] N. J. Higham, "Accuracy and Stability of Numerical Algorithms", 2nd ed.,
20// SIAM, 2002, chapter 27. Avoiding spurious overflow by rescaling with
21// powers of two, the technique behind the exponent-balanced determinant.
22// [3] P. H. Sterbenz, "Floating-Point Computation", Prentice-Hall, 1974.
23// Scaling by a power of two is exact, the property the determinant's
24// rescaling relies on.
25
26#ifndef EIGEN_STRUCTURED_KRONECKER_OPERATOR_H
27#define EIGEN_STRUCTURED_KRONECKER_OPERATOR_H
28
29// IWYU pragma: private
30#include "./InternalHeaderCheck.h"
31
32namespace Eigen {
33
34template <typename LhsMatrix, typename RhsMatrix>
36template <typename LhsMatrix, typename RhsMatrix>
37class KroneckerSum;
38template <typename OperatorType, int Options>
40
41namespace internal {
42
43template <typename LhsMatrix, typename RhsMatrix>
44struct traits<KroneckerOperator<LhsMatrix, RhsMatrix>> {
45 using Scalar = typename LhsMatrix::Scalar;
46 using StorageKind = Dense;
47 using XprKind = MatrixXpr;
48 using StorageIndex = int;
49 // size_at_compile_time is the compile-time dimension product, Dynamic when a
50 // factor is unknown or the product would overflow int.
51 static constexpr int RowsAtCompileTime =
52 size_at_compile_time(traits<LhsMatrix>::RowsAtCompileTime, traits<RhsMatrix>::RowsAtCompileTime);
53 static constexpr int ColsAtCompileTime =
54 size_at_compile_time(traits<LhsMatrix>::ColsAtCompileTime, traits<RhsMatrix>::ColsAtCompileTime);
55 static constexpr int MaxRowsAtCompileTime = RowsAtCompileTime;
56 static constexpr int MaxColsAtCompileTime = ColsAtCompileTime;
57 // Deliberately no NestByRefBit: transpose(), conjugate(), adjoint(), inverse(),
58 // eigenvectors(), matrixU() and matrixV() return owning temporaries (the
59 // operator stores its factors by value), so Product must nest the operator by
60 // value for a delayed-evaluated product expression to keep its left factor
61 // alive. The copy is O(m1 n1 + m2 n2), negligible against the product
62 // evaluation.
63 static constexpr int Flags = 0;
64};
65
66template <typename LhsMatrix, typename RhsMatrix>
67struct evaluator_traits<KroneckerOperator<LhsMatrix, RhsMatrix>> {
68 using Kind = IndexBased;
69 using Shape = StructuredShape;
70};
71
72// Factor kinds, each with its operations in the kron_factor_* helpers below:
73// dense; diagonal (stored as its diagonal); sparse (compressed, solved by
74// SparseLU); identity (a kron_identity_factor, dimensions only, skipped in
75// products); Kronecker (a nested KroneckerOperator, for three or more factors);
76// Kronecker sum (a KroneckerSum, see KroneckerSum.h).
77
78template <typename Scalar_, int Rows_, int Cols_>
79class kron_identity_factor;
80
81template <typename Scalar_, int Rows_, int Cols_>
82struct traits<kron_identity_factor<Scalar_, Rows_, Cols_>> : traits<Matrix<Scalar_, Rows_, Cols_>> {};
83
88template <typename Scalar_, int Rows_, int Cols_>
89class kron_identity_factor : public EigenBase<kron_identity_factor<Scalar_, Rows_, Cols_>> {
90 public:
91 using Scalar = Scalar_;
92 using PlainObject = Matrix<Scalar, Rows_, Cols_>;
93 static constexpr int RowsAtCompileTime = Rows_;
94 static constexpr int ColsAtCompileTime = Cols_;
95
96 kron_identity_factor(Index rows, Index cols) : m_rows(rows), m_cols(cols) {}
97 template <typename PlainObjectType>
98 explicit kron_identity_factor(const CwiseNullaryOp<scalar_identity_op<Scalar>, PlainObjectType>& identity)
99 : m_rows(identity.rows()), m_cols(identity.cols()) {}
100
101 EIGEN_DEVICE_FUNC constexpr Index rows() const { return m_rows.value(); }
102 EIGEN_DEVICE_FUNC constexpr Index cols() const { return m_cols.value(); }
103
104 private:
105 variable_if_dynamic<Index, Rows_> m_rows;
106 variable_if_dynamic<Index, Cols_> m_cols;
107};
108
109template <typename Factor>
110struct kron_factor_is_diagonal : std::false_type {};
111template <typename Scalar, int Size, int MaxSize>
112struct kron_factor_is_diagonal<DiagonalMatrix<Scalar, Size, MaxSize>> : std::true_type {};
113
114template <typename Factor>
115struct kron_factor_is_dense_matrix : std::false_type {};
116template <typename Scalar, int Rows, int Cols, int Options, int MaxRows, int MaxCols>
117struct kron_factor_is_dense_matrix<Matrix<Scalar, Rows, Cols, Options, MaxRows, MaxCols>> : std::true_type {};
118
119template <typename Factor>
120struct kron_factor_is_sparse_matrix : std::false_type {};
121template <typename Scalar, int Options, typename StorageIndex>
122struct kron_factor_is_sparse_matrix<SparseMatrix<Scalar, Options, StorageIndex>> : std::true_type {};
123
124template <typename Factor>
125struct kron_factor_is_identity : std::false_type {};
126template <typename Scalar, int Rows, int Cols>
127struct kron_factor_is_identity<kron_identity_factor<Scalar, Rows, Cols>> : std::true_type {};
128
129template <typename Factor>
130struct kron_factor_is_kronecker : std::false_type {};
131template <typename LhsMatrix, typename RhsMatrix>
132struct kron_factor_is_kronecker<KroneckerOperator<LhsMatrix, RhsMatrix>> : std::true_type {};
133
134template <typename Factor>
135struct kron_factor_is_kronecker_sum : std::false_type {};
136template <typename LhsMatrix, typename RhsMatrix>
137struct kron_factor_is_kronecker_sum<KroneckerSum<LhsMatrix, RhsMatrix>> : std::true_type {};
138
139// The factor kind, the dispatch key of kron_factor_ops and kron_factor_solver.
140constexpr int kKronDenseFactor = 0;
141constexpr int kKronDiagonalFactor = 1;
142constexpr int kKronSparseFactor = 2;
143constexpr int kKronIdentityFactor = 3;
144constexpr int kKronKroneckerFactor = 4;
145constexpr int kKronSumFactor = 5;
146
147template <typename Factor>
148constexpr int kron_factor_kind() {
149 return kron_factor_is_diagonal<Factor>::value ? kKronDiagonalFactor
150 : kron_factor_is_sparse_matrix<Factor>::value ? kKronSparseFactor
151 : kron_factor_is_identity<Factor>::value ? kKronIdentityFactor
152 : kron_factor_is_kronecker<Factor>::value ? kKronKroneckerFactor
153 : kron_factor_is_kronecker_sum<Factor>::value ? kKronSumFactor
154 : kKronDenseFactor;
155}
156
161template <typename Derived, bool StoredAsIs = kron_factor_is_identity<Derived>::value ||
162 kron_factor_is_kronecker<Derived>::value ||
163 kron_factor_is_kronecker_sum<Derived>::value>
164struct kron_factor_storage {
165 using type = typename Derived::PlainObject;
166};
167template <typename Derived>
168struct kron_factor_storage<Derived, true> {
169 using type = Derived;
170};
171template <typename Scalar, typename PlainObjectType>
172struct kron_factor_storage<CwiseNullaryOp<scalar_identity_op<Scalar>, PlainObjectType>, false> {
173 using type = kron_identity_factor<Scalar, PlainObjectType::RowsAtCompileTime, PlainObjectType::ColsAtCompileTime>;
174};
175
180template <typename Factor, int Kind = kron_factor_kind<Factor>()>
181struct kron_factor_visitable {
182 using type = Factor;
183 static const Factor& get(const Factor& f) { return f; }
184};
185
189template <typename LhsMatrix, typename RhsMatrix,
190 bool Unchanged = std::is_same<typename kron_factor_visitable<LhsMatrix>::type, LhsMatrix>::value &&
191 std::is_same<typename kron_factor_visitable<RhsMatrix>::type, RhsMatrix>::value>
192struct kron_operator_visitable {
193 using Factor = KroneckerOperator<LhsMatrix, RhsMatrix>;
194 using type = Factor;
195 static const Factor& get(const Factor& f) { return f; }
196};
197template <typename LhsMatrix, typename RhsMatrix>
198struct kron_operator_visitable<LhsMatrix, RhsMatrix, false> {
199 using LhsVisitable = kron_factor_visitable<LhsMatrix>;
200 using RhsVisitable = kron_factor_visitable<RhsMatrix>;
201 using type = KroneckerOperator<typename LhsVisitable::type, typename RhsVisitable::type>;
202 static type get(const KroneckerOperator<LhsMatrix, RhsMatrix>& f) {
203 return type(LhsVisitable::get(f.lhs()), RhsVisitable::get(f.rhs()));
204 }
205};
206template <typename LhsMatrix, typename RhsMatrix>
207struct kron_factor_visitable<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor>
208 : kron_operator_visitable<LhsMatrix, RhsMatrix> {};
209
216template <typename Stacked, typename Xpr>
217void kron_stack_columns(Stacked& stacked, const Xpr& x, Index rows, Index cols) {
218 stacked.resize(rows * x.cols(), cols);
219 for (Index k = 0; k < x.cols(); ++k)
220 stacked.middleRows(k * rows, rows) = x.col(k).reshaped(rows, cols).template cast<typename Stacked::Scalar>();
221}
222
228template <typename WorkScalar>
229Index kron_rhs_chunk(Index perColumn) {
230 const Index budget = Index(l2CacheSize() / 8) / Index(sizeof(WorkScalar));
231 return numext::maxi(Index(1), budget / numext::maxi(perColumn, Index(1)));
232}
233
234template <typename Factor, int Kind = kron_factor_kind<Factor>()>
235struct kron_factor_ops {
236 // Dense factor.
237 using Scalar = typename Factor::Scalar;
238 using RealScalar = typename NumTraits<Scalar>::Real;
239 using TransposedFactor = Matrix<Scalar, Factor::ColsAtCompileTime, Factor::RowsAtCompileTime>;
240 using InverseFactor = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
241 // Every entry is stored: a materialization has no structurally zero blocks
242 // to clear, and forEachNonZero visits all m*n entries in column-major order.
243 static constexpr bool StoresAllEntries = true;
244
245 static void prepare(Factor&) {}
246 static bool coeffIfStored(const Factor& f, Index row, Index col, Scalar& value) {
247 value = f.coeff(row, col);
248 return true;
249 }
250 template <typename Visitor>
251 static void forEachNonZero(const Factor& f, Visitor&& visit) {
252 for (Index j = 0; j < f.cols(); ++j)
253 for (Index i = 0; i < f.rows(); ++i) visit(i, j, f.coeff(i, j));
254 }
257 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool rowMajor) {
258 return Matrix<Index, Dynamic, 1>::Constant(rowMajor ? f.rows() : f.cols(), rowMajor ? f.cols() : f.rows());
259 }
260 static auto transposed(const Factor& f) { return f.transpose(); }
261 static auto conjugated(const Factor& f) { return f.conjugate(); }
262 static auto adjointed(const Factor& f) { return f.adjoint(); }
263 static auto inversed(const Factor& f) { return f.inverse(); }
264 // The factor as a dense expression, for the decomposition family.
265 static const Factor& denseFactor(const Factor& f) { return f; }
266 // The factor as the operand of a dense block assignment dst = a * f.
267 static const Factor& blockOperand(const Factor& f) { return f; }
268 static bool isSquareIdentity(const Factor&) { return false; }
269 // dst += alpha F X and dst += alpha X F^T: the two sides of the vec-trick product B X A^T.
270 // work: scratch for a nested factor's right product, owned by the caller's loop.
271 template <typename Dst, typename Alpha, typename Xpr>
272 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
273 dst.noalias() += alpha * (f * X);
274 }
275 template <typename Dst, typename Alpha, typename Xpr, typename Work>
276 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work&) {
277 dst.noalias() += alpha * (X * f.transpose());
278 }
279 static int exponentBound(const Factor& f) { return structured_exponent_bound(f); }
284 static Scalar balancedDet(const Factor& M, Index& exponent) {
285 // Scale small factors up, exactly, so that the elimination runs on normal
286 // numbers: a subnormal near 2^e carries only e - min_exponent + digits bits.
287 // Scaling down could erase small pivots in factors with a wide exponent range,
288 // and every entry is scaled exactly because a small entry can be a pivot.
289 const int bound = exponentBound(M);
290 const int scaleExponent = numext::mini(bound, 0);
291 Factor normalized = M;
292 structured_ldexp_entries_exact(normalized, -scaleExponent);
293 exponent += M.rows() * scaleExponent;
294 PartialPivLU<Factor> lu(normalized);
295 Scalar m = Scalar(RealScalar(lu.permutationP().determinant())); // +-1
296 for (Index i = 0; i < M.rows(); ++i)
297 m = balance_exponent(m * balance_exponent(lu.matrixLU().coeff(i, i), exponent), exponent);
298 return m;
299 }
300};
301
302template <typename Factor>
303struct kron_factor_ops<Factor, kKronDiagonalFactor> {
304 // Diagonal factor: everything runs on the stored diagonal vector.
305 using Scalar = typename Factor::Scalar;
306 using TransposedFactor = typename Factor::PlainObject; // a diagonal matrix is its own transpose
307 using InverseFactor = typename Factor::PlainObject; // entrywise reciprocals stay diagonal
308 static constexpr bool StoresAllEntries = false;
309
310 static void prepare(Factor&) {}
311 static bool coeffIfStored(const Factor& f, Index row, Index col, Scalar& value) {
312 if (row != col) return false;
313 value = f.diagonal().coeff(row);
314 return true;
315 }
316 template <typename Visitor>
317 static void forEachNonZero(const Factor& f, Visitor&& visit) {
318 for (Index k = 0; k < f.rows(); ++k) visit(k, k, f.diagonal().coeff(k));
319 }
320 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool) {
321 return Matrix<Index, Dynamic, 1>::Ones(f.rows());
322 }
323 static const Factor& transposed(const Factor& f) { return f; }
324 static auto conjugated(const Factor& f) { return f.diagonal().conjugate().asDiagonal(); }
325 static auto adjointed(const Factor& f) { return f.diagonal().conjugate().asDiagonal(); }
326 static auto inversed(const Factor& f) { return f.inverse(); }
327 static typename Factor::DenseMatrixType denseFactor(const Factor& f) { return f.toDenseMatrix(); }
328 static const Factor& blockOperand(const Factor& f) { return f; }
329 static bool isSquareIdentity(const Factor&) { return false; }
330 template <typename Dst, typename Alpha, typename Xpr>
331 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
332 dst.noalias() += alpha * (f * X);
333 }
334 template <typename Dst, typename Alpha, typename Xpr, typename Work>
335 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work&) {
336 dst.noalias() += alpha * (X * f);
337 }
338 static int exponentBound(const Factor& f) { return structured_exponent_bound(f.diagonal()); }
339 static Scalar balancedDet(const Factor& D, Index& exponent) {
340 // Scale a small diagonal up first: the balancing below compares and scales
341 // in floating point, which reads a subnormal entry as zero under flush-to-zero.
342 const int bound = exponentBound(D);
343 const int scaleExponent = numext::mini(bound, 0);
344 typename Factor::DiagonalVectorType d = D.diagonal();
345 structured_ldexp_entries_exact(d, -scaleExponent);
346 exponent += D.rows() * scaleExponent;
347 Scalar m(1);
348 for (Index i = 0; i < D.rows(); ++i) m = balance_exponent(m * balance_exponent(d.coeff(i), exponent), exponent);
349 return m;
350 }
351};
352
357template <typename SparseType>
358class kron_sparse_lu : public SparseLU<SparseType> {
359 public:
360 using Base = SparseLU<SparseType>;
361 using Scalar = typename SparseType::Scalar;
362 using RealScalar = typename NumTraits<Scalar>::Real;
363
364 Scalar balancedDet(Index& exponent) const {
365 eigen_assert(Base::info() == Success);
366 Scalar m = Scalar(RealScalar(Base::m_detPermR * Base::m_detPermC));
367 for (Index j = 0; j < Base::cols(); ++j) {
368 typename Base::SCMatrix::InnerIterator it(Base::m_Lstore, j);
369 while (it && it.index() != j) ++it;
370 if (it) m = balance_exponent(m * balance_exponent(it.value(), exponent), exponent);
371 }
372 return m;
373 }
374};
375
376template <typename Factor>
377struct kron_factor_ops<Factor, kKronSparseFactor> {
378 // Sparse factor: the products run through the sparse-dense kernels, the
379 // solve and the determinant through a SparseLU factorization.
380 using Scalar = typename Factor::Scalar;
381 using RealScalar = typename NumTraits<Scalar>::Real;
382 using ColMajorFactor = SparseMatrix<Scalar, ColMajor, typename Factor::StorageIndex>;
383 using TransposedFactor = Factor; // the transpose is stored sparse, in the same storage order
384 using InverseFactor = Matrix<Scalar, Dynamic, Dynamic, ColMajor>; // dense in general
385 static constexpr bool StoresAllEntries = false;
386
387 // coeffs() below reads the compressed value array.
388 static void prepare(Factor& f) { f.makeCompressed(); }
389 static bool coeffIfStored(const Factor& f, Index row, Index col, Scalar& value) {
390 const Index outer = Factor::IsRowMajor ? row : col;
391 const Index inner = Factor::IsRowMajor ? col : row;
392 const Index start = f.outerIndexPtr()[outer], end = f.outerIndexPtr()[outer + 1];
393 if (start == end) return false;
394 const Index position = f.data().searchLowerIndex(start, end, inner);
395 if (position == end || f.innerIndexPtr()[position] != inner) return false;
396 value = f.valuePtr()[position];
397 return true;
398 }
399 template <typename Visitor>
400 static void forEachNonZero(const Factor& f, Visitor&& visit) {
401 for (Index k = 0; k < f.outerSize(); ++k)
402 for (typename Factor::InnerIterator it(f, k); it; ++it) visit(it.row(), it.col(), it.value());
403 }
404 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool rowMajor) {
405 Matrix<Index, Dynamic, 1> counts = Matrix<Index, Dynamic, 1>::Zero(rowMajor ? f.rows() : f.cols());
406 for (Index k = 0; k < f.outerSize(); ++k)
407 for (typename Factor::InnerIterator it(f, k); it; ++it) ++counts[rowMajor ? it.row() : it.col()];
408 return counts;
409 }
410 static auto transposed(const Factor& f) { return f.transpose(); }
411 static auto conjugated(const Factor& f) { return f.conjugate(); }
412 static auto adjointed(const Factor& f) { return f.adjoint(); }
416 static InverseFactor inversed(const Factor& f) {
417 const ColMajorFactor colMajor(f);
418 SparseLU<ColMajorFactor> lu(colMajor);
419 if (lu.info() != Success) return nanMatrix(f.rows(), f.cols());
420 return lu.solve(InverseFactor::Identity(f.rows(), f.cols()));
421 }
425 static InverseFactor nanMatrix(Index rows, Index cols) {
426 return InverseFactor::Constant(rows, cols, Scalar(NumTraits<RealScalar>::quiet_NaN()));
427 }
428 static InverseFactor denseFactor(const Factor& f) { return InverseFactor(f); }
429 static const Factor& blockOperand(const Factor& f) { return f; }
430 static bool isSquareIdentity(const Factor&) { return false; }
431 template <typename Dst, typename Alpha, typename Xpr>
432 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
433 dst.noalias() += alpha * (f * X);
434 }
435 template <typename Dst, typename Alpha, typename Xpr, typename Work>
436 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work&) {
437 dst.noalias() += alpha * (X * f.transpose());
438 }
439 static int exponentBound(const Factor& f) { return structured_exponent_bound(f.coeffs()); }
440 static Scalar balancedDet(const Factor& M, Index& exponent) {
441 // Scale small factors up, exactly, so that the elimination runs on normal
442 // numbers: a subnormal near 2^e carries only e - min_exponent + digits bits.
443 // Scaling down could erase small pivots in factors with a wide exponent range.
444 const int bound = exponentBound(M);
445 const int scaleExponent = numext::mini(bound, 0);
446 ColMajorFactor normalized(M);
447 if (scaleExponent != 0) {
448 auto values = normalized.coeffs();
449 structured_ldexp_entries_exact(values, -scaleExponent);
450 }
451 kron_sparse_lu<ColMajorFactor> lu;
452 lu.compute(normalized);
453 if (lu.info() == Success) {
454 exponent += M.rows() * scaleExponent;
455 return lu.balancedDet(exponent);
456 }
457 // An aborted factorization met an exactly zero pivot column -- an exactly
458 // singular factor -- unless a non-finite entry defeated the pivot search.
459 return M.coeffs().allFinite() ? Scalar(0) : Scalar(NumTraits<RealScalar>::quiet_NaN());
460 }
461};
462
463template <typename Factor>
464struct kron_factor_ops<Factor, kKronIdentityFactor> {
465 // Identity factor, possibly rectangular: the m x n matrix I with I(i,i) = 1
466 // for i < min(m, n). I X keeps the leading min(m, n) rows of X, X I^T its
467 // leading min(m, n) columns.
468 using Scalar = typename Factor::Scalar;
469 using TransposedFactor = kron_identity_factor<Scalar, Factor::ColsAtCompileTime, Factor::RowsAtCompileTime>;
470 using InverseFactor = Factor;
471 static constexpr bool StoresAllEntries = false;
472
473 static void prepare(Factor&) {}
474 static bool coeffIfStored(const Factor&, Index row, Index col, Scalar& value) {
475 if (row != col) return false;
476 value = Scalar(1);
477 return true;
478 }
479 template <typename Visitor>
480 static void forEachNonZero(const Factor& f, Visitor&& visit) {
481 for (Index k = 0; k < numext::mini(f.rows(), f.cols()); ++k) visit(k, k, Scalar(1));
482 }
483 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool rowMajor) {
484 Matrix<Index, Dynamic, 1> counts = Matrix<Index, Dynamic, 1>::Zero(rowMajor ? f.rows() : f.cols());
485 counts.head(numext::mini(f.rows(), f.cols())).setOnes();
486 return counts;
487 }
488 static TransposedFactor transposed(const Factor& f) { return TransposedFactor(f.cols(), f.rows()); }
489 static const Factor& conjugated(const Factor& f) { return f; }
490 static TransposedFactor adjointed(const Factor& f) { return transposed(f); }
491 static const Factor& inversed(const Factor& f) { return f; }
492 static typename Factor::PlainObject denseFactor(const Factor& f) { return blockOperand(f); }
493 static typename Factor::PlainObject::IdentityReturnType blockOperand(const Factor& f) {
494 return Factor::PlainObject::Identity(f.rows(), f.cols());
495 }
496 static bool isSquareIdentity(const Factor& f) { return f.rows() == f.cols(); }
497 template <typename Dst, typename Alpha, typename Xpr>
498 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
499 const Index k = numext::mini(f.rows(), f.cols());
500 dst.topRows(k) += alpha * X.topRows(k);
501 }
502 template <typename Dst, typename Alpha, typename Xpr, typename Work>
503 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work&) {
504 const Index k = numext::mini(f.rows(), f.cols());
505 dst.leftCols(k) += alpha * X.leftCols(k);
506 }
507 static Scalar balancedDet(const Factor&, Index&) { return Scalar(1); }
508};
509
510template <typename LhsMatrix, typename RhsMatrix>
511struct kron_factor_ops<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor> {
512 // Nested Kronecker factor K = L (x) R: every operation recurses into L and R.
513 using Factor = KroneckerOperator<LhsMatrix, RhsMatrix>;
514 using Scalar = typename Factor::Scalar;
515 using LhsOps = kron_factor_ops<LhsMatrix>;
516 using RhsOps = kron_factor_ops<RhsMatrix>;
517 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
518 using TransposedFactor = KroneckerOperator<typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor>;
519 using InverseFactor = KroneckerOperator<typename LhsOps::InverseFactor, typename RhsOps::InverseFactor>;
520 static constexpr bool StoresAllEntries = LhsOps::StoresAllEntries && RhsOps::StoresAllEntries;
521
522 static void prepare(Factor&) {}
523 static bool coeffIfStored(const Factor& f, Index row, Index col, Scalar& value) {
524 const Index m2 = f.rhs().rows(), n2 = f.rhs().cols();
525 Scalar a, b;
526 if (!LhsOps::coeffIfStored(f.lhs(), row / m2, col / n2, a) ||
527 !RhsOps::coeffIfStored(f.rhs(), row % m2, col % n2, b))
528 return false;
529 value = a * b;
530 return true;
531 }
532 // Visits (iA m2 + iB, jA n2 + jB) with the loop over L outermost, so a fixed
533 // column is visited in increasing row and a fixed row in increasing column,
534 // the order the sparse materialization inserts in.
535 template <typename Visitor>
536 static void forEachNonZero(const Factor& f, Visitor&& visit) {
537 using RhsVisitable = kron_factor_visitable<RhsMatrix>;
538 const Index m2 = f.rhs().rows(), n2 = f.rhs().cols();
539 const auto& R = RhsVisitable::get(f.rhs());
540 LhsOps::forEachNonZero(f.lhs(), [&R, &visit, m2, n2](Index iA, Index jA, const Scalar& a) {
541 kron_factor_ops<typename RhsVisitable::type>::forEachNonZero(
542 R, [&visit, m2, n2, iA, jA, &a](Index iB, Index jB, const Scalar& b) {
543 visit(iA * m2 + iB, jA * n2 + jB, a * b);
544 });
545 });
546 }
547 static Matrix<Index, Dynamic, 1> innerNonZeros(const Factor& f, bool rowMajor) {
548 const Matrix<Index, Dynamic, Dynamic, ColMajor> counts =
549 RhsOps::innerNonZeros(f.rhs(), rowMajor) * LhsOps::innerNonZeros(f.lhs(), rowMajor).transpose();
550 return counts.reshaped();
551 }
552 static TransposedFactor transposed(const Factor& f) { return f.transpose(); }
553 static Factor conjugated(const Factor& f) { return f.conjugate(); }
554 static TransposedFactor adjointed(const Factor& f) { return f.adjoint(); }
555 static InverseFactor inversed(const Factor& f) { return f.inverse(); }
556 static DenseMatrix denseFactor(const Factor& f) { return DenseMatrix(f); }
557 static DenseMatrix blockOperand(const Factor& f) { return denseFactor(f); }
558 static bool isSquareIdentity(const Factor&) { return false; }
559 template <typename Dst, typename Alpha, typename Xpr>
560 static void addLeftProduct(Dst& dst, const Alpha& alpha, const Factor& f, const Xpr& X) {
561 f.addProduct(dst, X, alpha);
562 }
563 // X K^T without forming X^T: with X_j = X(:, j nR : (j+1) nR - 1), j < nL,
564 // X (L (x) R)^T = W L^T, W(:, j) = vec(X_j R^T), W (p mR) x nL in work,
565 // and W = X_{[p nR x nL]} when R is a square identity.
566 template <typename Dst, typename Alpha, typename Xpr, typename Work>
567 static void addRightProduct(Dst& dst, const Alpha& alpha, const Xpr& X, const Factor& f, Work& work) {
568 const Index p = X.rows(), mL = f.lhs().rows(), nL = f.lhs().cols(), mR = f.rhs().rows(), nR = f.rhs().cols();
569 auto dstL = dst.reshaped(p * mR, mL);
570 if (RhsOps::isSquareIdentity(f.rhs())) {
571 LhsOps::addRightProduct(dstL, alpha, X.reshaped(p * nR, nL), f.lhs(), work);
572 } else if (LhsOps::isSquareIdentity(f.lhs())) {
573 for (Index j = 0; j < nL; ++j) {
574 auto dstj = dst.middleCols(j * mR, mR);
575 RhsOps::addRightProduct(dstj, alpha, X.middleCols(j * nR, nR), f.rhs(), work);
576 }
577 } else {
578 Work inner; // scratch for L and R while work holds W; allocated only if one is nested
579 work.setZero(p * mR, nL);
580 for (Index j = 0; j < nL; ++j) {
581 auto Wj = work.col(j).reshaped(p, mR);
582 RhsOps::addRightProduct(Wj, Alpha(1), X.middleCols(j * nR, nR), f.rhs(), inner);
583 }
584 LhsOps::addRightProduct(dstL, alpha, work, f.lhs(), inner);
585 }
586 }
587 static Scalar balancedDet(const Factor& f, Index& exponent) { return f.balancedDeterminant(exponent); }
588};
589
594template <typename Factor, int Kind = kron_factor_kind<Factor>()>
595class kron_factor_solver {
596 public:
597 using Scalar = typename Factor::Scalar;
598 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
599
600 explicit kron_factor_solver(const Factor& f) : m_lu(f) {}
602 template <typename Xpr>
603 DenseMatrix solveLeft(const Xpr& M) const {
604 return m_lu.solve(M);
605 }
607 template <typename Xpr>
608 DenseMatrix solveTransposedRight(const Xpr& M) const {
609 return m_lu.solve(M.transpose()).transpose();
610 }
611
612 private:
613 PartialPivLU<DenseMatrix> m_lu;
614};
615
616template <typename Factor>
617class kron_factor_solver<Factor, kKronDiagonalFactor> {
618 public:
619 using Scalar = typename Factor::Scalar;
620 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
621
622 explicit kron_factor_solver(const Factor& f) : m_d(f.diagonal()) {}
623 template <typename Xpr>
624 DenseMatrix solveLeft(const Xpr& M) const {
625 return (M.array().colwise() / m_d.array()).matrix();
626 }
627 template <typename Xpr>
628 DenseMatrix solveTransposedRight(const Xpr& M) const {
629 return (M.array().rowwise() / m_d.transpose().array()).matrix();
630 }
631
632 private:
633 typename Factor::DiagonalVectorType m_d;
634};
635
636template <typename Factor>
637class kron_factor_solver<Factor, kKronSparseFactor> {
638 public:
639 using Scalar = typename Factor::Scalar;
640 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
641 using ColMajorFactor = SparseMatrix<Scalar, ColMajor, typename Factor::StorageIndex>;
642
643 explicit kron_factor_solver(const Factor& f) {
644 m_lu.compute(ColMajorFactor(f));
645 m_factorized = m_lu.info() == Success; // else the solves fill with NaN, see kron_factor_ops::nanMatrix
646 }
647 template <typename Xpr>
648 DenseMatrix solveLeft(const Xpr& M) const {
649 if (!m_factorized) return kron_factor_ops<Factor>::nanMatrix(M.rows(), M.cols());
650 return m_lu.solve(M);
651 }
652 template <typename Xpr>
653 DenseMatrix solveTransposedRight(const Xpr& M) const {
654 if (!m_factorized) return kron_factor_ops<Factor>::nanMatrix(M.rows(), M.cols());
655 // SparseLU solves into column-major storage only, which a transposed Solve
656 // expression would not evaluate into; the right-hand side stays a view.
657 const DenseMatrix Xt = m_lu.solve(M.transpose());
658 return Xt.transpose();
659 }
660
661 private:
662 bool m_factorized;
663 SparseLU<ColMajorFactor> m_lu;
664};
665
666template <typename Factor>
667class kron_factor_solver<Factor, kKronIdentityFactor> {
668 public:
669 using Scalar = typename Factor::Scalar;
670 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
671
672 explicit kron_factor_solver(const Factor&) {}
673 template <typename Xpr>
674 DenseMatrix solveLeft(const Xpr& M) const {
675 return M;
676 }
677 template <typename Xpr>
678 DenseMatrix solveTransposedRight(const Xpr& M) const {
679 return M;
680 }
681};
682
685template <typename LhsMatrix, typename RhsMatrix>
686class kron_factor_solver<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor> {
687 public:
688 using Factor = KroneckerOperator<LhsMatrix, RhsMatrix>;
689 using Scalar = typename Factor::Scalar;
690 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
691
692 explicit kron_factor_solver(const Factor& f)
693 : m_solverA(squareFactor(f.lhs())),
694 m_solverB(squareFactor(f.rhs())),
695 m_n1(f.lhs().cols()),
696 m_n2(f.rhs().cols()) {}
697 template <typename Xpr>
698 DenseMatrix solveLeft(const Xpr& M) const {
699 DenseMatrix x(M.rows(), M.cols());
700 Factor::solveWith(m_solverA, m_solverB, m_n1, m_n2, M, x);
701 return x;
702 }
703 // M K^{-T} = (K^{-1} M^T)^T.
704 template <typename Xpr>
705 DenseMatrix solveTransposedRight(const Xpr& M) const {
706 return solveLeft(M.transpose()).transpose();
707 }
708
709 private:
710 template <typename F>
711 static const F& squareFactor(const F& f) {
712 eigen_assert(f.rows() == f.cols() && "KroneckerOperator::solve requires square factors");
713 return f;
714 }
715
716 kron_factor_solver<LhsMatrix> m_solverA;
717 kron_factor_solver<RhsMatrix> m_solverB;
718 Index m_n1, m_n2;
719};
720
729template <typename Factor, int Kind = kron_factor_kind<Factor>()>
730struct kron_factor_spectrum {
731 using Ops = kron_factor_ops<Factor>;
732 using Scalar = typename Factor::Scalar;
733 using RealScalar = typename NumTraits<Scalar>::Real;
734 using ComplexScalar = std::complex<RealScalar>;
735 using DenseMatrix = Matrix<Scalar, Dynamic, Dynamic, ColMajor>;
736 using RealVector = Matrix<RealScalar, Dynamic, 1>;
737 using ComplexMatrix = Matrix<ComplexScalar, Dynamic, Dynamic, ColMajor>;
738 using ComplexVector = Matrix<ComplexScalar, Dynamic, 1>;
739 using Eigenvectors = ComplexMatrix;
740 using SingularVectors = DenseMatrix;
741
742 static ComplexMatrix complexFactor(const Factor& f) { return Ops::denseFactor(f).template cast<ComplexScalar>(); }
743 static ComplexVector eigenvalues(const Factor& f) {
744 ComplexEigenSolver<ComplexMatrix> es(complexFactor(f), /*computeEigenvectors=*/false);
745 eigen_assert(es.info() == Success);
746 return es.eigenvalues();
747 }
748 static Eigenvectors eigenvectors(const Factor& f) {
749 ComplexEigenSolver<ComplexMatrix> es(complexFactor(f));
750 eigen_assert(es.info() == Success);
751 return es.eigenvectors();
752 }
753 static RealVector singularValues(const Factor& f) {
754 return BDCSVD<DenseMatrix>(Ops::denseFactor(f)).singularValues();
755 }
756 static SingularVectors matrixU(const Factor& f) {
757 return BDCSVD<DenseMatrix, ComputeThinU>(Ops::denseFactor(f)).matrixU();
758 }
759 static SingularVectors matrixV(const Factor& f) {
760 return BDCSVD<DenseMatrix, ComputeThinV>(Ops::denseFactor(f)).matrixV();
761 }
762};
763
764template <typename LhsMatrix, typename RhsMatrix>
765struct kron_factor_spectrum<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor> {
766 using Factor = KroneckerOperator<LhsMatrix, RhsMatrix>;
767 using Eigenvectors = KroneckerOperator<typename kron_factor_spectrum<LhsMatrix>::Eigenvectors,
768 typename kron_factor_spectrum<RhsMatrix>::Eigenvectors>;
769 using SingularVectors = KroneckerOperator<typename kron_factor_spectrum<LhsMatrix>::SingularVectors,
770 typename kron_factor_spectrum<RhsMatrix>::SingularVectors>;
771
772 static typename Factor::ComplexVector eigenvalues(const Factor& f) { return f.eigenvalues(); }
773 static Eigenvectors eigenvectors(const Factor& f) { return f.eigenvectors(); }
774 static typename Factor::RealVector singularValues(const Factor& f) { return f.singularValues(); }
775 static SingularVectors matrixU(const Factor& f) { return f.matrixU(); }
776 static SingularVectors matrixV(const Factor& f) { return f.matrixV(); }
777};
778
779} // namespace internal
780
915template <typename LhsMatrix, typename RhsMatrix>
916class KroneckerOperator : public EigenBase<KroneckerOperator<LhsMatrix, RhsMatrix>> {
917 public:
918 using Scalar = typename LhsMatrix::Scalar;
919 using RealScalar = typename NumTraits<Scalar>::Real;
920 using StorageIndex = int;
921
922 static_assert(std::is_same<Scalar, typename RhsMatrix::Scalar>::value,
923 "KroneckerOperator requires both factors to have the same scalar type");
924 static_assert((internal::kron_factor_is_dense_matrix<LhsMatrix>::value ||
925 internal::kron_factor_kind<LhsMatrix>() != internal::kKronDenseFactor) &&
926 (internal::kron_factor_is_dense_matrix<RhsMatrix>::value ||
927 internal::kron_factor_kind<RhsMatrix>() != internal::kKronDenseFactor),
928 "KroneckerOperator factors must be plain Matrix, DiagonalMatrix or SparseMatrix types, identity "
929 "factors (makeKroneckerOperator stores an Identity() expression as one), KroneckerOperators or "
930 "KroneckerSums (owning their storage: views and other expressions would dangle)");
931
932 private:
933 // Factor-kind dispatch, see kron_factor_ops.
934 using LhsOps = internal::kron_factor_ops<LhsMatrix>;
935 using RhsOps = internal::kron_factor_ops<RhsMatrix>;
936 using LhsSpectrum = internal::kron_factor_spectrum<LhsMatrix>;
937 using RhsSpectrum = internal::kron_factor_spectrum<RhsMatrix>;
938 template <typename, int>
939 friend struct internal::kron_factor_ops;
940 template <typename, int>
941 friend class internal::kron_factor_solver;
942
943 public:
944 using ComplexScalar = std::complex<RealScalar>;
945 // The vec-trick reshapes below identify a vector of length n1*n2 with an
946 // n2 x n1 matrix whose columns are stacked, so every workspace taking part
947 // in a reshape is pinned to ColMajor explicitly: the semantics must not
948 // change under EIGEN_DEFAULT_TO_ROW_MAJOR.
950 using RealVector = Matrix<RealScalar, Dynamic, 1>;
952 using ComplexVector = Matrix<ComplexScalar, Dynamic, 1>;
953
954 static constexpr int RowsAtCompileTime =
955 internal::size_at_compile_time(LhsMatrix::RowsAtCompileTime, RhsMatrix::RowsAtCompileTime);
956 static constexpr int ColsAtCompileTime =
957 internal::size_at_compile_time(LhsMatrix::ColsAtCompileTime, RhsMatrix::ColsAtCompileTime);
958 static constexpr int MaxRowsAtCompileTime = RowsAtCompileTime;
959 static constexpr int MaxColsAtCompileTime = ColsAtCompileTime;
960 static constexpr int SizeAtCompileTime = internal::size_at_compile_time(RowsAtCompileTime, ColsAtCompileTime);
961 static constexpr int MaxSizeAtCompileTime = SizeAtCompileTime;
962 static constexpr bool IsRowMajor = false;
963 // Deliberately no IsVectorAtCompileTime: Ref<const KroneckerOperator>'s default
964 // StrideType argument reads it, so its absence makes internal::is_ref_compatible
965 // SFINAE to false and keeps the iterative solvers on their matrix-free path.
966
972 template <typename LhsDerived, typename RhsDerived>
974 : m_A(a.derived()), m_B(b.derived()) {
975 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_A, "KroneckerOperator factors must be non-empty");
976 EIGEN_INTERNAL_ASSERT_NONEMPTY_MSG(m_B, "KroneckerOperator factors must be non-empty");
977 LhsOps::prepare(m_A);
978 RhsOps::prepare(m_B);
979 }
980
981 EIGEN_DEVICE_FUNC Index rows() const { return m_A.rows() * m_B.rows(); }
982 EIGEN_DEVICE_FUNC Index cols() const { return m_A.cols() * m_B.cols(); }
983
987 template <int Options = ColMajor>
991
993 const LhsMatrix& lhs() const { return m_A; }
995 const RhsMatrix& rhs() const { return m_B; }
996
998 Scalar coeff(Index row, Index col) const {
999 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
1000 const Index m2 = m_B.rows(), n2 = m_B.cols();
1001 Scalar a, b;
1002 if (!LhsOps::coeffIfStored(m_A, row / m2, col / n2, a) || !RhsOps::coeffIfStored(m_B, row % m2, col % n2, b))
1003 return Scalar(0);
1004 return a * b;
1005 }
1006
1010 return {LhsOps::transposed(m_A), RhsOps::transposed(m_B)};
1011 }
1012
1014 KroneckerOperator conjugate() const { return {LhsOps::conjugated(m_A), RhsOps::conjugated(m_B)}; }
1015
1019 return {LhsOps::adjointed(m_A), RhsOps::adjointed(m_B)};
1020 }
1021
1038 template <typename Rhs>
1040 const Index n1 = m_A.cols(), n2 = m_B.cols();
1041 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_A, "KroneckerOperator::solve requires square factors");
1042 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_B, "KroneckerOperator::solve requires square factors");
1043 EIGEN_INTERNAL_ASSERT_SOLVER_RHS_MSG(*this, b, false, "right-hand side has the wrong number of rows");
1044 const internal::kron_factor_solver<LhsMatrix> solverA(m_A);
1045 const internal::kron_factor_solver<RhsMatrix> solverB(m_B);
1047 solveWith(solverA, solverB, n1, n2, b.derived(), x);
1048 return x;
1049 }
1050
1073 template <typename Rhs>
1075 EIGEN_STATIC_ASSERT(RowsAtCompileTime == Dynamic || Rhs::RowsAtCompileTime == Dynamic ||
1076 int(RowsAtCompileTime) == int(Rhs::RowsAtCompileTime),
1077 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES)
1078 const Index m1 = m_A.rows(), m2 = m_B.rows(), n1 = m_A.cols(), n2 = m_B.cols(), r = b.cols();
1079 eigen_assert(b.rows() == m1 * m2 && "right-hand side has the wrong number of rows");
1081 // The pivoted QR squares column norms, which over- or underflow on extreme
1082 // factor magnitudes, so decompose 2^-eA A and 2^-eB B and fold
1083 // 2^-(eA+eB) back into the solution.
1084 DenseMatrix An = LhsOps::denseFactor(m_A), Bn = RhsOps::denseFactor(m_B);
1085 if (!An.allFinite() || !Bn.allFinite()) {
1086 // The pivoted QR would rank a non-finite column out instead of propagating it.
1088 return x;
1089 }
1090 const int eA = internal::structured_exponent_bound(An), eB = internal::structured_exponent_bound(Bn);
1091 internal::structured_ldexp_entries_exact(An, -eA);
1092 internal::structured_ldexp_entries_exact(Bn, -eB);
1093 const CompleteOrthogonalDecomposition<DenseMatrix> codA(An), codB(Bn);
1094 typename internal::nested_eval<Rhs, 1>::type actualRhs(b.derived());
1095 DenseMatrix S, Z, X;
1096 const Index chunk = internal::kron_rhs_chunk<Scalar>(m1 * m2 + n2 * m1 + n1 * n2);
1097 for (Index k0 = 0; k0 < r; k0 += chunk) {
1098 const Index c = numext::mini(chunk, r - k0);
1099 internal::kron_stack_columns(S, actualRhs.middleCols(k0, c), m2, m1);
1100 Z = codB.solve(S.reshaped(m2, c * m1));
1101 X = codA.solve(Z.reshaped(n2 * c, m1).transpose()).transpose();
1102 internal::structured_ldexp_entries(X, -(eA + eB));
1103 for (Index k = 0; k < c; ++k) x.col(k0 + k).reshaped(n2, n1) = X.middleRows(k * n2, n2);
1104 }
1105 return x;
1106 }
1107
1123 Index rank() const {
1124 BDCSVD<DenseMatrix> svdA(LhsOps::denseFactor(m_A)), svdB(RhsOps::denseFactor(m_B));
1125 const RealVector &sa = svdA.singularValues(), &sb = svdB.singularValues();
1126 // An exactly zero factor zeroes the whole operator (and would make the
1127 // ratios below 0/0).
1128 if (sa[0] == RealScalar(0) || sb[0] == RealScalar(0)) return 0;
1129 const RealScalar tol = relativeRankThreshold();
1130 const SingularModes modesA(sa), modesB(sb);
1131 Index r = 0;
1132 for (Index i = 0; i < sa.size(); ++i)
1133 for (Index j = 0; j < sb.size(); ++j)
1134 // Negated ratio comparison so NaN ratios count as non-zero.
1135 if (modesA.retains(modesB, i, j, tol)) ++r;
1136 return r;
1137 }
1138
1145 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_A, "KroneckerOperator::inverse requires square factors");
1146 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_B, "KroneckerOperator::inverse requires square factors");
1147 return {LhsOps::inversed(m_A), RhsOps::inversed(m_B)};
1148 }
1149
1162 Scalar determinant() const {
1163 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_A, "KroneckerOperator::determinant requires square factors");
1164 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_B, "KroneckerOperator::determinant requires square factors");
1165 Index exponent = 0;
1166 const Scalar mant = balancedDeterminant(exponent);
1167 return internal::apply_exponent(mant, exponent);
1168 }
1169
1178 ComplexVector eigenvalues() const {
1179 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_A, "KroneckerOperator::eigenvalues requires square factors");
1180 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_B, "KroneckerOperator::eigenvalues requires square factors");
1181 // Column-major stacking of the nB x nA outer product puts mu_j(B) lambda_i(A)
1182 // at index i*nB + j, the Kronecker order.
1183 return (RhsSpectrum::eigenvalues(m_B) * LhsSpectrum::eigenvalues(m_A).transpose()).reshaped();
1184 }
1185
1191 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_A, "KroneckerOperator::eigenvectors requires square factors");
1192 EIGEN_INTERNAL_ASSERT_SQUARE_MSG(m_B, "KroneckerOperator::eigenvectors requires square factors");
1193 return {LhsSpectrum::eigenvectors(m_A), RhsSpectrum::eigenvectors(m_B)};
1194 }
1195
1203 RealVector singularValues() const {
1204 // Column-major stacking of the kB x kA outer product puts sigma_j(B) sigma_i(A)
1205 // at index i*kB + j, the Kronecker order.
1206 return (RhsSpectrum::singularValues(m_B) * LhsSpectrum::singularValues(m_A).transpose()).reshaped();
1207 }
1208
1213 return {LhsSpectrum::matrixU(m_A), RhsSpectrum::matrixU(m_B)};
1214 }
1215
1220 return {LhsSpectrum::matrixV(m_A), RhsSpectrum::matrixV(m_B)};
1221 }
1222
1226 template <typename Dest>
1227 void evalTo(Dest& dst) const {
1228 evalToImpl(dst, IsSparseDestination<Dest>());
1229 }
1230
1232 template <typename Dest>
1233 void addTo(Dest& dst) const {
1234 addToImpl(dst, IsSparseDestination<Dest>());
1235 }
1236
1238 template <typename Dest>
1239 void subTo(Dest& dst) const {
1240 subToImpl(dst, IsSparseDestination<Dest>());
1241 }
1242
1243 private:
1244 template <typename Dest>
1245 using IsSparseDestination = std::is_same<typename internal::traits<Dest>::StorageKind, Sparse>;
1246
1252 template <typename Dest>
1253 void evalToImpl(Dest& dst, std::false_type) const {
1254 const Index m2 = m_B.rows(), n2 = m_B.cols();
1255 if (!LhsOps::StoresAllEntries) dst.setZero();
1256 const auto& B = RhsOps::blockOperand(m_B);
1257 LhsOps::forEachNonZero(
1258 m_A, [&dst, &B, m2, n2](Index i, Index j, const Scalar& a) { dst.block(i * m2, j * n2, m2, n2) = a * B; });
1259 }
1260
1261 template <typename Dest>
1262 void addToImpl(Dest& dst, std::false_type) const {
1263 const Index m2 = m_B.rows(), n2 = m_B.cols();
1264 const auto& B = RhsOps::blockOperand(m_B);
1265 LhsOps::forEachNonZero(
1266 m_A, [&dst, &B, m2, n2](Index i, Index j, const Scalar& a) { dst.block(i * m2, j * n2, m2, n2) += a * B; });
1267 }
1268
1269 template <typename Dest>
1270 void subToImpl(Dest& dst, std::false_type) const {
1271 const Index m2 = m_B.rows(), n2 = m_B.cols();
1272 const auto& B = RhsOps::blockOperand(m_B);
1273 LhsOps::forEachNonZero(
1274 m_A, [&dst, &B, m2, n2](Index i, Index j, const Scalar& a) { dst.block(i * m2, j * n2, m2, n2) -= a * B; });
1275 }
1276
1286 template <typename Dest>
1287 void evalToImpl(Dest& S, std::true_type) const {
1288 using LhsVisitable = internal::kron_factor_visitable<LhsMatrix>;
1289 using RhsVisitable = internal::kron_factor_visitable<RhsMatrix>;
1290 using VisitedLhsOps = internal::kron_factor_ops<typename LhsVisitable::type>;
1291 using VisitedRhsOps = internal::kron_factor_ops<typename RhsVisitable::type>;
1292 const Index m2 = m_B.rows(), n2 = m_B.cols();
1293 const auto& A = LhsVisitable::get(m_A);
1294 const auto& B = RhsVisitable::get(m_B);
1295 S.resize(rows(), cols());
1296 using IndexVector = Matrix<Index, Dynamic, 1>;
1297 const IndexVector nnzA = VisitedLhsOps::innerNonZeros(A, Dest::IsRowMajor);
1298 const IndexVector nnzB = VisitedRhsOps::innerNonZeros(B, Dest::IsRowMajor);
1299 // Inner vectors kA of A and kB of B meet in inner vector kA * nnzB.size() + kB
1300 // of the product: the column-major stacking of the count outer product.
1301 const Matrix<Index, Dynamic, Dynamic, ColMajor> counts = nnzB * nnzA.transpose();
1302 S.reserve(counts.reshaped());
1303 VisitedLhsOps::forEachNonZero(A, [&S, &B, m2, n2](Index iA, Index jA, const Scalar& a) {
1304 VisitedRhsOps::forEachNonZero(B, [&S, m2, n2, iA, jA, &a](Index iB, Index jB, const Scalar& b) {
1305 S.insert(iA * m2 + iB, jA * n2 + jB) = a * b;
1306 });
1307 });
1308 S.makeCompressed();
1309 }
1310
1311 template <typename Dest>
1312 void addToImpl(Dest& dst, std::true_type) const {
1313 typename Dest::PlainObject product;
1314 evalTo(product);
1315 dst += product;
1316 }
1317
1318 template <typename Dest>
1319 void subToImpl(Dest& dst, std::true_type) const {
1320 typename Dest::PlainObject product;
1321 evalTo(product);
1322 dst -= product;
1323 }
1324
1325 public:
1331 template <typename Rhs>
1333 return Product<KroneckerOperator, Rhs>(*this, x.derived());
1334 }
1335
1354 template <typename Dest, typename Rhs, typename ProductScalar>
1355 void addProduct(Dest& dst, const Rhs& rhs, const ProductScalar& alpha) const {
1356 using ProductMatrix = Matrix<ProductScalar, Dynamic, Dynamic, ColMajor>; // ColMajor: see DenseMatrix
1357 const Index m1 = m_A.rows(), n1 = m_A.cols(), m2 = m_B.rows(), n2 = m_B.cols(), r = rhs.cols();
1358 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(*this, rhs, "invalid product: dimensions do not match");
1359 typename internal::nested_eval<Rhs, 1>::type actualRhs(rhs);
1360 const bool skipA = LhsOps::isSquareIdentity(m_A), skipB = RhsOps::isSquareIdentity(m_B);
1361 ProductMatrix X, BX, Y, work;
1362 const Index chunk = internal::kron_rhs_chunk<ProductScalar>(n1 * n2 + m2 * n1 + m2 * m1);
1363 for (Index k0 = 0; k0 < r; k0 += chunk) {
1364 const Index c = numext::mini(chunk, r - k0);
1365 if (c == 1) {
1366 const auto Xk = actualRhs.col(k0).reshaped(n2, n1);
1367 auto Yk = dst.col(k0).reshaped(m2, m1);
1368 if (skipA) {
1369 RhsOps::addLeftProduct(Yk, alpha, m_B, Xk);
1370 } else if (skipB) {
1371 LhsOps::addRightProduct(Yk, alpha, Xk, m_A, work);
1372 } else {
1373 BX.setZero(m2, n1);
1374 RhsOps::addLeftProduct(BX, ProductScalar(1), m_B, Xk);
1375 LhsOps::addRightProduct(Yk, alpha, BX, m_A, work);
1376 }
1377 continue;
1378 }
1379 internal::kron_stack_columns(X, actualRhs.middleCols(k0, c), n2, n1);
1380 if (!skipB) {
1381 BX.setZero(m2, c * n1);
1382 RhsOps::addLeftProduct(BX, ProductScalar(1), m_B, X.reshaped(n2, c * n1));
1383 }
1384 const auto BXhat = (skipB ? X : BX).reshaped(m2 * c, n1);
1385 if (!skipA) {
1386 Y.setZero(m2 * c, m1);
1387 LhsOps::addRightProduct(Y, ProductScalar(1), BXhat, m_A, work);
1388 }
1389 for (Index k = 0; k < c; ++k) {
1390 auto Yk = dst.col(k0 + k).reshaped(m2, m1);
1391 if (skipA)
1392 Yk += alpha * BXhat.middleRows(k * m2, m2);
1393 else
1394 Yk += alpha * Y.middleRows(k * m2, m2);
1395 }
1396 }
1397 }
1398
1399 private:
1411 RealScalar relativeRankThreshold() const {
1412 return RealScalar(numext::mini(rows(), cols())) * NumTraits<RealScalar>::epsilon();
1413 }
1414
1415 // Factor-level ratios and frexp decompositions, independent of the other factor.
1416 struct SingularModes {
1417 explicit SingularModes(const RealVector& s) : ratios(s.size()), mantissas(s.size()), exponents(s.size()) {
1418 for (Index i = 0; i < s.size(); ++i) {
1419 ratios[i] = s[i] / s[0];
1420 exponents[i] = 0;
1421 EIGEN_USING_STD(frexp);
1422 mantissas[i] = frexp(s[i], &exponents[i]);
1423 }
1424 }
1425
1426 bool retains(const SingularModes& other, Index i, Index j, RealScalar tol) const {
1427 // Negation counts NaN ratios as retained, matching SVDBase.
1428 if (ratios[i] * other.ratios[j] < tol) return false;
1429 const RealScalar m = mantissas[i] * other.mantissas[j];
1430 if (!(numext::isfinite)(m)) return true;
1431 if (m == RealScalar(0)) return false;
1432 // s_i*s_j = m*2^(e_i+e_j), with m in [0.25,1). Test the
1433 // smallest-normal clamp without forming an overflowing/underflowing product.
1434 const int e = exponents[i] + other.exponents[j] - (m < RealScalar(0.5) ? 1 : 0);
1435 return e >= std::numeric_limits<RealScalar>::min_exponent;
1436 }
1437
1438 RealVector ratios, mantissas;
1439 Matrix<int, Dynamic, 1> exponents;
1440 };
1441
1444 Scalar balancedDeterminant(Index& exponent) const {
1445 eigen_assert(m_A.rows() == m_A.cols() && m_B.rows() == m_B.cols() &&
1446 "KroneckerOperator::determinant requires square factors");
1447 const Scalar mant = balancedDetPow(m_A, m_B.cols(), exponent);
1448 return internal::balance_exponent(mant * balancedDetPow(m_B, m_A.cols(), exponent), exponent);
1449 }
1450
1455 template <typename SolverA, typename SolverB, typename Rhs, typename Dest>
1456 static void solveWith(const SolverA& solverA, const SolverB& solverB, Index n1, Index n2, const Rhs& b, Dest& x) {
1457 typename internal::nested_eval<Rhs, 1>::type actualRhs(b);
1458 DenseMatrix S, Z, X;
1459 const Index r = b.cols();
1460 const Index chunk = internal::kron_rhs_chunk<Scalar>(3 * n1 * n2);
1461 for (Index k0 = 0; k0 < r; k0 += chunk) {
1462 const Index c = numext::mini(chunk, r - k0);
1463 internal::kron_stack_columns(S, actualRhs.middleCols(k0, c), n2, n1);
1464 Z = solverB.solveLeft(S.reshaped(n2, c * n1));
1465 X = solverA.solveTransposedRight(Z.reshaped(n2 * c, n1));
1466 for (Index k = 0; k < c; ++k) x.col(k0 + k).reshaped(n2, n1) = X.middleRows(k * n2, n2);
1467 }
1468 }
1469
1479 template <typename Factor>
1480 static Scalar balancedDetPow(const Factor& M, Index power, Index& exponent) {
1481 Index e = 0;
1482 const Scalar m = internal::kron_factor_ops<Factor>::balancedDet(M, e);
1483 Scalar r(1);
1484 Index er = 0;
1485 for (Index k = 0; k < power; ++k) r = internal::balance_exponent(r * m, er);
1486 exponent += power * e + er;
1487 return r;
1488 }
1489
1490 LhsMatrix m_A;
1491 RhsMatrix m_B;
1492};
1493
1502template <typename LhsDerived, typename RhsDerived>
1503KroneckerOperator<typename internal::kron_factor_storage<LhsDerived>::type,
1504 typename internal::kron_factor_storage<RhsDerived>::type>
1506 return {a.derived(), b.derived()};
1507}
1508
1512template <typename D1, typename D2, typename D3, typename... Rest>
1514 const Rest&... rest) {
1515 return makeKroneckerOperator(a, makeKroneckerOperator(b, c, rest...));
1516}
1517
1518namespace internal {
1519
1520template <typename LhsMatrix, typename RhsMatrix, typename Rhs, int ProductTag>
1521struct generic_product_impl<KroneckerOperator<LhsMatrix, RhsMatrix>, Rhs, StructuredShape, DenseShape, ProductTag>
1522 : structured_product_impl<KroneckerOperator<LhsMatrix, RhsMatrix>, Rhs> {};
1523
1524} // namespace internal
1525
1526#if EIGEN_COMP_CXXVER < 17
1527template <typename LhsMatrix, typename RhsMatrix>
1528constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::RowsAtCompileTime;
1529template <typename LhsMatrix, typename RhsMatrix>
1530constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::ColsAtCompileTime;
1531template <typename LhsMatrix, typename RhsMatrix>
1532constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::MaxRowsAtCompileTime;
1533template <typename LhsMatrix, typename RhsMatrix>
1534constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::MaxColsAtCompileTime;
1535template <typename LhsMatrix, typename RhsMatrix>
1536constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::SizeAtCompileTime;
1537template <typename LhsMatrix, typename RhsMatrix>
1538constexpr int KroneckerOperator<LhsMatrix, RhsMatrix>::MaxSizeAtCompileTime;
1539template <typename LhsMatrix, typename RhsMatrix>
1540constexpr bool KroneckerOperator<LhsMatrix, RhsMatrix>::IsRowMajor;
1541#endif
1542
1543} // namespace Eigen
1544
1545#endif // EIGEN_STRUCTURED_KRONECKER_OPERATOR_H
The Kronecker product as an implicit operator that is never materialized.
Definition KroneckerOperator.h:916
KroneckerOperator< typename LhsOps::InverseFactor, typename RhsOps::InverseFactor > inverse() const
Definition KroneckerOperator.h:1144
KroneckerOperator< typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor > adjoint() const
Definition KroneckerOperator.h:1018
KroneckerOperator< typename LhsSpectrum::SingularVectors, typename RhsSpectrum::SingularVectors > matrixU() const
Definition KroneckerOperator.h:1212
Index rank() const
Definition KroneckerOperator.h:1123
Scalar determinant() const
Definition KroneckerOperator.h:1162
KroneckerSparseView< KroneckerOperator, Options > sparseView() const
Definition KroneckerOperator.h:988
const LhsMatrix & lhs() const
Definition KroneckerOperator.h:993
KroneckerOperator< typename LhsOps::TransposedFactor, typename RhsOps::TransposedFactor > transpose() const
Definition KroneckerOperator.h:1009
ComplexVector eigenvalues() const
Definition KroneckerOperator.h:1178
Product< KroneckerOperator, Rhs > operator*(const MatrixBase< Rhs > &x) const
Definition KroneckerOperator.h:1332
KroneckerOperator(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerOperator.h:973
KroneckerOperator< typename LhsSpectrum::SingularVectors, typename RhsSpectrum::SingularVectors > matrixV() const
Definition KroneckerOperator.h:1219
Matrix< Scalar, ColsAtCompileTime, Rhs::ColsAtCompileTime > leastSquaresSolve(const MatrixBase< Rhs > &b) const
Definition KroneckerOperator.h:1074
const RhsMatrix & rhs() const
Definition KroneckerOperator.h:995
KroneckerOperator< typename LhsSpectrum::Eigenvectors, typename RhsSpectrum::Eigenvectors > eigenvectors() const
Definition KroneckerOperator.h:1190
Matrix< Scalar, ColsAtCompileTime, Rhs::ColsAtCompileTime > solve(const MatrixBase< Rhs > &b) const
Definition KroneckerOperator.h:1039
KroneckerOperator conjugate() const
Definition KroneckerOperator.h:1014
RealVector singularValues() const
Definition KroneckerOperator.h:1203
Scalar coeff(Index row, Index col) const
Definition KroneckerOperator.h:998
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
Derived & setConstant(Index rows, Index cols, const Scalar &val)
const SingularValuesType & singularValues() const
ComputationInfo info() const
KroneckerOperator< typename internal::kron_factor_storage< LhsDerived >::type, typename internal::kron_factor_storage< RhsDerived >::type > makeKroneckerOperator(const EigenBase< LhsDerived > &a, const EigenBase< RhsDerived > &b)
Definition KroneckerOperator.h:1505
Namespace containing all symbols from the Eigen library.
constexpr Derived & derived()