Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseDenseProduct.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_SPARSEDENSEPRODUCT_H
12#define EIGEN_SPARSEDENSEPRODUCT_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21template <typename Lhs, typename Rhs, typename Dest, typename Alpha>
22void ordered_sparse_dense_add(Dest& dst, const Lhs& lhs, const Rhs& rhs, const Alpha& alpha, true_type) {
23 if (numext::is_exactly_zero(alpha)) return;
24 evaluator<Lhs> lhsEval(lhs);
25 evaluator<Rhs> rhsEval(rhs);
26 for (Index outer = 0; outer < lhs.outerSize(); ++outer)
27 for (typename evaluator<Lhs>::InnerIterator it(lhsEval, outer); it; ++it)
28 for (Index col = 0; col < rhs.cols(); ++col)
29 dst.coeffRef(it.row(), col) += alpha * (it.value() * rhsEval.coeff(it.col(), col));
30}
31
32template <typename Lhs, typename Rhs, typename Dest, typename Alpha>
33void ordered_sparse_dense_add(Dest& dst, const Lhs& lhs, const Rhs& rhs, const Alpha& alpha, false_type) {
34 if (numext::is_exactly_zero(alpha)) return;
35 evaluator<Lhs> lhsEval(lhs);
36 evaluator<Rhs> rhsEval(rhs);
37 for (Index outer = 0; outer < rhs.outerSize(); ++outer)
38 for (typename evaluator<Rhs>::InnerIterator it(rhsEval, outer); it; ++it)
39 for (Index row = 0; row < lhs.rows(); ++row)
40 dst.coeffRef(row, it.col()) += alpha * (lhsEval.coeff(row, it.row()) * it.value());
41}
42
43template <>
44struct product_promote_storage_type<Sparse, Dense, OuterProduct> {
45 using ret = Sparse;
46};
47template <>
48struct product_promote_storage_type<Dense, Sparse, OuterProduct> {
49 using ret = Sparse;
50};
51
52// Type trait to detect if a sparse type supports direct compressed storage access
53// (i.e., has valuePtr(), innerIndexPtr(), outerIndexPtr(), isCompressed()).
54// All types deriving from SparseCompressedBase provide these methods.
55template <typename T>
56struct has_compressed_storage : std::is_base_of<SparseCompressedBase<T>, T> {};
57
58template <typename SparseLhsType, typename DenseRhsType, typename DenseResType, typename AlphaType,
59 int LhsStorageOrder = ((SparseLhsType::Flags & RowMajorBit) == RowMajorBit) ? RowMajor : ColMajor,
60 bool ColPerCol = ((DenseRhsType::Flags & RowMajorBit) == 0) || DenseRhsType::ColsAtCompileTime == 1>
61struct sparse_time_dense_product_impl;
62
63// RowMajor, single column (ColPerCol=true): CSR SpMV
64template <typename SparseLhsType, typename DenseRhsType, typename DenseResType>
65struct sparse_time_dense_product_impl<SparseLhsType, DenseRhsType, DenseResType, typename DenseResType::Scalar,
66 RowMajor, true> {
67 using Lhs = internal::remove_all_t<SparseLhsType>;
68 using Res = internal::remove_all_t<DenseResType>;
69 using LhsInnerIterator = typename evaluator<Lhs>::InnerIterator;
70 using LhsEval = evaluator<Lhs>;
71 using ResScalar = typename Res::Scalar;
72
73 static void run(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
74 const typename Res::Scalar& alpha) {
75 LhsEval lhsEval(lhs);
76 Index n = lhs.outerSize();
77
78 // Nothing to add for an empty inner dimension. A Block without rows has data() == nullptr but a non-zero
79 // outerStride(), so the column pointer below would be a non-zero offset to a null pointer.
80 if (rhs.rows() == 0) return;
81 for (Index c = 0; c < rhs.cols(); ++c) {
82 runCol(lhsEval, lhs, rhs, res, alpha, n, c, bool_constant<has_compressed_storage<Lhs>::value>());
83 }
84 }
85
86 // Direct pointer path: works for both compressed and non-compressed storage.
87 static void runCol(const LhsEval& /*lhsEval*/, const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
88 const ResScalar& alpha, Index n, Index c, std::true_type /* has_compressed_storage */) {
89 runColImpl(lhs, rhs, res, alpha, n, c, bool_constant<bool(DenseRhsType::Flags & DirectAccessBit)>());
90 }
91
92 template <typename RhsT>
93 static void runColImpl(const SparseLhsType& lhs, const RhsT& rhs, DenseResType& res, const ResScalar& alpha, Index n,
94 Index c, std::true_type) {
95 const Lhs& mat = lhs;
96 const auto* vals = mat.valuePtr();
97 const auto* inds = mat.innerIndexPtr();
98 // Sparse vectors don't store outer indices.
99 const auto* outer = mat.outerIndexPtr();
100 const auto* innerNnz = mat.innerNonZeroPtr();
101 // The fast rhs pointer path requires unit inner stride (common case: VectorXd, contiguous matrix column).
102 if (rhs.innerStride() == 1) {
103 const auto* x = rhs.data() + c * rhs.outerStride();
104#ifdef EIGEN_HAS_OPENMP
105 Index threads = Eigen::nbThreads();
106 if (threads > 1 && mat.nonZeros() > 20000) {
107#pragma omp parallel for schedule(dynamic, (n + threads * 4 - 1) / (threads * 4)) num_threads(threads)
108 for (Index i = 0; i < n; ++i) {
109 Index k = outer ? outer[i] : 0;
110 const Index end = innerNnz ? (outer ? outer[i] : 0) + innerNnz[i] : (outer ? outer[i + 1] : mat.nonZeros());
111 ResScalar sum0(0), sum1(0);
112 for (; k < end; ++k) {
113 sum0 += vals[k] * x[inds[k]];
114 ++k;
115 if (k < end) {
116 sum1 += vals[k] * x[inds[k]];
117 }
118 }
119 res.coeffRef(i, c) += alpha * (sum0 + sum1);
120 }
121 } else
122#endif
123 {
124 for (Index i = 0; i < n; ++i) {
125 Index k = outer ? outer[i] : 0;
126 const Index end = innerNnz ? (outer ? outer[i] : 0) + innerNnz[i] : (outer ? outer[i + 1] : mat.nonZeros());
127 // Two independent accumulators to break the dependency chain
128 ResScalar sum0(0), sum1(0);
129 for (; k < end; ++k) {
130 sum0 += vals[k] * x[inds[k]];
131 ++k;
132 if (k < end) {
133 sum1 += vals[k] * x[inds[k]];
134 }
135 }
136 res.coeffRef(i, c) += alpha * (sum0 + sum1);
137 }
138 }
139 } else {
140 runColImpl(lhs, rhs, res, alpha, n, c, std::false_type());
141 }
142 }
143
144 // Use fall-back path without direct access to rhs.
145 template <typename RhsT>
146 static void runColImpl(const SparseLhsType& lhs, const RhsT& rhs, DenseResType& res, const ResScalar& alpha, Index n,
147 Index c, std::false_type) {
148 const Lhs& mat = lhs;
149 const auto* vals = mat.valuePtr();
150 const auto* inds = mat.innerIndexPtr();
151 const auto* outer = mat.outerIndexPtr();
152 const auto* innerNnz = mat.innerNonZeroPtr();
153 // Non-unit rhs stride (or no direct access): use direct pointers for sparse side, coeff() for rhs
154 for (Index i = 0; i < n; ++i) {
155 Index k = outer ? outer[i] : 0;
156 const Index end = innerNnz ? (outer ? outer[i] : 0) + innerNnz[i] : (outer ? outer[i + 1] : mat.nonZeros());
157 ResScalar sum0(0), sum1(0);
158 for (; k < end; ++k) {
159 sum0 += vals[k] * rhs.coeff(inds[k], c);
160 ++k;
161 if (k < end) {
162 sum1 += vals[k] * rhs.coeff(inds[k], c);
163 }
164 }
165 res.coeffRef(i, c) += alpha * (sum0 + sum1);
166 }
167 }
168
169 // Iterator fallback path
170 static void runCol(const LhsEval& lhsEval, const SparseLhsType& /*lhs*/, const DenseRhsType& rhs, DenseResType& res,
171 const ResScalar& alpha, Index n, Index c, std::false_type /* has_compressed_storage */) {
172#ifdef EIGEN_HAS_OPENMP
173 Index threads = Eigen::nbThreads();
174 if (threads > 1 && lhsEval.nonZerosEstimate() > 20000) {
175#pragma omp parallel for schedule(dynamic, (n + threads * 4 - 1) / (threads * 4)) num_threads(threads)
176 for (Index i = 0; i < n; ++i) processRow(lhsEval, rhs, res, alpha, i, c);
177 } else
178#endif
179 {
180 for (Index i = 0; i < n; ++i) processRow(lhsEval, rhs, res, alpha, i, c);
181 }
182 }
183
184 static void processRow(const LhsEval& lhsEval, const DenseRhsType& rhs, DenseResType& res, const ResScalar& alpha,
185 Index i, Index col) {
186 ResScalar tmp_a(0);
187 ResScalar tmp_b(0);
188 for (LhsInnerIterator it(lhsEval, i); it; ++it) {
189 tmp_a += it.value() * rhs.coeff(it.index(), col);
190 ++it;
191 if (it) {
192 tmp_b += it.value() * rhs.coeff(it.index(), col);
193 }
194 }
195 res.coeffRef(i, col) += alpha * (tmp_a + tmp_b);
196 }
197};
198
199// ColMajor, single column (ColPerCol=true): CSC SpMV
200template <typename SparseLhsType, typename DenseRhsType, typename DenseResType, typename AlphaType>
201struct sparse_time_dense_product_impl<SparseLhsType, DenseRhsType, DenseResType, AlphaType, ColMajor, true> {
202 using Lhs = internal::remove_all_t<SparseLhsType>;
203 using Rhs = internal::remove_all_t<DenseRhsType>;
204 using Res = internal::remove_all_t<DenseResType>;
205 using LhsEval = evaluator<Lhs>;
206 using LhsInnerIterator = typename LhsEval::InnerIterator;
207
208 static void run(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res, const AlphaType& alpha) {
209 runImpl(lhs, rhs, res, alpha, bool_constant<has_compressed_storage<Lhs>::value>());
210 }
211
212 // Direct pointer path: works for both compressed and non-compressed storage.
213 static void runImpl(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res, const AlphaType& alpha,
214 std::true_type /* has_compressed_storage */) {
215 using LhsScalar = typename Lhs::Scalar;
216 using StorageIndex = typename Lhs::StorageIndex;
217 const Lhs& mat = lhs;
218 const LhsScalar* vals = mat.valuePtr();
219 const StorageIndex* inds = mat.innerIndexPtr();
220 // Sparse vectors don't store outer indices.
221 const auto* outer = mat.outerIndexPtr();
222 const auto* innerNnz = mat.innerNonZeroPtr();
223 // An empty result (a Block without rows has data() == nullptr but a non-zero outerStride()) receives nothing.
224 if (res.rows() == 0 || rhs.cols() == 0) return;
225 // The fast result pointer path requires contiguous ColMajor result layout.
226 // Transpose<ColMajor> reports innerStride()==1 but is actually RowMajor, so check both.
227 EIGEN_IF_CONSTEXPR (!(Res::Flags & RowMajorBit)) {
228 if (res.innerStride() == 1) {
229 const Index n = lhs.outerSize();
230 // The threaded scatter+reduce path relies on a thread_local scratch buffer for
231 // host-thread safety (see below), so it is only available where thread_local is
232 // usable; under EIGEN_AVOID_THREAD_LOCAL fall through to the serial scatter.
233#if defined(EIGEN_HAS_OPENMP) && !defined(EIGEN_AVOID_THREAD_LOCAL)
234 using ResScalar = typename Res::Scalar;
235 const Index m = res.rows();
236 const Index threads = Eigen::nbThreads();
237 // Per-thread scratch + reduction: the natural per-column partition would
238 // race on the output (writes to y[inds[k]] are scattered across rows),
239 // so each thread accumulates into its own m-sized output buffer and the
240 // results are summed at the end. Activated above the same 20000-nnz
241 // threshold as the RowMajor kernel, plus a second gate on per-thread
242 // scratch size: `threads * m` scalars are touched by the reduction,
243 // and on tall / very-sparse matrices that can dwarf the SpMV cost --
244 // require avg nnz per row >= threads so the reduction can't dominate.
245 // `outer` is null for SparseVector lhs; the nnz-balanced partition needs
246 // the outer-index array, so fall back to the serial scatter below.
247 if (outer && threads > 1 && mat.nonZeros() > 20000 && mat.nonZeros() >= Index(threads) * m) {
248 // Per-calling-thread persistent scratch (per template instantiation).
249 // Grows monotonically; reused across calls. The buffer is left at
250 // all-zeros after each call by folding the zero-out into the reduction
251 // step, which avoids a separate init pass on every SpMV. `thread_local`
252 // is required: two unrelated host threads concurrently calling
253 // y = A*x would otherwise race on this static buffer (and a reallocating
254 // grow on one would dangle the other's scratch_ptr).
255 thread_local static std::vector<ResScalar> scratch_buf;
256 const std::size_t need = static_cast<std::size_t>(threads) * static_cast<std::size_t>(m);
257 if (scratch_buf.size() < need) scratch_buf.assign(need, ResScalar(0));
258 ResScalar* scratch_ptr = scratch_buf.data();
259 // nnz-balanced column partition: each thread t owns the contiguous
260 // column range [part[t], part[t+1]). Deterministic mapping of j to
261 // thread (required for bit-reproducible reduction below) AND
262 // nnz-balanced load (dynamic scheduling would balance but break
263 // determinism; static round-robin would be deterministic but
264 // imbalanced on skewed matrices).
265 std::vector<Index> part(static_cast<std::size_t>(threads) + 1);
266 part[threads] = n;
267 part[0] = 0;
268 // Targets are monotonically increasing in t, so each lower_bound starts
269 // from the previous result; total work is O(T + log n) rather than
270 // T * log n.
271 const StorageIndex* const part_last = outer + n + 1;
272 const StorageIndex* part_lo = outer;
273 for (Index t = 1; t < threads; ++t) {
274 const Index target = (t * mat.nonZeros()) / threads;
275 part_lo = std::lower_bound(part_lo, part_last, StorageIndex(target));
276 part[t] = part_lo - outer;
277 }
278 for (Index c = 0; c < rhs.cols(); ++c) {
279 typename Res::Scalar* y = res.data() + c * res.outerStride();
280#pragma omp parallel for schedule(static, 1) num_threads(threads)
281 for (Index t = 0; t < threads; ++t) {
282 ResScalar* yt = scratch_ptr + t * m;
283 const Index j_lo = part[t], j_hi = part[t + 1];
284 for (Index j = j_lo; j < j_hi; ++j) {
285 typename ScalarBinaryOpTraits<AlphaType, typename Rhs::Scalar>::ReturnType rhs_j(alpha *
286 rhs.coeff(j, c));
287 const Index start = outer ? outer[j] : 0;
288 const Index end = innerNnz ? start + innerNnz[j] : (outer ? outer[j + 1] : mat.nonZeros());
289 Index k = start;
290 for (; k + 3 < end; k += 4) {
291 yt[inds[k]] += vals[k] * rhs_j;
292 yt[inds[k + 1]] += vals[k + 1] * rhs_j;
293 yt[inds[k + 2]] += vals[k + 2] * rhs_j;
294 yt[inds[k + 3]] += vals[k + 3] * rhs_j;
295 }
296 for (; k < end; ++k) yt[inds[k]] += vals[k] * rhs_j;
297 }
298 }
299 // Reduce per-thread buffers into y AND zero them, so the next call
300 // doesn't have to re-init. Process rows in cache-resident blocks: the
301 // natural [t*m+i] scratch layout makes the cross-thread read for a
302 // single row a stride-m gather (one cache line per thread, ~threads*m
303 // bytes apart, unvectorizable). Blocking lets each thread's stripe be
304 // swept as a unit-stride, vectorizable stream into a small per-block
305 // accumulator. Each thread owns a contiguous range of row blocks
306 // (static schedule) so the zero stores stay independent, and the
307 // accumulator is summed in the exact t = 0..threads-1 order, keeping
308 // the result bit-identical to the scalar reduction it replaces.
309 constexpr Index kReduceBlock = 512;
310#pragma omp parallel for schedule(static) num_threads(threads)
311 for (Index i0 = 0; i0 < m; i0 += kReduceBlock) {
312 const Index i1 = numext::mini(i0 + kReduceBlock, m);
313 const Index len = i1 - i0;
314 EIGEN_ALIGN_MAX ResScalar acc[kReduceBlock];
315 for (Index ii = 0; ii < len; ++ii) acc[ii] = ResScalar(0);
316 for (Index t = 0; t < threads; ++t) {
317 ResScalar* row = scratch_ptr + t * m + i0;
318 for (Index ii = 0; ii < len; ++ii) {
319 acc[ii] += row[ii];
320 row[ii] = ResScalar(0);
321 }
322 }
323 for (Index ii = 0; ii < len; ++ii) y[i0 + ii] += acc[ii];
324 }
325 }
326 } else
327#endif
328 {
329 for (Index c = 0; c < rhs.cols(); ++c) {
330 typename Res::Scalar* y = res.data() + c * res.outerStride();
331 for (Index j = 0; j < n; ++j) {
332 typename ScalarBinaryOpTraits<AlphaType, typename Rhs::Scalar>::ReturnType rhs_j(alpha * rhs.coeff(j, c));
333 const Index start = outer ? outer[j] : 0;
334 const Index end = innerNnz ? start + innerNnz[j] : (outer ? outer[j + 1] : mat.nonZeros());
335 Index k = start;
336 // 4-way unrolled scatter-add (no SIMD: writes are scattered)
337 for (; k + 3 < end; k += 4) {
338 y[inds[k]] += vals[k] * rhs_j;
339 y[inds[k + 1]] += vals[k + 1] * rhs_j;
340 y[inds[k + 2]] += vals[k + 2] * rhs_j;
341 y[inds[k + 3]] += vals[k + 3] * rhs_j;
342 }
343 for (; k < end; ++k) y[inds[k]] += vals[k] * rhs_j;
344 }
345 }
346 }
347 return;
348 }
349 }
350 // Non-unit result stride: use coeffRef() for result access
351 for (Index c = 0; c < rhs.cols(); ++c) {
352 for (Index j = 0; j < lhs.outerSize(); ++j) {
353 typename ScalarBinaryOpTraits<AlphaType, typename Rhs::Scalar>::ReturnType rhs_j(alpha * rhs.coeff(j, c));
354 const Index start = outer ? outer[j] : 0;
355 const Index end = innerNnz ? start + innerNnz[j] : (outer ? outer[j + 1] : mat.nonZeros());
356 for (Index k = start; k < end; ++k) res.coeffRef(inds[k], c) += vals[k] * rhs_j;
357 }
358 }
359 }
360
361 // Iterator-based fallback
362 static void runImpl(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res, const AlphaType& alpha,
363 std::false_type /* has_compressed_storage */) {
364 LhsEval lhsEval(lhs);
365 for (Index c = 0; c < rhs.cols(); ++c) {
366 for (Index j = 0; j < lhs.outerSize(); ++j) {
367 typename ScalarBinaryOpTraits<AlphaType, typename Rhs::Scalar>::ReturnType rhs_j(alpha * rhs.coeff(j, c));
368 for (LhsInnerIterator it(lhsEval, j); it; ++it) res.coeffRef(it.index(), c) += it.value() * rhs_j;
369 }
370 }
371 }
372};
373
374// RowMajor, multiple columns (ColPerCol=false): sparse * dense_matrix
375template <typename SparseLhsType, typename DenseRhsType, typename DenseResType>
376struct sparse_time_dense_product_impl<SparseLhsType, DenseRhsType, DenseResType, typename DenseResType::Scalar,
377 RowMajor, false> {
378 using Lhs = internal::remove_all_t<SparseLhsType>;
379 using Res = internal::remove_all_t<DenseResType>;
380 using LhsEval = evaluator<Lhs>;
381 using LhsInnerIterator = typename LhsEval::InnerIterator;
382
383 static constexpr bool IsCompressedLhs = has_compressed_storage<Lhs>::value;
384
385 static void run(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
386 const typename Res::Scalar& alpha) {
387 Index n = lhs.rows();
388 LhsEval lhsEval(lhs);
389
390#ifdef EIGEN_HAS_OPENMP
391 Index threads = Eigen::nbThreads();
392 // This 20000 threshold has been found experimentally on 2D and 3D Poisson problems.
393 // It basically represents the minimal amount of work to be done to be worth it.
394 if (threads > 1 && lhsEval.nonZerosEstimate() * rhs.cols() > 20000) {
395#pragma omp parallel for schedule(dynamic, (n + threads * 4 - 1) / (threads * 4)) num_threads(threads)
396 for (Index i = 0; i < n; ++i) processRow(lhsEval, lhs, rhs, res, alpha, i, bool_constant<IsCompressedLhs>());
397 } else
398#endif
399 {
400 for (Index i = 0; i < n; ++i) processRow(lhsEval, lhs, rhs, res, alpha, i, bool_constant<IsCompressedLhs>());
401 }
402 }
403
404 // Direct pointer path: works for both compressed and non-compressed storage.
405 static void processRow(const LhsEval& /*lhsEval*/, const SparseLhsType& lhs, const DenseRhsType& rhs, Res& res,
406 const typename Res::Scalar& alpha, Index i, std::true_type /* has_compressed_storage */) {
407 using LhsScalar = typename Lhs::Scalar;
408 using StorageIndex = typename Lhs::StorageIndex;
409 const Lhs& mat = lhs;
410 const LhsScalar* vals = mat.valuePtr();
411 const StorageIndex* inds = mat.innerIndexPtr();
412 // Sparse vectors don't store outer indices.
413 const Index start = mat.outerIndexPtr() ? mat.outerIndexPtr()[i] : 0;
414 const auto* innerNnz = mat.innerNonZeroPtr();
415 const Index end =
416 innerNnz ? start + innerNnz[i] : (mat.outerIndexPtr() ? mat.outerIndexPtr()[i + 1] : mat.nonZeros());
417 typename Res::RowXpr res_i(res.row(i));
418 for (Index k = start; k < end; ++k) res_i.matrix() += (alpha * vals[k]) * rhs.row(inds[k]);
419 }
420
421 static void processRow(const LhsEval& lhsEval, const SparseLhsType& /*lhs*/, const DenseRhsType& rhs, Res& res,
422 const typename Res::Scalar& alpha, Index i, std::false_type /* has_compressed_storage */) {
423 typename Res::RowXpr res_i(res.row(i));
424 for (LhsInnerIterator it(lhsEval, i); it; ++it) res_i.matrix() += (alpha * it.value()) * rhs.row(it.index());
425 }
426};
427
428// ColMajor, multiple columns (ColPerCol=false): sparse * dense_matrix
429template <typename SparseLhsType, typename DenseRhsType, typename DenseResType>
430struct sparse_time_dense_product_impl<SparseLhsType, DenseRhsType, DenseResType, typename DenseResType::Scalar,
431 ColMajor, false> {
432 using Lhs = internal::remove_all_t<SparseLhsType>;
433 using Rhs = internal::remove_all_t<DenseRhsType>;
434 using Res = internal::remove_all_t<DenseResType>;
435 using LhsInnerIterator = typename evaluator<Lhs>::InnerIterator;
436
437 static void run(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
438 const typename Res::Scalar& alpha) {
439 runImpl(lhs, rhs, res, alpha, bool_constant<has_compressed_storage<Lhs>::value>());
440 }
441
442 // Direct pointer path: works for both compressed and non-compressed storage.
443 static void runImpl(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
444 const typename Res::Scalar& alpha, std::true_type /* has_compressed_storage */) {
445 using LhsScalar = typename Lhs::Scalar;
446 using StorageIndex = typename Lhs::StorageIndex;
447 const Lhs& mat = lhs;
448 const LhsScalar* vals = mat.valuePtr();
449 const StorageIndex* inds = mat.innerIndexPtr();
450 // Sparse vectors don't store outer indices.
451 const auto* outer = mat.outerIndexPtr();
452 const auto* innerNnz = mat.innerNonZeroPtr();
453 for (Index j = 0; j < lhs.outerSize(); ++j) {
454 typename Rhs::ConstRowXpr rhs_j(rhs.row(j));
455 const Index start = outer ? outer[j] : 0;
456 const Index end = innerNnz ? start + innerNnz[j] : (outer ? outer[j + 1] : mat.nonZeros());
457 for (Index k = start; k < end; ++k) res.row(inds[k]).matrix() += (alpha * vals[k]) * rhs_j;
458 }
459 }
460
461 static void runImpl(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
462 const typename Res::Scalar& alpha, std::false_type /* has_compressed_storage */) {
463 evaluator<Lhs> lhsEval(lhs);
464 for (Index j = 0; j < lhs.outerSize(); ++j) {
465 typename Rhs::ConstRowXpr rhs_j(rhs.row(j));
466 for (LhsInnerIterator it(lhsEval, j); it; ++it) res.row(it.index()).matrix() += (alpha * it.value()) * rhs_j;
467 }
468 }
469};
470
471template <typename SparseLhsType, typename DenseRhsType, typename DenseResType, typename AlphaType>
472inline void sparse_time_dense_product(const SparseLhsType& lhs, const DenseRhsType& rhs, DenseResType& res,
473 const AlphaType& alpha) {
474 sparse_time_dense_product_impl<SparseLhsType, DenseRhsType, DenseResType, AlphaType>::run(lhs, rhs, res, alpha);
475}
476
477} // end namespace internal
478
479namespace internal {
480
481template <typename Lhs, typename Rhs, int ProductType>
482struct generic_product_impl<Lhs, Rhs, SparseShape, DenseShape, ProductType>
483 : generic_product_impl_base<Lhs, Rhs, generic_product_impl<Lhs, Rhs, SparseShape, DenseShape, ProductType> > {
484 using Scalar = typename Product<Lhs, Rhs>::Scalar;
485
486 template <typename Dest>
487 static void scaleAndAddTo(Dest& dst, const Lhs& lhs, const Rhs& rhs, const Scalar& alpha) {
488 using LhsNested = typename nested_eval<Lhs, ((Rhs::Flags & RowMajorBit) == 0) ? 1 : Rhs::ColsAtCompileTime>::type;
489 using RhsNested = typename nested_eval<Rhs, ((Lhs::Flags & RowMajorBit) == 0) ? 1 : Dynamic>::type;
490 LhsNested lhsNested(lhs);
491 RhsNested rhsNested(rhs);
492 run(dst, lhsNested, rhsNested, alpha,
493 functor_is_commutative<scalar_product_op<typename Lhs::Scalar, typename Rhs::Scalar>>());
494 }
495
496 private:
497 template <typename Dest, typename NestedLhs, typename NestedRhs>
498 static void run(Dest& dst, const NestedLhs& lhs, const NestedRhs& rhs, const Scalar& alpha, true_type) {
499 internal::sparse_time_dense_product(lhs, rhs, dst, alpha);
500 }
501
502 template <typename Dest, typename NestedLhs, typename NestedRhs>
503 static void run(Dest& dst, const NestedLhs& lhs, const NestedRhs& rhs, const Scalar& alpha, false_type) {
504 ordered_sparse_dense_add(dst, lhs, rhs, alpha, true_type());
505 }
506};
507
508template <typename Lhs, typename Rhs, int ProductType>
509struct generic_product_impl<Lhs, Rhs, SparseTriangularShape, DenseShape, ProductType>
510 : generic_product_impl<Lhs, Rhs, SparseShape, DenseShape, ProductType> {};
511
512template <typename Lhs, typename Rhs, int ProductType>
513struct generic_product_impl<Lhs, Rhs, DenseShape, SparseShape, ProductType>
514 : generic_product_impl_base<Lhs, Rhs, generic_product_impl<Lhs, Rhs, DenseShape, SparseShape, ProductType> > {
515 using Scalar = typename Product<Lhs, Rhs>::Scalar;
516
517 template <typename Dst>
518 static void scaleAndAddTo(Dst& dst, const Lhs& lhs, const Rhs& rhs, const Scalar& alpha) {
519 using LhsNested = typename nested_eval<Lhs, ((Rhs::Flags & RowMajorBit) == 0) ? Dynamic : 1>::type;
520 using RhsNested =
521 typename nested_eval<Rhs, ((Lhs::Flags & RowMajorBit) == RowMajorBit) ? 1 : Lhs::RowsAtCompileTime>::type;
522 LhsNested lhsNested(lhs);
523 RhsNested rhsNested(rhs);
524
525 run(dst, lhsNested, rhsNested, alpha,
526 functor_is_commutative<scalar_product_op<typename Lhs::Scalar, typename Rhs::Scalar>>());
527 }
528
529 private:
530 template <typename Dst, typename NestedLhs, typename NestedRhs>
531 static void run(Dst& dst, const NestedLhs& lhs, const NestedRhs& rhs, const Scalar& alpha, true_type) {
532 // Transposition reverses coefficient multiplication, so this needs commutative scalars.
533 Transpose<Dst> dstT(dst);
534 internal::sparse_time_dense_product(rhs.transpose(), lhs.transpose(), dstT, alpha);
535 }
536
537 template <typename Dst, typename NestedLhs, typename NestedRhs>
538 static void run(Dst& dst, const NestedLhs& lhs, const NestedRhs& rhs, const Scalar& alpha, false_type) {
539 ordered_sparse_dense_add(dst, lhs, rhs, alpha, false_type());
540 }
541};
542
543template <typename Lhs, typename Rhs, int ProductType>
544struct generic_product_impl<Lhs, Rhs, DenseShape, SparseTriangularShape, ProductType>
545 : generic_product_impl<Lhs, Rhs, DenseShape, SparseShape, ProductType> {};
546
547template <typename LhsT, typename RhsT, bool NeedToTranspose>
548struct sparse_dense_outer_product_evaluator {
549 protected:
550 using Lhs1 = std::conditional_t<NeedToTranspose, RhsT, LhsT>;
551 using ActualRhs = std::conditional_t<NeedToTranspose, LhsT, RhsT>;
552 using ProdXprType = Product<LhsT, RhsT, DefaultProduct>;
553
554 // if the actual left-hand side is a dense vector,
555 // then build a sparse-view so that we can seamlessly iterate over it.
556 using ActualLhs = std::conditional_t<std::is_same<typename internal::traits<Lhs1>::StorageKind, Sparse>::value, Lhs1,
557 SparseView<Lhs1>>;
558 using LhsArg = std::conditional_t<std::is_same<typename internal::traits<Lhs1>::StorageKind, Sparse>::value,
559 const Lhs1&, SparseView<Lhs1>>;
560
561 using LhsEval = evaluator<ActualLhs>;
562 using RhsEval = evaluator<ActualRhs>;
563 using LhsIterator = typename evaluator<ActualLhs>::InnerIterator;
564 using Scalar = typename ProdXprType::Scalar;
565 using FactorScalar = typename ActualRhs::Scalar;
566 using ProductOp = sparse_scalar_product_op<typename ActualLhs::Scalar, FactorScalar, NeedToTranspose>;
567
568 public:
569 enum { Flags = NeedToTranspose ? RowMajorBit : 0, CoeffReadCost = HugeCost };
570
571 class InnerIterator : public LhsIterator {
572 public:
573 InnerIterator(const sparse_dense_outer_product_evaluator& xprEval, Index outer)
574 : LhsIterator(xprEval.m_lhsXprImpl, 0),
575 m_outer(outer),
576 m_empty(false),
577 m_factor(get(xprEval.m_rhsXprImpl, outer, typename internal::traits<ActualRhs>::StorageKind())) {}
578
579 EIGEN_STRONG_INLINE Index outer() const { return m_outer; }
580 EIGEN_STRONG_INLINE Index row() const { return NeedToTranspose ? m_outer : LhsIterator::index(); }
581 EIGEN_STRONG_INLINE Index col() const { return NeedToTranspose ? LhsIterator::index() : m_outer; }
582
583 EIGEN_STRONG_INLINE Scalar value() const { return ProductOp()(LhsIterator::value(), m_factor); }
584 EIGEN_STRONG_INLINE operator bool() const { return LhsIterator::operator bool() && (!m_empty); }
585
586 protected:
587 FactorScalar get(const RhsEval& rhs, Index outer, Dense = Dense()) const { return rhs.coeff(outer); }
588
589 FactorScalar get(const RhsEval& rhs, Index outer, Sparse = Sparse()) {
590 typename RhsEval::InnerIterator it(rhs, outer);
591 if (it && it.index() == 0 && it.value() != FactorScalar(0)) return it.value();
592 m_empty = true;
593 return FactorScalar(0);
594 }
595
596 Index m_outer;
597 bool m_empty;
598 FactorScalar m_factor;
599 };
600
601 sparse_dense_outer_product_evaluator(const Lhs1& lhs, const ActualRhs& rhs)
602 : m_lhs(lhs), m_lhsXprImpl(m_lhs), m_rhsXprImpl(rhs) {
603 EIGEN_INTERNAL_CHECK_COST_VALUE(CoeffReadCost);
604 }
605
606 // transpose case
607 sparse_dense_outer_product_evaluator(const ActualRhs& rhs, const Lhs1& lhs)
608 : m_lhs(lhs), m_lhsXprImpl(m_lhs), m_rhsXprImpl(rhs) {
609 EIGEN_INTERNAL_CHECK_COST_VALUE(CoeffReadCost);
610 }
611
612 protected:
613 const LhsArg m_lhs;
614 evaluator<ActualLhs> m_lhsXprImpl;
615 evaluator<ActualRhs> m_rhsXprImpl;
616};
617
618// sparse * dense outer product
619template <typename Lhs, typename Rhs>
620struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, OuterProduct, SparseShape, DenseShape>
621 : sparse_dense_outer_product_evaluator<Lhs, Rhs, Lhs::IsRowMajor> {
622 using Base = sparse_dense_outer_product_evaluator<Lhs, Rhs, Lhs::IsRowMajor>;
623
624 using XprType = Product<Lhs, Rhs>;
625 using PlainObject = typename XprType::PlainObject;
626
627 explicit product_evaluator(const XprType& xpr) : Base(xpr.lhs(), xpr.rhs()) {}
628};
629
630template <typename Lhs, typename Rhs>
631struct product_evaluator<Product<Lhs, Rhs, DefaultProduct>, OuterProduct, DenseShape, SparseShape>
632 : sparse_dense_outer_product_evaluator<Lhs, Rhs, Rhs::IsRowMajor> {
633 using Base = sparse_dense_outer_product_evaluator<Lhs, Rhs, Rhs::IsRowMajor>;
634
635 using XprType = Product<Lhs, Rhs>;
636 using PlainObject = typename XprType::PlainObject;
637
638 explicit product_evaluator(const XprType& xpr) : Base(xpr.lhs(), xpr.rhs()) {}
639};
640
641} // end namespace internal
642
643} // end namespace Eigen
644
645#endif // EIGEN_SPARSEDENSEPRODUCT_H
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int DirectAccessBit
Definition Constants.h:160
constexpr unsigned int RowMajorBit
Definition Constants.h:71