Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
GeneralMatrixMatrixTriangular.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009-2010 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_GENERAL_MATRIX_MATRIX_TRIANGULAR_H
12#define EIGEN_GENERAL_MATRIX_MATRIX_TRIANGULAR_H
13
14// IWYU pragma: private
15#include "../InternalHeaderCheck.h"
16
17namespace Eigen {
18
19template <typename Scalar, typename Index, int StorageOrder, int UpLo, bool ConjLhs, bool ConjRhs>
20struct selfadjoint_rank1_update;
21
22namespace internal {
23
24/**********************************************************************
25 * This file implements a general A * B product while
26 * evaluating only one triangular part of the product.
27 * This is a more general version of self adjoint product (C += A A^T)
28 * as the level 3 SYRK Blas routine.
29 **********************************************************************/
30
31// forward declarations (defined at the end of this file)
32template <typename LhsScalar, typename RhsScalar, typename Index, int mr, int nr, bool ConjLhs, bool ConjRhs,
33 int ResInnerStride, int UpLo>
34struct tribb_kernel;
35
36/* Optimized matrix-matrix product evaluating only one triangular half */
37template <typename Index, typename LhsScalar, int LhsStorageOrder, bool ConjugateLhs, typename RhsScalar,
38 int RhsStorageOrder, bool ConjugateRhs, int ResStorageOrder, int ResInnerStride, int UpLo,
39 int Version = Specialized>
40struct general_matrix_matrix_triangular_product;
41
42// as usual if the result is row major => we transpose the product
43template <typename Index, typename LhsScalar, int LhsStorageOrder, bool ConjugateLhs, typename RhsScalar,
44 int RhsStorageOrder, bool ConjugateRhs, int ResInnerStride, int UpLo, int Version>
45struct general_matrix_matrix_triangular_product<Index, LhsScalar, LhsStorageOrder, ConjugateLhs, RhsScalar,
46 RhsStorageOrder, ConjugateRhs, RowMajor, ResInnerStride, UpLo,
47 Version> {
48 using ResScalar = typename ScalarBinaryOpTraits<LhsScalar, RhsScalar>::ReturnType;
49 static EIGEN_STRONG_INLINE void run(Index size, Index depth, const LhsScalar* lhs, Index lhsStride,
50 const RhsScalar* rhs, Index rhsStride, ResScalar* res, Index resIncr,
51 Index resStride, const ResScalar& alpha,
52 level3_blocking<RhsScalar, LhsScalar>& blocking) {
53 general_matrix_matrix_triangular_product<Index, RhsScalar, RhsStorageOrder == RowMajor ? ColMajor : RowMajor,
54 ConjugateRhs, LhsScalar, LhsStorageOrder == RowMajor ? ColMajor : RowMajor,
55 ConjugateLhs, ColMajor, ResInnerStride,
56 UpLo == Lower ? Upper : Lower>::run(size, depth, rhs, rhsStride, lhs,
57 lhsStride, res, resIncr, resStride,
58 alpha, blocking);
59 }
60};
61
62template <typename Index, typename LhsScalar, int LhsStorageOrder, bool ConjugateLhs, typename RhsScalar,
63 int RhsStorageOrder, bool ConjugateRhs, int ResInnerStride, int UpLo, int Version>
64struct general_matrix_matrix_triangular_product<Index, LhsScalar, LhsStorageOrder, ConjugateLhs, RhsScalar,
65 RhsStorageOrder, ConjugateRhs, ColMajor, ResInnerStride, UpLo,
66 Version> {
67 using ResScalar = typename ScalarBinaryOpTraits<LhsScalar, RhsScalar>::ReturnType;
68 // Inlining into callers' loops can accumulate the packing buffers' stack allocations.
69 static EIGEN_DONT_INLINE void run(Index size, Index depth, const LhsScalar* lhs_, Index lhsStride,
70 const RhsScalar* rhs_, Index rhsStride, ResScalar* res_, Index resIncr,
71 Index resStride, const ResScalar& alpha,
72 level3_blocking<LhsScalar, RhsScalar>& blocking) {
73 if (size == 0) {
74 return;
75 }
76
77 using Traits = gebp_traits<LhsScalar, RhsScalar>;
78
79 using LhsMapper = const_blas_data_mapper<LhsScalar, Index, LhsStorageOrder>;
80 using RhsMapper = const_blas_data_mapper<RhsScalar, Index, RhsStorageOrder>;
81 using ResMapper = blas_data_mapper<typename Traits::ResScalar, Index, ColMajor, Unaligned, ResInnerStride>;
82 LhsMapper lhs(lhs_, lhsStride);
83 RhsMapper rhs(rhs_, rhsStride);
84 ResMapper res(res_, resStride, resIncr);
85
86 Index kc = blocking.kc();
87 // Ensure that mc >= nr and <= size
88 Index mc = (std::min)(size, (std::max)(static_cast<decltype(blocking.mc())>(Traits::nr), blocking.mc()));
89
90 // !!! mc must be a multiple of nr
91 if (mc > Traits::nr) {
92 using UnsignedIndex = std::make_unsigned_t<Index>;
93 mc = (UnsignedIndex(mc) / Traits::nr) * Traits::nr;
94 }
95
96 std::size_t sizeA = kc * mc;
97 std::size_t sizeB = kc * size;
98
99 gemm_packing_space<LhsScalar, RhsScalar> packing(sizeA, sizeB, blocking.blockA(), blocking.blockB());
100 ei_declare_aligned_stack_constructed_variable(LhsScalar, blockA, sizeA, packing.blockA());
101 ei_declare_aligned_stack_constructed_variable(RhsScalar, blockB, sizeB, packing.blockB());
102
103 gemm_pack_lhs<LhsScalar, Index, LhsMapper, Traits::mr, Traits::LhsProgress, typename Traits::LhsPacket4Packing,
104 LhsStorageOrder>
105 pack_lhs;
106 gemm_pack_rhs<RhsScalar, Index, RhsMapper, Traits::nr, RhsStorageOrder> pack_rhs;
107 gebp_kernel<LhsScalar, RhsScalar, Index, ResMapper, Traits::mr, Traits::nr, ConjugateLhs, ConjugateRhs> gebp;
108 tribb_kernel<LhsScalar, RhsScalar, Index, Traits::mr, Traits::nr, ConjugateLhs, ConjugateRhs, ResInnerStride, UpLo>
109 sybb;
110
111 for (Index k2 = 0; k2 < depth; k2 += kc) {
112 const Index actual_kc = (std::min)(k2 + kc, depth) - k2;
113
114 // note that the actual rhs is the transpose/adjoint of mat
115 pack_rhs(blockB, rhs.getSubMapper(k2, 0), actual_kc, size);
116
117 for (Index i2 = 0; i2 < size; i2 += mc) {
118 const Index actual_mc = (std::min)(i2 + mc, size) - i2;
119
120 pack_lhs(blockA, lhs.getSubMapper(i2, k2), actual_kc, actual_mc);
121
122 // the selected actual_mc * size panel of res is split into three different parts:
123 // 1 - before the diagonal => processed with gebp or skipped
124 // 2 - the actual_mc x actual_mc symmetric block => processed with a special kernel
125 // 3 - after the diagonal => processed with gebp or skipped
126 EIGEN_IF_CONSTEXPR (UpLo == Lower) {
127 gebp(res.getSubMapper(i2, 0), blockA, blockB, actual_mc, actual_kc, (std::min)(size, i2), alpha, -1, -1, 0,
128 0);
129 }
130
131 sybb(res_ + resStride * i2 + resIncr * i2, resIncr, resStride, blockA, blockB + actual_kc * i2, actual_mc,
132 actual_kc, alpha);
133
134 EIGEN_IF_CONSTEXPR (UpLo == Upper) {
135 Index j2 = i2 + actual_mc;
136 gebp(res.getSubMapper(i2, j2), blockA, blockB + actual_kc * j2, actual_mc, actual_kc,
137 (std::max)(Index(0), size - j2), alpha, -1, -1, 0, 0);
138 }
139 }
140 }
141 }
142};
143
144// Optimized packed Block * packed Block product kernel evaluating only one given triangular part
145// This kernel is built on top of the gebp kernel:
146// - the current destination block is processed per panel of actual_mc x BlockSize
147// where BlockSize is set to the minimal value allowing gebp to be as fast as possible
148// - then, as usual, each panel is split into three parts along the diagonal,
149// the sub blocks above and below the diagonal are processed as usual,
150// while the triangular block overlapping the diagonal is evaluated into a
151// small temporary buffer which is then accumulated into the result using a
152// triangular traversal.
153template <typename LhsScalar, typename RhsScalar, typename Index, int mr, int nr, bool ConjLhs, bool ConjRhs,
154 int ResInnerStride, int UpLo>
155struct tribb_kernel {
156 using Traits = gebp_traits<LhsScalar, RhsScalar, ConjLhs, ConjRhs>;
157 using ResScalar = typename Traits::ResScalar;
158
159 enum { BlockSize = meta_least_common_multiple<plain_enum_max(mr, nr), plain_enum_min(mr, nr)>::value };
160 void operator()(ResScalar* res_, Index resIncr, Index resStride, const LhsScalar* blockA, const RhsScalar* blockB,
161 Index size, Index depth, const ResScalar& alpha) const {
162 using ResMapper = blas_data_mapper<ResScalar, Index, ColMajor, Unaligned, ResInnerStride>;
163 using BufferMapper = blas_data_mapper<ResScalar, Index, ColMajor, Unaligned>;
164 ResMapper res(res_, resStride, resIncr);
165 gebp_kernel<LhsScalar, RhsScalar, Index, ResMapper, mr, nr, ConjLhs, ConjRhs> gebp_kernel1;
166 gebp_kernel<LhsScalar, RhsScalar, Index, BufferMapper, mr, nr, ConjLhs, ConjRhs> gebp_kernel2;
167
168 static constexpr int BufferCapacity =
169 (EIGEN_STACK_ALLOCATION_LIMIT == 0 || BlockSize * BlockSize * sizeof(ResScalar) <= EIGEN_STACK_ALLOCATION_LIMIT)
170 ? int(BlockSize)
171 : Dynamic;
172 Matrix<ResScalar, BufferCapacity, BufferCapacity, ColMajor> buffer(BlockSize, BlockSize);
173
174 // let's process the block per panel of actual_mc x BlockSize,
175 // again, each is split into three parts, etc.
176 for (Index j = 0; j < size; j += BlockSize) {
177 Index actualBlockSize = std::min<Index>(BlockSize, size - j);
178 const RhsScalar* actual_b = blockB + j * depth;
179
180 EIGEN_IF_CONSTEXPR (UpLo == Upper) {
181 gebp_kernel1(res.getSubMapper(0, j), blockA, actual_b, j, depth, actualBlockSize, alpha, -1, -1, 0, 0);
182 }
183
184 // selfadjoint micro block
185 {
186 Index i = j;
187 buffer.setZero();
188 // 1 - apply the kernel on the temporary buffer
189 gebp_kernel2(BufferMapper(buffer.data(), BlockSize), blockA + depth * i, actual_b, actualBlockSize, depth,
190 actualBlockSize, alpha, -1, -1, 0, 0);
191
192 // 2 - triangular accumulation
193 for (Index j1 = 0; j1 < actualBlockSize; ++j1) {
194 typename ResMapper::LinearMapper r = res.getLinearMapper(i, j + j1);
195 for (Index i1 = UpLo == Lower ? j1 : 0; UpLo == Lower ? i1 < actualBlockSize : i1 <= j1; ++i1)
196 r(i1) += buffer(i1, j1);
197 }
198 }
199
200 EIGEN_IF_CONSTEXPR (UpLo == Lower) {
201 Index i = j + actualBlockSize;
202 gebp_kernel1(res.getSubMapper(i, j), blockA + depth * i, actual_b, size - i, depth, actualBlockSize, alpha, -1,
203 -1, 0, 0);
204 }
205 }
206 }
207};
208
209} // end namespace internal
210
211// high level API
212
213template <typename MatrixType, typename ProductType, int UpLo, bool IsOuterProduct>
214struct general_product_to_triangular_selector;
215
216template <typename MatrixType, typename ProductType, int UpLo>
217struct general_product_to_triangular_selector<MatrixType, ProductType, UpLo, true> {
218 static void run(MatrixType& mat, const ProductType& prod, const typename MatrixType::Scalar& alpha, bool beta) {
219 using Scalar = typename MatrixType::Scalar;
220
221 using Lhs = internal::remove_all_t<typename ProductType::LhsNested>;
222 using LhsBlasTraits = internal::blas_traits<Lhs>;
223 using ActualLhs = typename LhsBlasTraits::DirectLinearAccessType;
224 using ActualLhs_ = internal::remove_all_t<ActualLhs>;
225 internal::add_const_on_value_type_t<ActualLhs> actualLhs = LhsBlasTraits::extract(prod.lhs());
226
227 using Rhs = internal::remove_all_t<typename ProductType::RhsNested>;
228 using RhsBlasTraits = internal::blas_traits<Rhs>;
229 using ActualRhs = typename RhsBlasTraits::DirectLinearAccessType;
230 using ActualRhs_ = internal::remove_all_t<ActualRhs>;
231 internal::add_const_on_value_type_t<ActualRhs> actualRhs = RhsBlasTraits::extract(prod.rhs());
232
233 Scalar actualAlpha = alpha * LhsBlasTraits::extractScalarFactor(prod.lhs().derived()) *
234 RhsBlasTraits::extractScalarFactor(prod.rhs().derived());
235
236 if (!beta) mat.template triangularView<UpLo>().setZero();
237
238 // The rank-1 kernel below addresses mat with a unit inner stride.
239 if (MatrixType::InnerStrideAtCompileTime != 1 && mat.innerStride() != 1) {
240 mat.template triangularView<UpLo>() += typename ProductType::PlainObject(alpha * prod);
241 return;
242 }
243
244 enum {
245 StorageOrder = (internal::traits<MatrixType>::Flags & RowMajorBit) ? RowMajor : ColMajor,
246 UseLhsDirectly = ActualLhs_::InnerStrideAtCompileTime == 1,
247 UseRhsDirectly = ActualRhs_::InnerStrideAtCompileTime == 1
248 };
249
250 internal::gemv_static_vector_if<Scalar, Lhs::SizeAtCompileTime, Lhs::MaxSizeAtCompileTime, !UseLhsDirectly>
251 static_lhs;
252 ei_declare_aligned_stack_constructed_variable(
253 Scalar, actualLhsPtr, actualLhs.size(),
254 (UseLhsDirectly ? const_cast<Scalar*>(actualLhs.data()) : static_lhs.data()));
255 EIGEN_IF_CONSTEXPR (!UseLhsDirectly) {
256 Map<typename ActualLhs_::PlainObject>(actualLhsPtr, actualLhs.size()) = actualLhs;
257 }
258
259 internal::gemv_static_vector_if<Scalar, Rhs::SizeAtCompileTime, Rhs::MaxSizeAtCompileTime, !UseRhsDirectly>
260 static_rhs;
261 ei_declare_aligned_stack_constructed_variable(
262 Scalar, actualRhsPtr, actualRhs.size(),
263 (UseRhsDirectly ? const_cast<Scalar*>(actualRhs.data()) : static_rhs.data()));
264 EIGEN_IF_CONSTEXPR (!UseRhsDirectly) {
265 Map<typename ActualRhs_::PlainObject>(actualRhsPtr, actualRhs.size()) = actualRhs;
266 }
267
268 // A strictly triangular part is the triangle of the trailing (size-1) block one step off the diagonal.
269 const bool skipDiag = (UpLo & ZeroDiag) != 0, isLower = (UpLo & Lower) != 0;
270 const Index size = actualLhs.size() - skipDiag;
271 if (size <= 0) return;
272 Scalar* res = mat.data() + (!skipDiag ? 0 : (int(StorageOrder) == RowMajor) != isLower ? 1 : mat.outerStride());
273 selfadjoint_rank1_update<Scalar, Index, StorageOrder, UpLo&(Lower | Upper),
274 LhsBlasTraits::NeedToConjugate && NumTraits<Scalar>::IsComplex,
275 RhsBlasTraits::NeedToConjugate &&
276 NumTraits<Scalar>::IsComplex>::run(size, res, mat.outerStride(),
277 actualLhsPtr + (skipDiag && isLower),
278 actualRhsPtr + (skipDiag && !isLower), actualAlpha);
279 }
280};
281
282template <typename MatrixType, typename ProductType, int UpLo>
283struct general_product_to_triangular_selector<MatrixType, ProductType, UpLo, false> {
284 static void run(MatrixType& mat, const ProductType& prod, const typename MatrixType::Scalar& alpha, bool beta) {
285 using Lhs = internal::remove_all_t<typename ProductType::LhsNested>;
286 using LhsBlasTraits = internal::blas_traits<Lhs>;
287 using ActualLhs = typename LhsBlasTraits::DirectLinearAccessType;
288 using ActualLhs_ = internal::remove_all_t<ActualLhs>;
289 internal::add_const_on_value_type_t<ActualLhs> actualLhs = LhsBlasTraits::extract(prod.lhs());
290
291 using Rhs = internal::remove_all_t<typename ProductType::RhsNested>;
292 using RhsBlasTraits = internal::blas_traits<Rhs>;
293 using ActualRhs = typename RhsBlasTraits::DirectLinearAccessType;
294 using ActualRhs_ = internal::remove_all_t<ActualRhs>;
295 internal::add_const_on_value_type_t<ActualRhs> actualRhs = RhsBlasTraits::extract(prod.rhs());
296
297 typename ProductType::Scalar actualAlpha = alpha * LhsBlasTraits::extractScalarFactor(prod.lhs().derived()) *
298 RhsBlasTraits::extractScalarFactor(prod.rhs().derived());
299
300 if (!beta) mat.template triangularView<UpLo>().setZero();
301
302 enum {
303 IsRowMajor = (internal::traits<MatrixType>::Flags & RowMajorBit) ? 1 : 0,
304 LhsIsRowMajor = ActualLhs_::Flags & RowMajorBit ? 1 : 0,
305 RhsIsRowMajor = ActualRhs_::Flags & RowMajorBit ? 1 : 0,
306 SkipDiag = (UpLo & (UnitDiag | ZeroDiag)) != 0
307 };
308
309 Index size = mat.cols();
310 EIGEN_IF_CONSTEXPR (SkipDiag) size--;
311 Index depth = actualLhs.cols();
312 EIGEN_INTERNAL_ASSERT_SAME_ROWS(actualLhs, mat);
313 EIGEN_INTERNAL_ASSERT_SAME_COLS(actualRhs, mat);
314 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE(actualLhs, actualRhs);
315 if (size <= 0 || depth == 0) return;
316
317 using BlockingType =
318 internal::gemm_blocking_space<IsRowMajor ? RowMajor : ColMajor, typename Lhs::Scalar, typename Rhs::Scalar,
319 MatrixType::MaxColsAtCompileTime, MatrixType::MaxColsAtCompileTime,
320 ActualRhs_::MaxColsAtCompileTime>;
321
322 BlockingType blocking(size, size, depth, 1, false);
323
324 internal::general_matrix_matrix_triangular_product<
325 Index, typename Lhs::Scalar, LhsIsRowMajor ? RowMajor : ColMajor, LhsBlasTraits::NeedToConjugate,
326 typename Rhs::Scalar, RhsIsRowMajor ? RowMajor : ColMajor, RhsBlasTraits::NeedToConjugate,
327 IsRowMajor ? RowMajor : ColMajor, MatrixType::InnerStrideAtCompileTime,
328 UpLo&(Lower | Upper)>::run(size, depth, &actualLhs.coeffRef(SkipDiag && (UpLo & Lower) == Lower ? 1 : 0, 0),
329 actualLhs.outerStride(),
330 &actualRhs.coeffRef(0, SkipDiag && (UpLo & Upper) == Upper ? 1 : 0),
331 actualRhs.outerStride(),
332 mat.data() +
333 (SkipDiag ? (bool(IsRowMajor) != ((UpLo & Lower) == Lower) ? mat.innerStride()
334 : mat.outerStride())
335 : 0),
336 mat.innerStride(), mat.outerStride(), actualAlpha, blocking);
337 }
338};
339
340template <typename MatrixType_, unsigned int Mode_>
341template <typename ProductType>
342EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename TriangularViewImpl<MatrixType_, Mode_, Dense>::TriangularViewType&
343TriangularViewImpl<MatrixType_, Mode_, Dense>::_assignProduct(
344 const ProductType& prod, const typename TriangularViewImpl<MatrixType_, Mode_, Dense>::Scalar& alpha, bool beta) {
345 EIGEN_STATIC_ASSERT((Mode_ & UnitDiag) == 0, WRITING_TO_TRIANGULAR_PART_WITH_UNIT_DIAGONAL_IS_NOT_SUPPORTED);
346 EIGEN_INTERNAL_ASSERT_SAME_SHAPE(derived(), prod);
347
348 // The rank-k and rank-1 kernels below update a square triangle.
349 if (derived().rows() != derived().cols()) {
350 typename ProductType::PlainObject tmp(alpha * prod);
351 if (beta)
352 derived() += tmp;
353 else
354 derived() = tmp;
355 return derived();
356 }
357
358 general_product_to_triangular_selector<MatrixType_, ProductType, Mode_,
359 internal::traits<ProductType>::InnerSize == 1>::run(derived()
360 .nestedExpression()
361 .const_cast_derived(),
362 prod, alpha, beta);
363
364 return derived();
365}
366
367} // end namespace Eigen
368
369#endif // EIGEN_GENERAL_MATRIX_MATRIX_TRIANGULAR_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