Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseDiagonalProduct.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009-2015 Gael Guennebaud <gael.guennebaud@inria.fr>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_SPARSE_DIAGONAL_PRODUCT_H
12#define EIGEN_SPARSE_DIAGONAL_PRODUCT_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19// The product of a diagonal matrix with a sparse matrix can be easily
20// implemented using expression template.
21// We have to consider two very different cases:
22// 1 - diag * row-major sparse
23// => each inner vector <=> scalar * sparse vector product
24// => so we can reuse CwiseUnaryOp::InnerIterator
25// 2 - diag * col-major sparse
26// => each inner vector <=> densevector * sparse vector cwise product
27// => again, we can reuse specialization of CwiseBinaryOp::InnerIterator
28// for that particular case
29// The two other cases are symmetric.
30
31namespace internal {
32
33enum { SDP_AsScalarProduct, SDP_AsCwiseProduct };
34
35template <typename SparseXprType, typename DiagonalCoeffType, int SDP_Tag, bool DiagonalOnLeft = true>
36struct sparse_diagonal_product_evaluator;
37
38template <typename Lhs, typename Rhs, int ProductTag>
39struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, DiagonalShape, SparseShape>
40 : public sparse_diagonal_product_evaluator<Rhs, typename Lhs::DiagonalVectorType,
41 Rhs::Flags & RowMajorBit ? SDP_AsScalarProduct : SDP_AsCwiseProduct,
42 true> {
43 using XprType = Product<Lhs, Rhs, DefaultProduct>;
44 enum {
45 CoeffReadCost = HugeCost,
46 Flags = Rhs::Flags & RowMajorBit,
47 Alignment = 0
48 }; // FIXME: compute proper CoeffReadCost and propagate Flags.
49
50 using Base =
51 sparse_diagonal_product_evaluator<Rhs, typename Lhs::DiagonalVectorType,
52 Rhs::Flags & RowMajorBit ? SDP_AsScalarProduct : SDP_AsCwiseProduct, true>;
53 explicit product_evaluator(const XprType& xpr) : Base(xpr.rhs(), xpr.lhs().diagonal()) {}
54};
55
56template <typename Lhs, typename Rhs, int ProductTag>
57struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, SparseShape, DiagonalShape>
58 : public sparse_diagonal_product_evaluator<Lhs, Transpose<const typename Rhs::DiagonalVectorType>,
59 Lhs::Flags & RowMajorBit ? SDP_AsCwiseProduct : SDP_AsScalarProduct,
60 false> {
61 using XprType = Product<Lhs, Rhs, DefaultProduct>;
62 enum {
63 CoeffReadCost = HugeCost,
64 Flags = Lhs::Flags & RowMajorBit,
65 Alignment = 0
66 }; // FIXME: compute proper CoeffReadCost and propagate Flags.
67
68 using Base =
69 sparse_diagonal_product_evaluator<Lhs, Transpose<const typename Rhs::DiagonalVectorType>,
70 Lhs::Flags & RowMajorBit ? SDP_AsCwiseProduct : SDP_AsScalarProduct, false>;
71 explicit product_evaluator(const XprType& xpr) : Base(xpr.lhs(), xpr.rhs().diagonal().transpose()) {}
72};
73
74// SparseSelfAdjointView synthesizes mirrored entries; build the diagonal-scaled
75// full result directly instead of first materializing an unscaled PlainObject.
76template <int Mode, int ProductOrder, typename SelfAdjointViewType, typename DiagonalType, typename Dest>
77struct sparse_selfadjoint_diagonal_product_impl {
78 using MatrixType = typename SelfAdjointViewType::MatrixTypeNested_;
79 using MatrixEvaluator = evaluator<MatrixType>;
80 using MatrixIterator = typename MatrixEvaluator::InnerIterator;
81 using StorageIndex = typename Dest::StorageIndex;
82 using VectorI = Matrix<StorageIndex, Dynamic, 1>;
83 enum { IsFullMode = Mode == int(Upper | Lower), IsLowerMode = (Mode & int(Lower)) == int(Lower) };
84
85 static void run(Dest& dest, const SelfAdjointViewType& selfadjoint, const DiagonalType& diagonal) {
86 MatrixEvaluator matrixEval(selfadjoint.matrix());
87 const Index size = selfadjoint.rows();
88 VectorI count(size);
89 count.setZero();
90 dest.resize(size, size);
91
92 for (Index outer = 0; outer < selfadjoint.matrix().outerSize(); ++outer) {
93 for (MatrixIterator it(matrixEval, outer); it; ++it) countEntry(count, it.row(), it.col());
94 }
95
96 Index nnz = count.sum();
97 dest.resizeNonZeros(nnz);
98 dest.outerIndexPtr()[0] = 0;
99 for (Index outer = 0; outer < size; ++outer)
100 dest.outerIndexPtr()[outer + 1] = dest.outerIndexPtr()[outer] + count[outer];
101 for (Index outer = 0; outer < size; ++outer) count[outer] = dest.outerIndexPtr()[outer];
102
103 for (Index outer = 0; outer < selfadjoint.matrix().outerSize(); ++outer) {
104 for (MatrixIterator it(matrixEval, outer); it; ++it) {
105 const Index row = it.row();
106 const Index col = it.col();
107 if (isStored(row, col)) {
108 insertEntry(dest, count, diagonal, row, col, it.value());
109 }
110 if (mirrorsStoredEntry(row, col)) {
111 insertEntry(dest, count, diagonal, col, row, numext::conj(it.value()));
112 }
113 }
114 }
115 }
116
117 private:
118 static EIGEN_STRONG_INLINE bool isStored(Index row, Index col) {
119 return IsFullMode || row == col || (IsLowerMode ? row > col : row < col);
120 }
121
122 static EIGEN_STRONG_INLINE bool mirrorsStoredEntry(Index row, Index col) {
123 return !IsFullMode && row != col && (IsLowerMode ? row > col : row < col);
124 }
125
126 static void countEntry(VectorI& count, Index row, Index col) {
127 if (isStored(row, col)) {
128 ++count[outerIndex(row, col)];
129 }
130 if (mirrorsStoredEntry(row, col)) {
131 ++count[outerIndex(col, row)];
132 }
133 }
134
135 static EIGEN_STRONG_INLINE StorageIndex outerIndex(Index row, Index col) {
136 return internal::convert_index<StorageIndex>(Dest::IsRowMajor ? row : col);
137 }
138
139 static EIGEN_STRONG_INLINE StorageIndex innerIndex(Index row, Index col) {
140 return internal::convert_index<StorageIndex>(Dest::IsRowMajor ? col : row);
141 }
142
143 template <typename Coeff>
144 static void insertEntry(Dest& dest, VectorI& count, const DiagonalType& diagonal, Index row, Index col,
145 const Coeff& coeff) {
146 const StorageIndex outer = outerIndex(row, col);
147 const Index k = count[outer]++;
148 dest.innerIndexPtr()[k] = innerIndex(row, col);
149 EIGEN_IF_CONSTEXPR (ProductOrder == OnTheLeft) {
150 dest.valuePtr()[k] = diagonal.coeff(row) * coeff;
151 } else {
152 dest.valuePtr()[k] = coeff * diagonal.coeff(col);
153 }
154 }
155};
156
157template <typename Lhs, typename Rhs>
158struct materialized_left_sparse_product_evaluator_base
159 : public evaluator<typename Product<Lhs, typename Rhs::PlainObject, DefaultProduct>::PlainObject> {
160 using XprType = Product<Lhs, Rhs, DefaultProduct>;
161 using PlainObject = typename XprType::PlainObject;
162 using Base = evaluator<PlainObject>;
163
164 explicit materialized_left_sparse_product_evaluator_base(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
165 internal::construct_at<Base>(this, m_result);
166 sparse_selfadjoint_diagonal_product_impl<Rhs::Mode, OnTheLeft, Rhs, typename Lhs::DiagonalVectorType,
167 PlainObject>::run(m_result, xpr.rhs(), xpr.lhs().diagonal());
168 }
169
170 protected:
171 PlainObject m_result;
172};
173
174template <typename Lhs, typename Rhs>
175struct materialized_right_sparse_product_evaluator_base
176 : public evaluator<typename Product<typename Lhs::PlainObject, Rhs, DefaultProduct>::PlainObject> {
177 using XprType = Product<Lhs, Rhs, DefaultProduct>;
178 using PlainObject = typename XprType::PlainObject;
179 using Base = evaluator<PlainObject>;
180
181 explicit materialized_right_sparse_product_evaluator_base(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
182 internal::construct_at<Base>(this, m_result);
183 sparse_selfadjoint_diagonal_product_impl<Lhs::Mode, OnTheRight, Lhs, typename Rhs::DiagonalVectorType,
184 PlainObject>::run(m_result, xpr.lhs(), xpr.rhs().diagonal());
185 }
186
187 protected:
188 PlainObject m_result;
189};
190
191template <typename Lhs, typename Rhs, int ProductTag>
192struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, DiagonalShape, SparseTriangularShape>
193 : product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, DiagonalShape, SparseShape> {
194 using Base = product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, DiagonalShape, SparseShape>;
195 using Base::Base;
196};
197
198template <typename Lhs, typename Rhs, int ProductTag>
199struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, DiagonalShape, SparseSelfAdjointShape>
200 : materialized_left_sparse_product_evaluator_base<Lhs, Rhs> {
201 using materialized_left_sparse_product_evaluator_base<Lhs, Rhs>::materialized_left_sparse_product_evaluator_base;
202};
203
204template <typename Lhs, typename Rhs, int ProductTag>
205struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, SparseTriangularShape, DiagonalShape>
206 : product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, SparseShape, DiagonalShape> {
207 using Base = product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, SparseShape, DiagonalShape>;
208 using Base::Base;
209};
210
211template <typename Lhs, typename Rhs, int ProductTag>
212struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, ProductTag, SparseSelfAdjointShape, DiagonalShape>
213 : materialized_right_sparse_product_evaluator_base<Lhs, Rhs> {
214 using materialized_right_sparse_product_evaluator_base<Lhs, Rhs>::materialized_right_sparse_product_evaluator_base;
215};
216
217template <typename SparseXprType, typename DiagonalCoeffType, bool DiagonalOnLeft>
218struct sparse_diagonal_product_evaluator<SparseXprType, DiagonalCoeffType, SDP_AsScalarProduct, DiagonalOnLeft> {
219 protected:
220 using SparseXprInnerIterator = typename evaluator<SparseXprType>::InnerIterator;
221 using SparseScalar = typename SparseXprType::Scalar;
222 using DiagonalScalar = typename DiagonalCoeffType::Scalar;
223 using Scalar = typename std::conditional_t<DiagonalOnLeft, ScalarBinaryOpTraits<DiagonalScalar, SparseScalar>,
224 ScalarBinaryOpTraits<SparseScalar, DiagonalScalar>>::ReturnType;
225 using ProductOp = sparse_scalar_product_op<DiagonalScalar, SparseScalar, !DiagonalOnLeft>;
226
227 public:
228 class InnerIterator : public SparseXprInnerIterator {
229 public:
230 InnerIterator(const sparse_diagonal_product_evaluator& xprEval, Index outer)
231 : SparseXprInnerIterator(xprEval.m_sparseXprImpl, outer), m_coeff(xprEval.m_diagCoeffImpl.coeff(outer)) {}
232
233 EIGEN_STRONG_INLINE Scalar value() const { return ProductOp()(m_coeff, SparseXprInnerIterator::value()); }
234
235 protected:
236 typename DiagonalCoeffType::Scalar m_coeff;
237 };
238
239 sparse_diagonal_product_evaluator(const SparseXprType& sparseXpr, const DiagonalCoeffType& diagCoeff)
240 : m_sparseXprImpl(sparseXpr), m_diagCoeffImpl(diagCoeff) {}
241
242 Index nonZerosEstimate() const { return m_sparseXprImpl.nonZerosEstimate(); }
243
244 protected:
245 evaluator<SparseXprType> m_sparseXprImpl;
246 evaluator<DiagonalCoeffType> m_diagCoeffImpl;
247};
248
249template <typename SparseXprType, typename DiagCoeffType, bool DiagonalOnLeft>
250struct sparse_diagonal_product_evaluator<SparseXprType, DiagCoeffType, SDP_AsCwiseProduct, DiagonalOnLeft> {
251 using SparseScalar = typename SparseXprType::Scalar;
252 using DiagonalScalar = typename DiagCoeffType::Scalar;
253 using Scalar = typename std::conditional_t<DiagonalOnLeft, ScalarBinaryOpTraits<DiagonalScalar, SparseScalar>,
254 ScalarBinaryOpTraits<SparseScalar, DiagonalScalar>>::ReturnType;
255 using ProductOp = sparse_scalar_product_op<SparseScalar, DiagonalScalar, DiagonalOnLeft>;
256 using StorageIndex = typename SparseXprType::StorageIndex;
257
258 using DiagCoeffNested =
259 typename nested_eval<DiagCoeffType, SparseXprType::IsRowMajor ? SparseXprType::RowsAtCompileTime
260 : SparseXprType::ColsAtCompileTime>::type;
261
262 class InnerIterator {
263 using SparseXprIter = typename evaluator<SparseXprType>::InnerIterator;
264
265 public:
266 InnerIterator(const sparse_diagonal_product_evaluator& xprEval, Index outer)
267 : m_sparseIter(xprEval.m_sparseXprEval, outer), m_diagCoeffNested(xprEval.m_diagCoeffNested) {}
268
269 EIGEN_STRONG_INLINE Scalar value() const {
270 return ProductOp()(m_sparseIter.value(), m_diagCoeffNested.coeff(index()));
271 }
272 inline StorageIndex index() const { return m_sparseIter.index(); }
273 inline Index outer() const { return m_sparseIter.outer(); }
274 inline Index col() const { return SparseXprType::IsRowMajor ? m_sparseIter.index() : m_sparseIter.outer(); }
275 inline Index row() const { return SparseXprType::IsRowMajor ? m_sparseIter.outer() : m_sparseIter.index(); }
276
277 EIGEN_STRONG_INLINE InnerIterator& operator++() {
278 ++m_sparseIter;
279 return *this;
280 }
281 inline operator bool() const { return m_sparseIter; }
282
283 protected:
284 SparseXprIter m_sparseIter;
285 DiagCoeffNested m_diagCoeffNested;
286 };
287
288 sparse_diagonal_product_evaluator(const SparseXprType& sparseXpr, const DiagCoeffType& diagCoeff)
289 : m_sparseXprEval(sparseXpr), m_diagCoeffNested(diagCoeff) {}
290
291 Index nonZerosEstimate() const { return m_sparseXprEval.nonZerosEstimate(); }
292
293 protected:
294 evaluator<SparseXprType> m_sparseXprEval;
295 DiagCoeffNested m_diagCoeffNested;
296};
297
298} // end namespace internal
299
300} // end namespace Eigen
301
302#endif // EIGEN_SPARSE_DIAGONAL_PRODUCT_H
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ OnTheLeft
Definition Constants.h:332
@ OnTheRight
Definition Constants.h:334
constexpr unsigned int RowMajorBit
Definition Constants.h:71