Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparseSparseProductWithPruning.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-2014 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_SPARSESPARSEPRODUCTWITHPRUNING_H
12#define EIGEN_SPARSESPARSEPRODUCTWITHPRUNING_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21// perform a pseudo in-place sparse * sparse product assuming all matrices are col major
22template <typename Lhs, typename Rhs, typename ResultType, bool ReverseProduct = false>
23static void sparse_sparse_product_with_pruning_impl(const Lhs& lhs, const Rhs& rhs, ResultType& res,
24 const typename ResultType::RealScalar& tolerance) {
25 using LhsScalar = typename remove_all_t<Lhs>::Scalar;
26 using RhsScalar = typename remove_all_t<Rhs>::Scalar;
27 using ResScalar = typename remove_all_t<ResultType>::Scalar;
28 const sparse_scalar_product_op<LhsScalar, RhsScalar, ReverseProduct> product;
29 using StorageIndex = typename remove_all_t<Lhs>::StorageIndex;
30
31 // make sure to call innerSize/outerSize since we fake the storage order.
32 Index rows = lhs.innerSize();
33 Index cols = rhs.outerSize();
34 eigen_assert(lhs.outerSize() == rhs.innerSize());
35
36 // allocate a temporary buffer
37 AmbiVector<ResScalar, StorageIndex> tempVector(rows);
38
39 // mimics a resizeByInnerOuter:
40 EIGEN_IF_CONSTEXPR (ResultType::IsRowMajor) {
41 res.resize(cols, rows);
42 } else {
43 res.resize(rows, cols);
44 }
45
46 evaluator<Lhs> lhsEval(lhs);
47 evaluator<Rhs> rhsEval(rhs);
48
49 // estimate the number of non zero entries
50 // given a rhs column containing Y non zeros, we assume that the respective Y columns
51 // of the lhs differs in average of one non zeros, thus the number of non zeros for
52 // the product of a rhs column with the lhs is X+Y where X is the average number of non zero
53 // per column of the lhs.
54 // Therefore, we have nnz(lhs*rhs) = nnz(lhs) + nnz(rhs)
55 Index estimated_nnz_prod = lhsEval.nonZerosEstimate() + rhsEval.nonZerosEstimate();
56
57 res.reserve(estimated_nnz_prod);
58 double ratioColRes = double(estimated_nnz_prod) / (double(lhs.rows()) * double(rhs.cols()));
59 for (Index j = 0; j < cols; ++j) {
60 // FIXME: compute a more accurate per-column nnz ratio for res.
61 tempVector.init(ratioColRes);
62 tempVector.setZero();
63 for (typename evaluator<Rhs>::InnerIterator rhsIt(rhsEval, j); rhsIt; ++rhsIt) {
64 // FIXME: rewrite as tmp += rhsIt.value() * lhs.col(rhsIt.index()).
65 tempVector.restart();
66 RhsScalar x = rhsIt.value();
67 for (typename evaluator<Lhs>::InnerIterator lhsIt(lhsEval, rhsIt.index()); lhsIt; ++lhsIt) {
68 product.accumulate(tempVector.coeffRef(lhsIt.index()), lhsIt.value(), x);
69 }
70 }
71 res.startVec(j);
72 for (typename AmbiVector<ResScalar, StorageIndex>::Iterator it(tempVector, tolerance); it; ++it)
73 res.insertBackByOuterInner(j, it.index()) = it.value();
74 }
75 res.finalize();
76}
77
78template <typename Lhs, typename Rhs, typename ResultType, int LhsStorageOrder = traits<Lhs>::Flags & RowMajorBit,
79 int RhsStorageOrder = traits<Rhs>::Flags & RowMajorBit,
80 int ResStorageOrder = traits<ResultType>::Flags & RowMajorBit>
81struct sparse_sparse_product_with_pruning_selector;
82
83template <typename Lhs, typename Rhs, typename ResultType>
84struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, ColMajor, ColMajor, ColMajor> {
85 using RealScalar = typename ResultType::RealScalar;
86
87 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
88 remove_all_t<ResultType> res_{res.rows(), res.cols()};
89 internal::sparse_sparse_product_with_pruning_impl<Lhs, Rhs, ResultType>(lhs, rhs, res_, tolerance);
90 res.swap(res_);
91 }
92};
93
94template <typename Lhs, typename Rhs, typename ResultType>
95struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, ColMajor, ColMajor, RowMajor> {
96 using RealScalar = typename ResultType::RealScalar;
97 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
98 // we need a col-major matrix to hold the result
99 using SparseTemporaryType = SparseMatrix<typename ResultType::Scalar, ColMajor, typename ResultType::StorageIndex>;
100 SparseTemporaryType res_{res.rows(), res.cols()};
101 internal::sparse_sparse_product_with_pruning_impl<Lhs, Rhs, SparseTemporaryType>(lhs, rhs, res_, tolerance);
102 res = res_;
103 }
104};
105
106template <typename Lhs, typename Rhs, typename ResultType>
107struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, RowMajor, RowMajor, RowMajor> {
108 using RealScalar = typename ResultType::RealScalar;
109 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
110 // let's transpose the product to get a column x column product
111 remove_all_t<ResultType> res_{res.rows(), res.cols()};
112 internal::sparse_sparse_product_with_pruning_impl<Rhs, Lhs, ResultType, true>(rhs, lhs, res_, tolerance);
113 res.swap(res_);
114 }
115};
116
117template <typename Lhs, typename Rhs, typename ResultType>
118struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, RowMajor, RowMajor, ColMajor> {
119 using RealScalar = typename ResultType::RealScalar;
120 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
121 using ColMajorMatrixLhs = SparseMatrix<typename Lhs::Scalar, ColMajor, typename Lhs::StorageIndex>;
122 using ColMajorMatrixRhs = SparseMatrix<typename Rhs::Scalar, ColMajor, typename Lhs::StorageIndex>;
123 ColMajorMatrixLhs colLhs(lhs);
124 ColMajorMatrixRhs colRhs(rhs);
125 internal::sparse_sparse_product_with_pruning_impl<ColMajorMatrixLhs, ColMajorMatrixRhs, ResultType>(colLhs, colRhs,
126 res, tolerance);
127 }
128};
129
130template <typename Lhs, typename Rhs, typename ResultType>
131struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, ColMajor, RowMajor, RowMajor> {
132 using RealScalar = typename ResultType::RealScalar;
133 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
134 using RowMajorMatrixLhs = SparseMatrix<typename Lhs::Scalar, RowMajor, typename Lhs::StorageIndex>;
135 RowMajorMatrixLhs rowLhs(lhs);
136 sparse_sparse_product_with_pruning_selector<RowMajorMatrixLhs, Rhs, ResultType, RowMajor, RowMajor>::run(
137 rowLhs, rhs, res, tolerance);
138 }
139};
140
141template <typename Lhs, typename Rhs, typename ResultType>
142struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, RowMajor, ColMajor, RowMajor> {
143 using RealScalar = typename ResultType::RealScalar;
144 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
145 using RowMajorMatrixRhs = SparseMatrix<typename Rhs::Scalar, RowMajor, typename Lhs::StorageIndex>;
146 RowMajorMatrixRhs rowRhs(rhs);
147 sparse_sparse_product_with_pruning_selector<Lhs, RowMajorMatrixRhs, ResultType, RowMajor, RowMajor, RowMajor>::run(
148 lhs, rowRhs, res, tolerance);
149 }
150};
151
152template <typename Lhs, typename Rhs, typename ResultType>
153struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, ColMajor, RowMajor, ColMajor> {
154 using RealScalar = typename ResultType::RealScalar;
155 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
156 using ColMajorMatrixRhs = SparseMatrix<typename Rhs::Scalar, ColMajor, typename Lhs::StorageIndex>;
157 ColMajorMatrixRhs colRhs(rhs);
158 internal::sparse_sparse_product_with_pruning_impl<Lhs, ColMajorMatrixRhs, ResultType>(lhs, colRhs, res, tolerance);
159 }
160};
161
162template <typename Lhs, typename Rhs, typename ResultType>
163struct sparse_sparse_product_with_pruning_selector<Lhs, Rhs, ResultType, RowMajor, ColMajor, ColMajor> {
164 using RealScalar = typename ResultType::RealScalar;
165 static void run(const Lhs& lhs, const Rhs& rhs, ResultType& res, const RealScalar& tolerance) {
166 using ColMajorMatrixLhs = SparseMatrix<typename Lhs::Scalar, ColMajor, typename Lhs::StorageIndex>;
167 ColMajorMatrixLhs colLhs(lhs);
168 internal::sparse_sparse_product_with_pruning_impl<ColMajorMatrixLhs, Rhs, ResultType>(colLhs, rhs, res, tolerance);
169 }
170};
171
172} // end namespace internal
173
174} // end namespace Eigen
175
176#endif // EIGEN_SPARSESPARSEPRODUCTWITHPRUNING_H
Definition AmbiVector.h:312
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int RowMajorBit
Definition Constants.h:71