Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ConservativeSparseSparseProduct.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-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_CONSERVATIVESPARSESPARSEPRODUCT_H
12#define EIGEN_CONSERVATIVESPARSESPARSEPRODUCT_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21template <typename Lhs, typename Rhs, typename ResultType, bool ReverseProduct = false>
22static void conservative_sparse_sparse_product_impl(const Lhs& lhs, const Rhs& rhs, ResultType& res,
23 bool sortedInsertion = false) {
24 using LhsScalar = typename remove_all_t<Lhs>::Scalar;
25 using RhsScalar = typename remove_all_t<Rhs>::Scalar;
26 using ResScalar = typename remove_all_t<ResultType>::Scalar;
27 const sparse_scalar_product_op<LhsScalar, RhsScalar, ReverseProduct> product;
28
29 // make sure to call innerSize/outerSize since we fake the storage order.
30 Index rows = lhs.innerSize();
31 Index cols = rhs.outerSize();
32 eigen_assert(lhs.outerSize() == rhs.innerSize());
33
34 ei_declare_aligned_stack_constructed_variable(bool, mask, rows, 0);
35 ei_declare_aligned_stack_constructed_variable(ResScalar, values, rows, 0);
36 ei_declare_aligned_stack_constructed_variable(Index, indices, rows, 0);
37
38 std::fill_n(mask, rows, false);
39
40 evaluator<Lhs> lhsEval(lhs);
41 evaluator<Rhs> rhsEval(rhs);
42
43 // estimate the number of non zero entries
44 // given a rhs column containing Y non zeros, we assume that the respective Y columns
45 // of the lhs differs in average of one non zeros, thus the number of non zeros for
46 // the product of a rhs column with the lhs is X+Y where X is the average number of non zero
47 // per column of the lhs.
48 // Therefore, we have nnz(lhs*rhs) = nnz(lhs) + nnz(rhs)
49 Index estimated_nnz_prod = lhsEval.nonZerosEstimate() + rhsEval.nonZerosEstimate();
50
51 res.setZero();
52 res.reserve(Index(estimated_nnz_prod));
53 // we compute each column of the result, one after the other
54 for (Index j = 0; j < cols; ++j) {
55 res.startVec(j);
56 Index nnz = 0;
57 for (typename evaluator<Rhs>::InnerIterator rhsIt(rhsEval, j); rhsIt; ++rhsIt) {
58 RhsScalar y = rhsIt.value();
59 Index k = rhsIt.index();
60 for (typename evaluator<Lhs>::InnerIterator lhsIt(lhsEval, k); lhsIt; ++lhsIt) {
61 Index i = lhsIt.index();
62 LhsScalar x = lhsIt.value();
63 if (!mask[i]) {
64 mask[i] = true;
65 values[i] = product(x, y);
66 indices[nnz] = i;
67 ++nnz;
68 } else
69 product.accumulate(values[i], x, y);
70 }
71 }
72 if (!sortedInsertion) {
73 // unordered insertion
74 for (Index k = 0; k < nnz; ++k) {
75 Index i = indices[k];
76 res.insertBackByOuterInnerUnordered(j, i) = values[i];
77 mask[i] = false;
78 }
79 } else {
80 // alternative ordered insertion code:
81 const Index t200 = rows / 11; // 11 == (log2(200)*1.39)
82 const Index t = (rows * 100) / 139;
83
84 // if the result is sparse enough => use a quick sort
85 // otherwise => loop through the entire vector
86 // In order to avoid to perform an expensive log2 when the
87 // result is clearly very sparse we use a linear bound up to 200.
88 if ((nnz < 200 && nnz < t200) || nnz * numext::log2(int(nnz)) < t) {
89 if (nnz > 1) std::sort(indices, indices + nnz);
90 for (Index k = 0; k < nnz; ++k) {
91 Index i = indices[k];
92 res.insertBackByOuterInner(j, i) = values[i];
93 mask[i] = false;
94 }
95 } else {
96 // dense path
97 for (Index i = 0; i < rows; ++i) {
98 if (mask[i]) {
99 mask[i] = false;
100 res.insertBackByOuterInner(j, i) = values[i];
101 }
102 }
103 }
104 }
105 }
106 res.finalize();
107}
108
109// Helper template to generate new sparse matrix types
110template <class Source, int Order>
111using WithStorageOrder = SparseMatrix<typename Source::Scalar, Order, typename Source::StorageIndex>;
112
113template <typename Lhs, typename Rhs, typename ResultType,
114 int LhsStorageOrder = (traits<Lhs>::Flags & RowMajorBit) ? RowMajor : ColMajor,
115 int RhsStorageOrder = (traits<Rhs>::Flags & RowMajorBit) ? RowMajor : ColMajor,
116 int ResStorageOrder = (traits<ResultType>::Flags & RowMajorBit) ? RowMajor : ColMajor>
117struct conservative_sparse_sparse_product_selector;
118
119template <typename Lhs, typename Rhs, typename ResultType>
120struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, ColMajor, ColMajor, ColMajor> {
121 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
122 using RowMajorMatrix = WithStorageOrder<ResultType, RowMajor>;
123 using ColMajorMatrixAux = WithStorageOrder<ResultType, ColMajor>;
124
125 // If the result is tall and thin (in the extreme case a column vector)
126 // then it is faster to sort the coefficients inplace instead of transposing twice.
127 // The dimension-only test here ignores nnz / per-column density; a proper
128 // cost model using estimated_nnz_prod would pick the right path more often.
129 if (lhs.rows() > rhs.cols()) {
130 using ColMajorMatrix = typename sparse_eval<ColMajorMatrixAux, ResultType::RowsAtCompileTime,
131 ResultType::ColsAtCompileTime, ColMajorMatrixAux::Flags>::type;
132 ColMajorMatrix resCol(lhs.rows(), rhs.cols());
133 // perform sorted insertion
134 internal::conservative_sparse_sparse_product_impl<Lhs, Rhs, ColMajorMatrix>(lhs, rhs, resCol, true);
135 res = resCol.markAsRValue();
136 } else {
137 ColMajorMatrixAux resCol(lhs.rows(), rhs.cols());
138 // resort to transpose to sort the entries
139 internal::conservative_sparse_sparse_product_impl<Lhs, Rhs, ColMajorMatrixAux>(lhs, rhs, resCol, false);
140 RowMajorMatrix resRow(resCol);
141 res = resRow.markAsRValue();
142 }
143 }
144};
145
146template <typename Lhs, typename Rhs, typename ResultType>
147struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, RowMajor, ColMajor, ColMajor> {
148 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
149 using RowMajorRhs = WithStorageOrder<Rhs, RowMajor>;
150 using RowMajorRes = WithStorageOrder<ResultType, RowMajor>;
151 RowMajorRhs rhsRow = rhs;
152 RowMajorRes resRow(lhs.rows(), rhs.cols());
153 internal::conservative_sparse_sparse_product_impl<RowMajorRhs, Lhs, RowMajorRes, true>(rhsRow, lhs, resRow);
154 res = resRow;
155 }
156};
157
158template <typename Lhs, typename Rhs, typename ResultType>
159struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, ColMajor, RowMajor, ColMajor> {
160 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
161 using RowMajorLhs = WithStorageOrder<Lhs, RowMajor>;
162 using RowMajorRes = WithStorageOrder<ResultType, RowMajor>;
163 RowMajorLhs lhsRow = lhs;
164 RowMajorRes resRow(lhs.rows(), rhs.cols());
165 internal::conservative_sparse_sparse_product_impl<Rhs, RowMajorLhs, RowMajorRes, true>(rhs, lhsRow, resRow);
166 res = resRow;
167 }
168};
169
170template <typename Lhs, typename Rhs, typename ResultType>
171struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, RowMajor, RowMajor, ColMajor> {
172 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
173 using RowMajorRes = WithStorageOrder<ResultType, RowMajor>;
174 RowMajorRes resRow(lhs.rows(), rhs.cols());
175 internal::conservative_sparse_sparse_product_impl<Rhs, Lhs, RowMajorRes, true>(rhs, lhs, resRow);
176 res = resRow;
177 }
178};
179
180template <typename Lhs, typename Rhs, typename ResultType>
181struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, ColMajor, ColMajor, RowMajor> {
182 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
183 using ColMajorRes = WithStorageOrder<ResultType, ColMajor>;
184 ColMajorRes resCol(lhs.rows(), rhs.cols());
185 internal::conservative_sparse_sparse_product_impl<Lhs, Rhs, ColMajorRes>(lhs, rhs, resCol);
186 res = resCol;
187 }
188};
189
190template <typename Lhs, typename Rhs, typename ResultType>
191struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, RowMajor, ColMajor, RowMajor> {
192 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
193 using ColMajorLhs = WithStorageOrder<Lhs, ColMajor>;
194 using ColMajorRes = WithStorageOrder<ResultType, ColMajor>;
195 ColMajorLhs lhsCol = lhs;
196 ColMajorRes resCol(lhs.rows(), rhs.cols());
197 internal::conservative_sparse_sparse_product_impl<ColMajorLhs, Rhs, ColMajorRes>(lhsCol, rhs, resCol);
198 res = resCol;
199 }
200};
201
202template <typename Lhs, typename Rhs, typename ResultType>
203struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, ColMajor, RowMajor, RowMajor> {
204 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
205 using ColMajorRhs = WithStorageOrder<Rhs, ColMajor>;
206 using ColMajorRes = WithStorageOrder<ResultType, ColMajor>;
207 ColMajorRhs rhsCol = rhs;
208 ColMajorRes resCol(lhs.rows(), rhs.cols());
209 internal::conservative_sparse_sparse_product_impl<Lhs, ColMajorRhs, ColMajorRes>(lhs, rhsCol, resCol);
210 res = resCol;
211 }
212};
213
214template <typename Lhs, typename Rhs, typename ResultType>
215struct conservative_sparse_sparse_product_selector<Lhs, Rhs, ResultType, RowMajor, RowMajor, RowMajor> {
216 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
217 using ColMajorRes = WithStorageOrder<ResultType, ColMajor>;
218 using RowMajorRes = WithStorageOrder<ResultType, RowMajor>;
219 RowMajorRes resRow(lhs.rows(), rhs.cols());
220 internal::conservative_sparse_sparse_product_impl<Rhs, Lhs, RowMajorRes, true>(rhs, lhs, resRow);
221 // sort the non zeros:
222 ColMajorRes resCol(resRow);
223 res = resCol;
224 }
225};
226
227template <typename Lhs, typename Rhs, typename ResultType, bool ReverseProduct = false>
228static void sparse_sparse_to_dense_product_impl(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
229 using LhsScalar = typename remove_all_t<Lhs>::Scalar;
230 using RhsScalar = typename remove_all_t<Rhs>::Scalar;
231 const sparse_scalar_product_op<LhsScalar, RhsScalar, ReverseProduct> product;
232 Index cols = rhs.outerSize();
233 eigen_assert(lhs.outerSize() == rhs.innerSize());
234
235 evaluator<Lhs> lhsEval(lhs);
236 evaluator<Rhs> rhsEval(rhs);
237
238 for (Index j = 0; j < cols; ++j) {
239 for (typename evaluator<Rhs>::InnerIterator rhsIt(rhsEval, j); rhsIt; ++rhsIt) {
240 RhsScalar y = rhsIt.value();
241 Index k = rhsIt.index();
242 for (typename evaluator<Lhs>::InnerIterator lhsIt(lhsEval, k); lhsIt; ++lhsIt) {
243 Index i = lhsIt.index();
244 LhsScalar x = lhsIt.value();
245 product.accumulate(res.coeffRef(i, j), x, y);
246 }
247 }
248 }
249}
250
251} // end namespace internal
252
253namespace internal {
254
255template <typename Lhs, typename Rhs, typename ResultType,
256 int LhsStorageOrder = (traits<Lhs>::Flags & RowMajorBit) ? RowMajor : ColMajor,
257 int RhsStorageOrder = (traits<Rhs>::Flags & RowMajorBit) ? RowMajor : ColMajor>
258struct sparse_sparse_to_dense_product_selector;
259
260template <typename Lhs, typename Rhs, typename ResultType>
261struct sparse_sparse_to_dense_product_selector<Lhs, Rhs, ResultType, ColMajor, ColMajor> {
262 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
263 internal::sparse_sparse_to_dense_product_impl<Lhs, Rhs, ResultType>(lhs, rhs, res);
264 }
265};
266
267template <typename Lhs, typename Rhs, typename ResultType>
268struct sparse_sparse_to_dense_product_selector<Lhs, Rhs, ResultType, RowMajor, ColMajor> {
269 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
270 using ColMajorLhs = WithStorageOrder<Lhs, ColMajor>;
271 ColMajorLhs lhsCol(lhs);
272 internal::sparse_sparse_to_dense_product_impl<ColMajorLhs, Rhs, ResultType>(lhsCol, rhs, res);
273 }
274};
275
276template <typename Lhs, typename Rhs, typename ResultType>
277struct sparse_sparse_to_dense_product_selector<Lhs, Rhs, ResultType, ColMajor, RowMajor> {
278 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
279 using ColMajorRhs = WithStorageOrder<Rhs, ColMajor>;
280 ColMajorRhs rhsCol(rhs);
281 internal::sparse_sparse_to_dense_product_impl<Lhs, ColMajorRhs, ResultType>(lhs, rhsCol, res);
282 }
283};
284
285template <typename Lhs, typename Rhs, typename ResultType>
286struct sparse_sparse_to_dense_product_selector<Lhs, Rhs, ResultType, RowMajor, RowMajor> {
287 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res) {
288 Transpose<ResultType> trRes(res);
289 internal::sparse_sparse_to_dense_product_impl<Rhs, Lhs, Transpose<ResultType>, true>(rhs, lhs, trRes);
290 }
291};
292
293} // end namespace internal
294
295} // end namespace Eigen
296
297#endif // EIGEN_CONSERVATIVESPARSESPARSEPRODUCT_H
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int RowMajorBit
Definition Constants.h:71