Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SparsePermutation.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2012 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_PERMUTATION_H
12#define EIGEN_SPARSE_PERMUTATION_H
13
14// This file implements sparse * permutation products
15
16// IWYU pragma: private
17#include "./InternalHeaderCheck.h"
18
19namespace Eigen {
20
21namespace internal {
22
23template <typename ExpressionType, typename PlainObjectType,
24 bool NeedEval = !std::is_same<ExpressionType, PlainObjectType>::value>
25struct XprHelper {
26 XprHelper(const ExpressionType& xpr) : m_xpr(xpr) {}
27 inline const PlainObjectType& xpr() const { return m_xpr; }
28 // this is a new PlainObjectType initialized by xpr
29 const PlainObjectType m_xpr;
30};
31template <typename ExpressionType, typename PlainObjectType>
32struct XprHelper<ExpressionType, PlainObjectType, false> {
33 XprHelper(const ExpressionType& xpr) : m_xpr(xpr) {}
34 inline const PlainObjectType& xpr() const { return m_xpr; }
35 // this is a reference to xpr
36 const PlainObjectType& m_xpr;
37};
38
39template <typename PermDerived, bool NeedInverseEval>
40struct PermHelper {
41 using IndicesType = typename PermDerived::IndicesType;
42 using PermutationIndex = typename IndicesType::Scalar;
43 using type = PermutationMatrix<IndicesType::SizeAtCompileTime, IndicesType::MaxSizeAtCompileTime, PermutationIndex>;
44 PermHelper(const PermDerived& perm) : m_perm(perm.inverse()) {}
45 inline const type& perm() const { return m_perm; }
46 // this is a new PermutationMatrix initialized by perm.inverse()
47 const type m_perm;
48};
49template <typename PermDerived>
50struct PermHelper<PermDerived, false> {
51 using type = PermDerived;
52 PermHelper(const PermDerived& perm) : m_perm(perm) {}
53 inline const type& perm() const { return m_perm; }
54 // this is a reference to perm
55 const type& m_perm;
56};
57
58template <typename ExpressionType, int Side, bool Transposed>
59struct permutation_matrix_product<ExpressionType, Side, Transposed, SparseShape> {
60 using MatrixType = typename nested_eval<ExpressionType, 1>::type;
61 using MatrixTypeCleaned = remove_all_t<MatrixType>;
62
63 using Scalar = typename MatrixTypeCleaned::Scalar;
64 using StorageIndex = typename MatrixTypeCleaned::StorageIndex;
65
66 // the actual "return type" is `Dest`. this is a temporary type
67 using ReturnType = SparseMatrix<Scalar, MatrixTypeCleaned::IsRowMajor ? RowMajor : ColMajor, StorageIndex>;
68 using TmpHelper = XprHelper<ExpressionType, ReturnType>;
69
70 // The storage order of the matrix that is permuted is that of ReturnType, which can differ from ExpressionType's
71 // (e.g. for a product whose evaluated plain object is row-major).
72 static constexpr bool NeedOuterPermutation = ReturnType::IsRowMajor ? Side == OnTheLeft : Side == OnTheRight;
73 static constexpr bool NeedInversePermutation = Transposed ? Side == OnTheLeft : Side == OnTheRight;
74
75 template <typename Dest, typename PermutationType>
76 static inline void permute_outer(Dest& dst, const PermutationType& perm, const ExpressionType& xpr) {
77 // if ExpressionType is not ReturnType, evaluate `xpr` (allocation)
78 // otherwise, just reference `xpr`
79 // TODO: handle trivial expressions such as CwiseBinaryOp without temporary
80 const TmpHelper tmpHelper(xpr);
81 const ReturnType& tmp = tmpHelper.xpr();
82
83 ReturnType result(tmp.rows(), tmp.cols());
84
85 for (Index j = 0; j < tmp.outerSize(); j++) {
86 Index jp = perm.indices().coeff(j);
87 Index jsrc = NeedInversePermutation ? jp : j;
88 Index jdst = NeedInversePermutation ? j : jp;
89 Index begin = tmp.outerIndexPtr()[jsrc];
90 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[jsrc + 1] : begin + tmp.innerNonZeroPtr()[jsrc];
91 result.outerIndexPtr()[jdst + 1] += end - begin;
92 }
93
94 std::partial_sum(result.outerIndexPtr(), result.outerIndexPtr() + result.outerSize() + 1, result.outerIndexPtr());
95 result.resizeNonZeros(result.nonZeros());
96
97 for (Index j = 0; j < tmp.outerSize(); j++) {
98 Index jp = perm.indices().coeff(j);
99 Index jsrc = NeedInversePermutation ? jp : j;
100 Index jdst = NeedInversePermutation ? j : jp;
101 Index begin = tmp.outerIndexPtr()[jsrc];
102 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[jsrc + 1] : begin + tmp.innerNonZeroPtr()[jsrc];
103 Index target = result.outerIndexPtr()[jdst];
104 smart_copy(tmp.innerIndexPtr() + begin, tmp.innerIndexPtr() + end, result.innerIndexPtr() + target);
105 smart_copy(tmp.valuePtr() + begin, tmp.valuePtr() + end, result.valuePtr() + target);
106 }
107 dst = std::move(result);
108 }
109
110 template <typename Dest, typename PermutationType>
111 static inline void permute_inner(Dest& dst, const PermutationType& perm, const ExpressionType& xpr) {
112 using InnerPermHelper = PermHelper<PermutationType, NeedInversePermutation>;
113 using InnerPermType = typename InnerPermHelper::type;
114
115 // if ExpressionType is not ReturnType, evaluate `xpr` (allocation)
116 // otherwise, just reference `xpr`
117 // TODO: handle trivial expressions such as CwiseBinaryOp without temporary
118 const TmpHelper tmpHelper(xpr);
119 const ReturnType& tmp = tmpHelper.xpr();
120
121 // if inverse permutation of inner indices is requested, calculate perm.inverse() (allocation)
122 // otherwise, just reference `perm`
123 const InnerPermHelper permHelper(perm);
124 const InnerPermType& innerPerm = permHelper.perm();
125
126 ReturnType result(tmp.rows(), tmp.cols());
127
128 for (Index j = 0; j < tmp.outerSize(); j++) {
129 Index begin = tmp.outerIndexPtr()[j];
130 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[j + 1] : begin + tmp.innerNonZeroPtr()[j];
131 result.outerIndexPtr()[j + 1] += end - begin;
132 }
133
134 std::partial_sum(result.outerIndexPtr(), result.outerIndexPtr() + result.outerSize() + 1, result.outerIndexPtr());
135 result.resizeNonZeros(result.nonZeros());
136
137 for (Index j = 0; j < tmp.outerSize(); j++) {
138 Index begin = tmp.outerIndexPtr()[j];
139 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[j + 1] : begin + tmp.innerNonZeroPtr()[j];
140 Index target = result.outerIndexPtr()[j];
141 std::transform(tmp.innerIndexPtr() + begin, tmp.innerIndexPtr() + end, result.innerIndexPtr() + target,
142 [&innerPerm](StorageIndex i) { return innerPerm.indices().coeff(i); });
143 smart_copy(tmp.valuePtr() + begin, tmp.valuePtr() + end, result.valuePtr() + target);
144 }
145 // the inner indices were permuted, and must be sorted
146 result.sortInnerIndices();
147 dst = std::move(result);
148 }
149
150 template <typename Dest, typename PermutationType, bool DoOuter = NeedOuterPermutation,
151 std::enable_if_t<DoOuter, int> = 0>
152 static inline void run(Dest& dst, const PermutationType& perm, const ExpressionType& xpr) {
153 permute_outer(dst, perm, xpr);
154 }
155
156 template <typename Dest, typename PermutationType, bool DoOuter = NeedOuterPermutation,
157 std::enable_if_t<!DoOuter, int> = 0>
158 static inline void run(Dest& dst, const PermutationType& perm, const ExpressionType& xpr) {
159 permute_inner(dst, perm, xpr);
160 }
161};
162
163} // namespace internal
164
165namespace internal {
166
167template <int ProductTag>
168struct product_promote_storage_type<Sparse, PermutationStorage, ProductTag> {
169 using ret = Sparse;
170};
171template <int ProductTag>
172struct product_promote_storage_type<PermutationStorage, Sparse, ProductTag> {
173 using ret = Sparse;
174};
175
176// TODO, the following two overloads are only needed to define the right temporary type through
177// typename traits<permutation_matrix_product<Rhs,Lhs,OnTheRight,false> >::ReturnType
178// whereas it should be correctly handled by traits<Product<> >::PlainObject
179
180template <typename Lhs, typename Rhs, int ProductTag>
181struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, PermutationShape, SparseShape>
182 : public evaluator<typename permutation_matrix_product<Rhs, OnTheLeft, false, SparseShape>::ReturnType> {
183 using XprType = Product<Lhs, Rhs, AliasFreeProduct>;
184 using PlainObject = typename permutation_matrix_product<Rhs, OnTheLeft, false, SparseShape>::ReturnType;
185 using Base = evaluator<PlainObject>;
186
187 enum { Flags = Base::Flags | EvalBeforeNestingBit };
188
189 explicit product_evaluator(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
190 internal::construct_at<Base>(this, m_result);
191 generic_product_impl<Lhs, Rhs, PermutationShape, SparseShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs());
192 }
193
194 protected:
195 PlainObject m_result;
196};
197
198template <typename Lhs, typename Rhs, int ProductTag>
199struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, SparseShape, PermutationShape>
200 : public evaluator<typename permutation_matrix_product<Lhs, OnTheRight, false, SparseShape>::ReturnType> {
201 using XprType = Product<Lhs, Rhs, AliasFreeProduct>;
202 using PlainObject = typename permutation_matrix_product<Lhs, OnTheRight, false, SparseShape>::ReturnType;
203 using Base = evaluator<PlainObject>;
204
205 enum { Flags = Base::Flags | EvalBeforeNestingBit };
206
207 explicit product_evaluator(const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
208 ::new (static_cast<Base*>(this)) Base(m_result);
209 generic_product_impl<Lhs, Rhs, SparseShape, PermutationShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs());
210 }
211
212 protected:
213 PlainObject m_result;
214};
215
216} // end namespace internal
217
220template <typename SparseDerived, typename PermDerived>
221inline const Product<SparseDerived, PermDerived, AliasFreeProduct> operator*(
222 const SparseMatrixBase<SparseDerived>& matrix, const PermutationBase<PermDerived>& perm) {
223 return Product<SparseDerived, PermDerived, AliasFreeProduct>(matrix.derived(), perm.derived());
224}
225
228template <typename SparseDerived, typename PermDerived>
229inline const Product<PermDerived, SparseDerived, AliasFreeProduct> operator*(
230 const PermutationBase<PermDerived>& perm, const SparseMatrixBase<SparseDerived>& matrix) {
231 return Product<PermDerived, SparseDerived, AliasFreeProduct>(perm.derived(), matrix.derived());
232}
233
236template <typename SparseDerived, typename PermutationType>
237inline const Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct> operator*(
238 const SparseMatrixBase<SparseDerived>& matrix, const InverseImpl<PermutationType, PermutationStorage>& tperm) {
239 return Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct>(matrix.derived(), tperm.derived());
240}
241
244template <typename SparseDerived, typename PermutationType>
245inline const Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct> operator*(
246 const InverseImpl<PermutationType, PermutationStorage>& tperm, const SparseMatrixBase<SparseDerived>& matrix) {
247 return Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct>(tperm.derived(), matrix.derived());
248}
249
250} // end namespace Eigen
251
252#endif // EIGEN_SPARSE_PERMUTATION_H
@ OnTheLeft
Definition Constants.h:332
@ OnTheRight
Definition Constants.h:334
constexpr unsigned int EvalBeforeNestingBit
Definition Constants.h:75