Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
KroneckerSparseView.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#ifndef EIGEN_STRUCTURED_KRONECKER_SPARSE_VIEW_H
11#define EIGEN_STRUCTURED_KRONECKER_SPARSE_VIEW_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16namespace Eigen {
17
18namespace internal {
19
22template <typename Factor, int Kind = kron_factor_kind<Factor>()>
23struct kron_view_storage_index {
24 using type = int;
25};
26template <typename Scalar, int Options, typename StorageIndex>
27struct kron_view_storage_index<SparseMatrix<Scalar, Options, StorageIndex>, kKronSparseFactor> {
28 using type = StorageIndex;
29};
30template <typename LhsMatrix, typename RhsMatrix>
31struct kron_view_storage_index<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor>
32 : promote_index_type<typename kron_view_storage_index<LhsMatrix>::type,
33 typename kron_view_storage_index<RhsMatrix>::type> {};
34template <typename LhsMatrix, typename RhsMatrix>
35struct kron_view_storage_index<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor>
36 : promote_index_type<typename kron_view_storage_index<LhsMatrix>::type,
37 typename kron_view_storage_index<RhsMatrix>::type> {};
38
39template <typename OperatorType, int Options>
40struct traits<KroneckerSparseView<OperatorType, Options>> {
41 using Scalar = typename OperatorType::Scalar;
42 using StorageKind = Sparse;
43 using XprKind = MatrixXpr;
44 // The index type of the plain matrices Eigen evaluates the view into (eval(),
45 // product temporaries), which the user does not choose.
46 using StorageIndex = typename kron_view_storage_index<OperatorType>::type;
47 static constexpr int RowsAtCompileTime = OperatorType::RowsAtCompileTime;
48 static constexpr int ColsAtCompileTime = OperatorType::ColsAtCompileTime;
49 static constexpr int MaxRowsAtCompileTime = OperatorType::MaxRowsAtCompileTime;
50 static constexpr int MaxColsAtCompileTime = OperatorType::MaxColsAtCompileTime;
51 // Nested by reference like a SparseMatrix: the view owns a copy of the
52 // operator, which a by-value nesting would copy into every expression.
53 static constexpr unsigned int Flags = (unsigned(Options) & RowMajorBit) | NestByRefBit;
54};
55
59template <typename Factor, int Options, int Kind = kron_factor_kind<Factor>()>
60struct kron_view_factor {
61 using type = Factor;
62 static const Factor& convert(const Factor& f) { return f; }
63};
64template <typename Scalar, int FactorOptions, typename StorageIndex, int Options>
65struct kron_view_factor<SparseMatrix<Scalar, FactorOptions, StorageIndex>, Options, kKronSparseFactor> {
66 using type = SparseMatrix<Scalar, Options & RowMajorBit ? RowMajor : ColMajor, StorageIndex>;
67 // A same-order copy keeps the factor's entry order, and a compressed matrix
68 // may hold unsorted inner vectors; the iterators need them sorted.
69 static type convert(const SparseMatrix<Scalar, FactorOptions, StorageIndex>& f) {
70 type g(f);
71 if (g.innerIndicesAreSorted() != g.outerSize()) g.sortInnerIndices();
72 return g;
73 }
74};
75template <typename LhsMatrix, typename RhsMatrix, int Options>
76struct kron_view_factor<KroneckerOperator<LhsMatrix, RhsMatrix>, Options, kKronKroneckerFactor> {
77 using Lhs = kron_view_factor<LhsMatrix, Options>;
78 using Rhs = kron_view_factor<RhsMatrix, Options>;
79 using type = KroneckerOperator<typename Lhs::type, typename Rhs::type>;
80 static type convert(const KroneckerOperator<LhsMatrix, RhsMatrix>& f) {
81 return type(Lhs::convert(f.lhs()), Rhs::convert(f.rhs()));
82 }
83};
84template <typename LhsMatrix, typename RhsMatrix, int Options>
85struct kron_view_factor<KroneckerSum<LhsMatrix, RhsMatrix>, Options, kKronSumFactor> {
86 using Lhs = kron_view_factor<LhsMatrix, Options>;
87 using Rhs = kron_view_factor<RhsMatrix, Options>;
88 using type = KroneckerSum<typename Lhs::type, typename Rhs::type>;
89 static type convert(const KroneckerSum<LhsMatrix, RhsMatrix>& f) {
90 return type(Lhs::convert(f.lhs()), Rhs::convert(f.rhs()));
91 }
92};
93
97template <typename Factor, bool RowMajor, int Kind = kron_factor_kind<Factor>()>
98class kron_view_iterator {
99 public:
100 using Scalar = typename Factor::Scalar;
101 kron_view_iterator(const Factor& f, Index outer)
102 : m_f(&f), m_outer(outer), m_inner(0), m_end(RowMajor ? f.cols() : f.rows()) {}
103 explicit operator bool() const { return m_inner < m_end; }
104 kron_view_iterator& operator++() {
105 ++m_inner;
106 return *this;
107 }
108 Index index() const { return m_inner; }
109 Scalar value() const { return RowMajor ? m_f->coeff(m_outer, m_inner) : m_f->coeff(m_inner, m_outer); }
110
111 private:
112 const Factor* m_f;
113 Index m_outer, m_inner, m_end;
114};
115
116// Diagonal and identity factors: at most the diagonal entry.
117template <typename Factor, bool RowMajor>
118class kron_view_iterator<Factor, RowMajor, kKronDiagonalFactor> {
119 public:
120 using Scalar = typename Factor::Scalar;
121 kron_view_iterator(const Factor& f, Index outer) : m_f(&f), m_outer(outer), m_valid(true) {}
122 explicit operator bool() const { return m_valid; }
123 kron_view_iterator& operator++() {
124 m_valid = false;
125 return *this;
126 }
127 Index index() const { return m_outer; }
128 Scalar value() const { return m_f->diagonal().coeff(m_outer); }
129
130 private:
131 const Factor* m_f;
132 Index m_outer;
133 bool m_valid;
134};
135
136template <typename Factor, bool RowMajor>
137class kron_view_iterator<Factor, RowMajor, kKronIdentityFactor> {
138 public:
139 using Scalar = typename Factor::Scalar;
140 kron_view_iterator(const Factor& f, Index outer)
141 : m_outer(outer), m_valid(outer < numext::mini(f.rows(), f.cols())) {}
142 explicit operator bool() const { return m_valid; }
143 kron_view_iterator& operator++() {
144 m_valid = false;
145 return *this;
146 }
147 Index index() const { return m_outer; }
148 Scalar value() const { return Scalar(1); }
149
150 private:
151 Index m_outer;
152 bool m_valid;
153};
154
155// Sparse factor, compressed and stored in the view's order (see
156// kron_view_factor). Raw pointers rather than the matrix's InnerIterator keep
157// the iterator assignable, which the Kronecker iterator needs to restart it.
158template <typename Factor, bool RowMajor>
159class kron_view_iterator<Factor, RowMajor, kKronSparseFactor> {
160 public:
161 using Scalar = typename Factor::Scalar;
162 static_assert(bool(Factor::IsRowMajor) == RowMajor, "the view converts sparse factors to its storage order");
163 kron_view_iterator(const Factor& f, Index outer)
164 : m_values(f.valuePtr()),
165 m_indices(f.innerIndexPtr()),
166 m_pos(convert_index<Index>(f.outerIndexPtr()[outer])),
167 m_end(convert_index<Index>(f.outerIndexPtr()[outer + 1])) {
168 eigen_internal_assert(f.isCompressed());
169 }
170 explicit operator bool() const { return m_pos < m_end; }
171 kron_view_iterator& operator++() {
172 ++m_pos;
173 return *this;
174 }
175 Index index() const { return Index(m_indices[m_pos]); }
176 Scalar value() const { return m_values[m_pos]; }
177
178 private:
179 const Scalar* m_values;
180 const typename Factor::StorageIndex* m_indices;
181 Index m_pos, m_end;
182};
183
188template <typename LhsMatrix, typename RhsMatrix, bool RowMajor>
189class kron_view_iterator<KroneckerOperator<LhsMatrix, RhsMatrix>, RowMajor, kKronKroneckerFactor> {
190 public:
191 using Factor = KroneckerOperator<LhsMatrix, RhsMatrix>;
192 using Scalar = typename Factor::Scalar;
193 kron_view_iterator(const Factor& f, Index outer)
194 : m_rhs(&f.rhs()),
195 m_outerR(outer % outerSize(f.rhs())),
196 m_innerR(RowMajor ? f.rhs().cols() : f.rhs().rows()),
197 m_itL(f.lhs(), outer / outerSize(f.rhs())),
198 m_itR(f.rhs(), m_outerR),
199 m_nonEmptyR(bool(m_itR)) {}
200 explicit operator bool() const { return m_nonEmptyR && bool(m_itL); }
201 kron_view_iterator& operator++() {
202 ++m_itR;
203 if (!m_itR) {
204 ++m_itL;
205 if (m_itL) m_itR = RhsIterator(*m_rhs, m_outerR);
206 }
207 return *this;
208 }
209 Index index() const { return m_itL.index() * m_innerR + m_itR.index(); }
210 Scalar value() const { return m_itL.value() * m_itR.value(); }
211
212 private:
213 using LhsIterator = kron_view_iterator<LhsMatrix, RowMajor>;
214 using RhsIterator = kron_view_iterator<RhsMatrix, RowMajor>;
215 template <typename F>
216 static Index outerSize(const F& f) {
217 return RowMajor ? f.rows() : f.cols();
218 }
219
220 const RhsMatrix* m_rhs;
221 Index m_outerR, m_innerR;
222 LhsIterator m_itL;
223 RhsIterator m_itR;
224 bool m_nonEmptyR;
225};
226
231template <typename LhsMatrix, typename RhsMatrix, bool RowMajor>
232class kron_view_iterator<KroneckerSum<LhsMatrix, RhsMatrix>, RowMajor, kKronSumFactor> {
233 public:
234 using Factor = KroneckerSum<LhsMatrix, RhsMatrix>;
235 using Scalar = typename Factor::Scalar;
236 kron_view_iterator(const Factor& f, Index outer)
237 : m_n2(f.rhs().rows()),
238 m_outerL(outer / m_n2),
239 m_outerR(outer % m_n2),
240 m_itL(f.lhs(), m_outerL),
241 m_itR(f.rhs(), m_outerR) {}
242 explicit operator bool() const { return bool(m_itL) || bool(m_itR); }
243 kron_view_iterator& operator++() {
244 const Index current = index();
245 if (indexL() == current) ++m_itL;
246 if (indexR() == current) ++m_itR;
247 return *this;
248 }
249 Index index() const { return numext::mini(indexL(), indexR()); }
250 // The values of the materialization (A (x) I) + (I (x) B), signed zeros
251 // included: a + b on the diagonal, a + 0 and 0 + b off it.
252 Scalar value() const {
253 const Index l = indexL(), r = indexR();
254 if (l == r) return m_itL.value() + m_itR.value();
255 return l < r ? m_itL.value() + Scalar(0) : Scalar(0) + m_itR.value();
256 }
257
258 private:
259 using LhsIterator = kron_view_iterator<LhsMatrix, RowMajor>;
260 using RhsIterator = kron_view_iterator<RhsMatrix, RowMajor>;
261 Index indexL() const { return m_itL ? m_itL.index() * m_n2 + m_outerR : NumTraits<Index>::highest(); }
262 Index indexR() const { return m_itR ? m_outerL * m_n2 + m_itR.index() : NumTraits<Index>::highest(); }
263
264 Index m_n2, m_outerL, m_outerR;
265 LhsIterator m_itL;
266 RhsIterator m_itR;
267};
268
271template <typename Factor, int Kind = kron_factor_kind<Factor>()>
272struct kron_view_nonzeros {
273 static Index run(const Factor& f) { return kron_factor_ops<Factor>::innerNonZeros(f, false).sum(); }
274};
275template <typename LhsMatrix, typename RhsMatrix>
276struct kron_view_nonzeros<KroneckerOperator<LhsMatrix, RhsMatrix>, kKronKroneckerFactor> {
277 static Index run(const KroneckerOperator<LhsMatrix, RhsMatrix>& f) {
278 return kron_view_nonzeros<LhsMatrix>::run(f.lhs()) * kron_view_nonzeros<RhsMatrix>::run(f.rhs());
279 }
280};
281template <typename LhsMatrix, typename RhsMatrix>
282struct kron_view_nonzeros<KroneckerSum<LhsMatrix, RhsMatrix>, kKronSumFactor> {
283 static Index run(const KroneckerSum<LhsMatrix, RhsMatrix>& f) {
284 return kron_view_nonzeros<LhsMatrix>::run(f.lhs()) * f.rhs().rows() +
285 f.lhs().rows() * kron_view_nonzeros<RhsMatrix>::run(f.rhs());
286 }
287};
288
289} // namespace internal
290
341template <typename OperatorType, int Options>
342class KroneckerSparseView : public SparseMatrixBase<KroneckerSparseView<OperatorType, Options>> {
343 using ViewFactor = internal::kron_view_factor<OperatorType, Options>;
344
345 public:
347 EIGEN_SPARSE_PUBLIC_INTERFACE(KroneckerSparseView)
348 using ViewOperator = typename ViewFactor::type;
349 static constexpr bool RowMajorView = (unsigned(Options) & RowMajorBit) != 0;
350
351 explicit KroneckerSparseView(const OperatorType& op) : m_op(ViewFactor::convert(op)) {}
352
353 Index rows() const { return m_op.rows(); }
354 Index cols() const { return m_op.cols(); }
355
358 const ViewOperator& nestedOperator() const { return m_op; }
359
361 class InnerIterator {
362 public:
363 InnerIterator(const KroneckerSparseView& view, Index outer) : m_it(view.m_op, outer), m_outer(outer) {}
364 InnerIterator& operator++() {
365 ++m_it;
366 return *this;
367 }
368 operator bool() const { return bool(m_it); }
369 Index index() const { return m_it.index(); }
370 Index outer() const { return m_outer; }
371 Index row() const { return RowMajorView ? m_outer : index(); }
372 Index col() const { return RowMajorView ? index() : m_outer; }
373 Scalar value() const { return m_it.value(); }
374
375 private:
376 internal::kron_view_iterator<ViewOperator, RowMajorView> m_it;
377 Index m_outer;
378 };
379
380 private:
381 ViewOperator m_op;
382};
383
384namespace internal {
385
386template <typename OperatorType, int Options>
387struct evaluator<KroneckerSparseView<OperatorType, Options>>
388 : evaluator_base<KroneckerSparseView<OperatorType, Options>> {
390 using Scalar = typename XprType::Scalar;
391 static constexpr int CoeffReadCost = NumTraits<Scalar>::MulCost;
392 static constexpr unsigned int Flags = traits<XprType>::Flags;
393
394 class InnerIterator : public XprType::InnerIterator {
395 public:
396 InnerIterator(const evaluator& eval, Index outer) : XprType::InnerIterator(eval.m_view, outer) {}
397 };
398
399 explicit evaluator(const XprType& xpr) : m_view(xpr) {}
400 Index nonZerosEstimate() const {
401 return kron_view_nonzeros<typename XprType::ViewOperator>::run(m_view.nestedOperator());
402 }
403
404 const XprType& m_view;
405};
406
407} // namespace internal
408
409} // namespace Eigen
410
411#endif // EIGEN_STRUCTURED_KRONECKER_SPARSE_VIEW_H
A KroneckerOperator or KroneckerSum as a lazy sparse expression.
Definition KroneckerSparseView.h:342
const ViewOperator & nestedOperator() const
Definition KroneckerSparseView.h:358
constexpr unsigned int RowMajorBit
Namespace containing all symbols from the Eigen library.