Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TriangularMatrixVector.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 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_TRIANGULARMATRIXVECTOR_H
12#define EIGEN_TRIANGULARMATRIXVECTOR_H
13
14// IWYU pragma: private
15#include "../InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21// GCC 15.1 and 15.2 at -O3 with AVX2 miscompile run() for a real matrix times a complex vector: the SLP vectorizer
22// breaks copies of it specialized for a constant size (#3214); see EIGEN_GCC15_SLP_BUG.
23#if EIGEN_GCC15_SLP_BUG
24#define EIGEN_TRMV_DONT_INLINE EIGEN_DONT_INLINE __attribute__((optimize("no-tree-slp-vectorize")))
25#else
26#define EIGEN_TRMV_DONT_INLINE EIGEN_DONT_INLINE
27#endif
28
29template <typename Index, int Mode, typename LhsScalar, bool ConjLhs, typename RhsScalar, bool ConjRhs,
30 int StorageOrder, int Version = Specialized>
31struct triangular_matrix_vector_product;
32
33template <typename Index, int Mode, typename LhsScalar, bool ConjLhs, typename RhsScalar, bool ConjRhs, int Version>
34struct triangular_matrix_vector_product<Index, Mode, LhsScalar, ConjLhs, RhsScalar, ConjRhs, ColMajor, Version> {
35 using ResScalar = typename ScalarBinaryOpTraits<LhsScalar, RhsScalar>::ReturnType;
36 static constexpr bool IsLower = (Mode & Lower) == Lower;
37 static constexpr bool HasUnitDiag = (Mode & UnitDiag) == UnitDiag;
38 static constexpr bool HasZeroDiag = (Mode & ZeroDiag) == ZeroDiag;
39 static EIGEN_TRMV_DONT_INLINE void run(Index _rows, Index _cols, const LhsScalar* lhs_, Index lhsStride,
40 const RhsScalar* rhs_, Index rhsIncr, ResScalar* res_, Index resIncr,
41 const RhsScalar& alpha);
42};
43
44template <typename Index, int Mode, typename LhsScalar, bool ConjLhs, typename RhsScalar, bool ConjRhs, int Version>
45EIGEN_DONT_INLINE void triangular_matrix_vector_product<Index, Mode, LhsScalar, ConjLhs, RhsScalar, ConjRhs, ColMajor,
46 Version>::run(Index _rows, Index _cols, const LhsScalar* lhs_,
47 Index lhsStride, const RhsScalar* rhs_,
48 Index rhsIncr, ResScalar* res_, Index resIncr,
49 const RhsScalar& alpha) {
50 static const Index PanelWidth = EIGEN_TUNE_TRIANGULAR_PANEL_WIDTH;
51 Index size = (std::min)(_rows, _cols);
52 Index rows = IsLower ? _rows : (std::min)(_rows, _cols);
53 Index cols = IsLower ? (std::min)(_rows, _cols) : _cols;
54
55 using LhsMapper = const_blas_data_mapper<LhsScalar, Index, ColMajor>;
56 using RhsMapper = const_blas_data_mapper<RhsScalar, Index, RowMajor>;
57
58 conj_if<ConjLhs> cjl;
59 conj_if<ConjRhs> cjr;
60
61 for (Index pi = 0; pi < size; pi += PanelWidth) {
62 Index actualPanelWidth = (std::min)(PanelWidth, size - pi);
63
64 // Process the triangular panel using raw pointer operations with 2-column batching
65 // to eliminate expression template overhead and share result loads/stores.
66 EIGEN_IF_CONSTEXPR (IsLower) {
67 Index k = 0;
68 for (; k + 1 < actualPanelWidth; k += 2) {
69 Index i0 = pi + k;
70 Index i1 = i0 + 1;
71 ResScalar s0 = alpha * cjr(rhs_[i0 * rhsIncr]);
72 ResScalar s1 = alpha * cjr(rhs_[i1 * rhsIncr]);
73 const LhsScalar* EIGEN_RESTRICT c0 = lhs_ + i0 * lhsStride;
74 const LhsScalar* EIGEN_RESTRICT c1 = lhs_ + i1 * lhsStride;
75
76 // Diagonal of column 0
77 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) res_[i0] += s0 * cjl(c0[i0]);
78 // Row i1: contribution from column 0 + diagonal of column 1
79 {
80 ResScalar r1 = s0 * cjl(c0[i1]);
81 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) r1 += s1 * cjl(c1[i1]);
82 res_[i1] += r1;
83 }
84 // Shared rows where both columns contribute
85 Index panelEnd = pi + actualPanelWidth;
86 for (Index j = i1 + 1; j < panelEnd; ++j) res_[j] += s0 * cjl(c0[j]) + s1 * cjl(c1[j]);
87
88 EIGEN_IF_CONSTEXPR (HasUnitDiag) {
89 res_[i0] += s0;
90 res_[i1] += s1;
91 }
92 }
93 if (k < actualPanelWidth) {
94 Index i = pi + k;
95 ResScalar s = alpha * cjr(rhs_[i * rhsIncr]);
96 const LhsScalar* EIGEN_RESTRICT c = lhs_ + i * lhsStride;
97 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) res_[i] += s * cjl(c[i]);
98 EIGEN_IF_CONSTEXPR (HasUnitDiag) res_[i] += s;
99 }
100 } else {
101 // Upper triangular: process 2 columns at a time
102 Index k = 0;
103 for (; k + 1 < actualPanelWidth; k += 2) {
104 Index i0 = pi + k;
105 Index i1 = i0 + 1;
106 ResScalar s0 = alpha * cjr(rhs_[i0 * rhsIncr]);
107 ResScalar s1 = alpha * cjr(rhs_[i1 * rhsIncr]);
108 const LhsScalar* EIGEN_RESTRICT c0 = lhs_ + i0 * lhsStride;
109 const LhsScalar* EIGEN_RESTRICT c1 = lhs_ + i1 * lhsStride;
110
111 // Shared rows before the diagonal block
112 for (Index j = pi; j < i0; ++j) res_[j] += s0 * cjl(c0[j]) + s1 * cjl(c1[j]);
113
114 // Row i0: diagonal of col0 + contribution from col1
115 {
116 ResScalar r0 = s1 * cjl(c1[i0]);
117 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) r0 += s0 * cjl(c0[i0]);
118 res_[i0] += r0;
119 }
120 // Diagonal of column 1
121 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) res_[i1] += s1 * cjl(c1[i1]);
122
123 EIGEN_IF_CONSTEXPR (HasUnitDiag) {
124 res_[i0] += s0;
125 res_[i1] += s1;
126 }
127 }
128 if (k < actualPanelWidth) {
129 Index i = pi + k;
130 ResScalar s = alpha * cjr(rhs_[i * rhsIncr]);
131 const LhsScalar* EIGEN_RESTRICT c = lhs_ + i * lhsStride;
132 for (Index j = pi; j < i; ++j) res_[j] += s * cjl(c[j]);
133 EIGEN_IF_CONSTEXPR (!(HasUnitDiag || HasZeroDiag)) res_[i] += s * cjl(c[i]);
134 EIGEN_IF_CONSTEXPR (HasUnitDiag) res_[i] += s;
135 }
136 }
137
138 // Rectangular part: delegate to optimized GEMV
139 Index r = IsLower ? rows - pi - actualPanelWidth : pi;
140 if (r > 0) {
141 Index s = IsLower ? pi + actualPanelWidth : 0;
142 general_matrix_vector_product<Index, LhsScalar, LhsMapper, ColMajor, ConjLhs, RhsScalar, RhsMapper, ConjRhs,
143 BuiltIn>::run(r, actualPanelWidth, LhsMapper(&lhs_[pi * lhsStride + s], lhsStride),
144 RhsMapper(&rhs_[pi * rhsIncr], rhsIncr), &res_[s], resIncr, alpha);
145 }
146 }
147 EIGEN_IF_CONSTEXPR (!IsLower) {
148 if (cols > size) {
149 general_matrix_vector_product<Index, LhsScalar, LhsMapper, ColMajor, ConjLhs, RhsScalar, RhsMapper, ConjRhs>::run(
150 rows, cols - size, LhsMapper(&lhs_[size * lhsStride], lhsStride), RhsMapper(&rhs_[size * rhsIncr], rhsIncr),
151 res_, resIncr, alpha);
152 }
153 }
154}
155
156template <typename Index, int Mode, typename LhsScalar, bool ConjLhs, typename RhsScalar, bool ConjRhs, int Version>
157struct triangular_matrix_vector_product<Index, Mode, LhsScalar, ConjLhs, RhsScalar, ConjRhs, RowMajor, Version> {
158 using ResScalar = typename ScalarBinaryOpTraits<LhsScalar, RhsScalar>::ReturnType;
159 static constexpr bool IsLower = (Mode & Lower) == Lower;
160 static constexpr bool HasUnitDiag = (Mode & UnitDiag) == UnitDiag;
161 static constexpr bool HasZeroDiag = (Mode & ZeroDiag) == ZeroDiag;
162 static EIGEN_TRMV_DONT_INLINE void run(Index _rows, Index _cols, const LhsScalar* lhs_, Index lhsStride,
163 const RhsScalar* rhs_, Index rhsIncr, ResScalar* res_, Index resIncr,
164 const ResScalar& alpha);
165};
166
167template <typename Index, int Mode, typename LhsScalar, bool ConjLhs, typename RhsScalar, bool ConjRhs, int Version>
168EIGEN_DONT_INLINE void triangular_matrix_vector_product<Index, Mode, LhsScalar, ConjLhs, RhsScalar, ConjRhs, RowMajor,
169 Version>::run(Index _rows, Index _cols, const LhsScalar* lhs_,
170 Index lhsStride, const RhsScalar* rhs_,
171 Index rhsIncr, ResScalar* res_, Index resIncr,
172 const ResScalar& alpha) {
173 static const Index PanelWidth = EIGEN_TUNE_TRIANGULAR_PANEL_WIDTH;
174 Index diagSize = (std::min)(_rows, _cols);
175 Index rows = IsLower ? _rows : diagSize;
176 Index cols = IsLower ? diagSize : _cols;
177
178 using LhsMapper = const_blas_data_mapper<LhsScalar, Index, RowMajor>;
179 using RhsMapper = const_blas_data_mapper<RhsScalar, Index, RowMajor>;
180
181 conj_if<ConjLhs> cjl;
182 conj_if<ConjRhs> cjr;
183
184 for (Index pi = 0; pi < diagSize; pi += PanelWidth) {
185 Index actualPanelWidth = (std::min)(PanelWidth, diagSize - pi);
186
187 // Process the triangular panel using raw dot products to eliminate
188 // the cwiseProduct().sum() expression template overhead.
189 for (Index k = 0; k < actualPanelWidth; ++k) {
190 Index i = pi + k;
191 const LhsScalar* EIGEN_RESTRICT row_i = lhs_ + i * lhsStride;
192 ResScalar dot = ResScalar(0);
193
194 EIGEN_IF_CONSTEXPR (IsLower) {
195 Index s = pi;
196 Index len = (HasUnitDiag || HasZeroDiag) ? k : k + 1;
197 for (Index j = 0; j < len; ++j) dot += cjl(row_i[s + j]) * cjr(rhs_[s + j]);
198 } else {
199 Index s = (HasUnitDiag || HasZeroDiag) ? i + 1 : i;
200 Index len = pi + actualPanelWidth - s;
201 for (Index j = 0; j < len; ++j) dot += cjl(row_i[s + j]) * cjr(rhs_[s + j]);
202 }
203 res_[i * resIncr] += alpha * dot;
204 EIGEN_IF_CONSTEXPR (HasUnitDiag) res_[i * resIncr] += alpha * cjr(rhs_[i]);
205 }
206
207 // Rectangular part: delegate to optimized GEMV
208 Index r = IsLower ? pi : cols - pi - actualPanelWidth;
209 if (r > 0) {
210 Index s = IsLower ? 0 : pi + actualPanelWidth;
211 general_matrix_vector_product<Index, LhsScalar, LhsMapper, RowMajor, ConjLhs, RhsScalar, RhsMapper, ConjRhs,
212 BuiltIn>::run(actualPanelWidth, r, LhsMapper(&lhs_[pi * lhsStride + s], lhsStride),
213 RhsMapper(&rhs_[s], rhsIncr), &res_[pi * resIncr], resIncr, alpha);
214 }
215 }
216 EIGEN_IF_CONSTEXPR (IsLower) {
217 if (rows > diagSize) {
218 general_matrix_vector_product<Index, LhsScalar, LhsMapper, RowMajor, ConjLhs, RhsScalar, RhsMapper, ConjRhs>::run(
219 rows - diagSize, cols, LhsMapper(&lhs_[diagSize * lhsStride], lhsStride), RhsMapper(rhs_, rhsIncr),
220 &res_[diagSize * resIncr], resIncr, alpha);
221 }
222 }
223}
224
225#undef EIGEN_TRMV_DONT_INLINE
226
227/***************************************************************************
228 * Wrapper to product_triangular_vector
229 ***************************************************************************/
230
231template <int Mode, int StorageOrder>
232struct trmv_selector;
233
234} // end namespace internal
235
236namespace internal {
237
238template <int Mode, typename Lhs, typename Rhs>
239struct triangular_product_impl<Mode, true, Lhs, false, Rhs, true> {
240 template <typename Dest>
241 static void run(Dest& dst, const Lhs& lhs, const Rhs& rhs, const typename Dest::Scalar& alpha) {
242 EIGEN_INTERNAL_ASSERT_SAME_ROWS(dst, lhs);
243 EIGEN_INTERNAL_ASSERT_SAME_COLS(dst, rhs);
244
245 internal::trmv_selector<Mode, (int(internal::traits<Lhs>::Flags) & RowMajorBit) ? RowMajor : ColMajor>::run(
246 lhs, rhs, dst, alpha);
247 }
248};
249
250template <int Mode, typename Lhs, typename Rhs>
251struct triangular_product_impl<Mode, false, Lhs, true, Rhs, false> {
252 template <typename Dest>
253 static void run(Dest& dst, const Lhs& lhs, const Rhs& rhs, const typename Dest::Scalar& alpha) {
254 EIGEN_INTERNAL_ASSERT_SAME_ROWS(dst, lhs);
255 EIGEN_INTERNAL_ASSERT_SAME_COLS(dst, rhs);
256
257 Transpose<Dest> dstT(dst);
258 internal::trmv_selector<(Mode & (UnitDiag | ZeroDiag)) | ((Mode & Lower) ? Upper : Lower),
259 (int(internal::traits<Rhs>::Flags) & RowMajorBit) ? ColMajor
260 : RowMajor>::run(rhs.transpose(),
261 lhs.transpose(), dstT,
262 alpha);
263 }
264};
265
266} // end namespace internal
267
268namespace internal {
269
270// A factor s nested in a unit triangle reached the kernel through the product's alpha, so the unit diagonal
271// contributed alpha * s * rhs instead of alpha * rhs: subtract alpha * (s - 1) * rhs.
272template <int Mode, typename Lhs, typename Rhs, typename Dest, typename LhsScalar>
273EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void trmv_correct_unit_diagonal(const Lhs& lhs, const Rhs& rhs, Dest& dest,
274 const typename Dest::Scalar& alpha,
275 const LhsScalar& lhs_alpha) {
276 EIGEN_IF_CONSTEXPR ((Mode & UnitDiag) == UnitDiag) {
277 if (!numext::is_exactly_one(lhs_alpha)) {
278 Index diagSize = (std::min)(lhs.rows(), lhs.cols());
279 dest.matrix().head(diagSize) -= (alpha * (lhs_alpha - LhsScalar(1))) * rhs.head(diagSize);
280 }
281 }
282}
283
284template <int Mode>
285struct trmv_selector<Mode, ColMajor> {
286 template <typename Lhs, typename Rhs, typename Dest>
287 static void run(const Lhs& lhs, const Rhs& rhs, Dest& dest, const typename Dest::Scalar& alpha) {
288 using LhsScalar = typename Lhs::Scalar;
289 using RhsScalar = typename Rhs::Scalar;
290 using ResScalar = typename Dest::Scalar;
291
292 using LhsBlasTraits = internal::blas_traits<Lhs>;
293 using ActualLhsType = typename LhsBlasTraits::DirectLinearAccessType;
294 using RhsBlasTraits = internal::blas_traits<Rhs>;
295 using ActualRhsType = typename RhsBlasTraits::DirectLinearAccessType;
296 add_const_on_value_type_t<ActualLhsType> actualLhs = LhsBlasTraits::extract(lhs);
297 add_const_on_value_type_t<ActualRhsType> actualRhs = RhsBlasTraits::extract(rhs);
298
299 LhsScalar lhs_alpha = LhsBlasTraits::extractScalarFactor(lhs);
300 RhsScalar rhs_alpha = RhsBlasTraits::extractScalarFactor(rhs);
301 ResScalar actualAlpha = alpha * lhs_alpha * rhs_alpha;
302
303 // FIXME find a way to allow an inner stride on the result if packet_traits<Scalar>::size==1
304 // On the other hand, it is good for the cache to pack the vector anyways...
305 constexpr bool EvalToDestAtCompileTime = Dest::InnerStrideAtCompileTime == 1;
306 constexpr bool ComplexByReal = (NumTraits<LhsScalar>::IsComplex) && (!NumTraits<RhsScalar>::IsComplex);
307 constexpr bool MightCannotUseDest = (Dest::InnerStrideAtCompileTime != 1) || ComplexByReal;
308
309 gemv_static_vector_if<ResScalar, Dest::SizeAtCompileTime, Dest::MaxSizeAtCompileTime, MightCannotUseDest>
310 static_dest;
311
312 gemv_destination_policy<RhsScalar, ResScalar, EvalToDestAtCompileTime, ComplexByReal> destPolicy(actualAlpha);
313
314 ei_declare_aligned_stack_constructed_variable(ResScalar, actualDestPtr, dest.size(),
315 destPolicy.eval_to_dest() ? dest.data() : static_dest.data());
316
317 destPolicy.prepare(dest, actualDestPtr);
318
319 internal::triangular_matrix_vector_product<Index, Mode, LhsScalar, LhsBlasTraits::NeedToConjugate, RhsScalar,
320 RhsBlasTraits::NeedToConjugate,
321 ColMajor>::run(actualLhs.rows(), actualLhs.cols(), actualLhs.data(),
322 actualLhs.outerStride(), actualRhs.data(),
323 actualRhs.innerStride(), actualDestPtr, 1,
324 destPolicy.compatible_alpha());
325
326 destPolicy.copy_back(dest, actualDestPtr);
327
328 trmv_correct_unit_diagonal<Mode>(lhs, rhs, dest, alpha, lhs_alpha);
329 }
330};
331
332template <int Mode>
333struct trmv_selector<Mode, RowMajor> {
334 template <typename Lhs, typename Rhs, typename Dest>
335 static void run(const Lhs& lhs, const Rhs& rhs, Dest& dest, const typename Dest::Scalar& alpha) {
336 using LhsScalar = typename Lhs::Scalar;
337 using RhsScalar = typename Rhs::Scalar;
338 using ResScalar = typename Dest::Scalar;
339
340 using LhsBlasTraits = internal::blas_traits<Lhs>;
341 using ActualLhsType = typename LhsBlasTraits::DirectLinearAccessType;
342 using RhsBlasTraits = internal::blas_traits<Rhs>;
343 using ActualRhsType = typename RhsBlasTraits::DirectLinearAccessType;
344 using ActualRhsTypeCleaned = internal::remove_all_t<ActualRhsType>;
345
346 std::add_const_t<ActualLhsType> actualLhs = LhsBlasTraits::extract(lhs);
347 std::add_const_t<ActualRhsType> actualRhs = RhsBlasTraits::extract(rhs);
348
349 LhsScalar lhs_alpha = LhsBlasTraits::extractScalarFactor(lhs);
350 RhsScalar rhs_alpha = RhsBlasTraits::extractScalarFactor(rhs);
351 ResScalar actualAlpha = alpha * lhs_alpha * rhs_alpha;
352
353 constexpr bool DirectlyUseRhs = ActualRhsTypeCleaned::InnerStrideAtCompileTime == 1;
354
355 gemv_static_vector_if<RhsScalar, ActualRhsTypeCleaned::SizeAtCompileTime,
356 ActualRhsTypeCleaned::MaxSizeAtCompileTime, !DirectlyUseRhs>
357 static_rhs;
358
359 ei_declare_aligned_stack_constructed_variable(
360 RhsScalar, actualRhsPtr, actualRhs.size(),
361 DirectlyUseRhs ? const_cast<RhsScalar*>(actualRhs.data()) : static_rhs.data());
362
363 gemv_prepare_rhs<DirectlyUseRhs>(actualRhs, actualRhsPtr);
364
365 internal::triangular_matrix_vector_product<Index, Mode, LhsScalar, LhsBlasTraits::NeedToConjugate, RhsScalar,
366 RhsBlasTraits::NeedToConjugate, RowMajor>::run(actualLhs.rows(),
367 actualLhs.cols(),
368 actualLhs.data(),
369 actualLhs.outerStride(),
370 actualRhsPtr, 1,
371 dest.data(),
372 dest.innerStride(),
373 actualAlpha);
374
375 trmv_correct_unit_diagonal<Mode>(lhs, rhs, dest, alpha, lhs_alpha);
376 }
377};
378
379} // end namespace internal
380
381} // end namespace Eigen
382
383#endif // EIGEN_TRIANGULARMATRIXVECTOR_H
@ UnitDiag
Definition Constants.h:216
@ ZeroDiag
Definition Constants.h:218
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
constexpr unsigned int RowMajorBit
Definition Constants.h:71