Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
SolveTriangular.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2008-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_SOLVETRIANGULAR_H
12#define EIGEN_SOLVETRIANGULAR_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21// Forward declarations:
22// The following two routines are implemented in the products/TriangularSolver*.h files
23template <typename LhsScalar, typename RhsScalar, typename Index, int Side, int Mode, bool Conjugate, int StorageOrder>
24struct triangular_solve_vector;
25
26template <typename Scalar, typename Index, int Side, int Mode, bool Conjugate, int TriStorageOrder,
27 int OtherStorageOrder, int OtherInnerStride>
28struct triangular_solve_matrix;
29
30// small helper struct extracting some traits on the underlying solver operation
31template <typename Lhs, typename Rhs, int Side>
32class trsolve_traits {
33 private:
34 enum { RhsIsVectorAtCompileTime = (Side == OnTheLeft ? Rhs::ColsAtCompileTime : Rhs::RowsAtCompileTime) == 1 };
35
36 public:
37 enum {
38 Unrolling = (RhsIsVectorAtCompileTime && Rhs::SizeAtCompileTime != Dynamic && Rhs::SizeAtCompileTime <= 8)
39 ? CompleteUnrolling
40 : NoUnrolling,
41 RhsVectors = RhsIsVectorAtCompileTime ? 1 : Dynamic
42 };
43};
44
45template <typename Lhs, typename Rhs,
46 int Side, // can be OnTheLeft/OnTheRight
47 int Mode, // can be Upper/Lower | UnitDiag
48 int Unrolling = trsolve_traits<Lhs, Rhs, Side>::Unrolling,
49 int RhsVectors = trsolve_traits<Lhs, Rhs, Side>::RhsVectors>
50struct triangular_solver_selector;
51
52template <typename Lhs, typename Rhs, int Side, int Mode>
53struct triangular_solver_selector<Lhs, Rhs, Side, Mode, NoUnrolling, 1> {
54 using LhsScalar = typename Lhs::Scalar;
55 using RhsScalar = typename Rhs::Scalar;
56 using LhsProductTraits = blas_traits<Lhs>;
57 using ActualLhsType = typename LhsProductTraits::DirectLinearAccessType;
58 using ActualLhsTypeCleaned = remove_all_t<ActualLhsType>;
59 using MappedRhs = Map<Matrix<RhsScalar, Dynamic, 1>, Aligned>;
60 static EIGEN_DEVICE_FUNC void run(const Lhs& lhs, Rhs& rhs) {
61 add_const_on_value_type_t<ActualLhsType> actualLhs = LhsProductTraits::extract(lhs);
62
63 // FIXME find a way to allow an inner stride if packet_traits<Scalar>::size==1
64
65 bool useRhsDirectly = Rhs::InnerStrideAtCompileTime == 1 || rhs.innerStride() == 1;
66
67 ei_declare_aligned_stack_constructed_variable(RhsScalar, actualRhs, rhs.size(), (useRhsDirectly ? rhs.data() : 0));
68
69 if (!useRhsDirectly) MappedRhs(actualRhs, rhs.size()) = rhs;
70
71 triangular_solve_vector<LhsScalar, RhsScalar, Index, Side, Mode, LhsProductTraits::NeedToConjugate,
72 (int(ActualLhsTypeCleaned::Flags) & RowMajorBit) ? RowMajor
73 : ColMajor>::run(actualLhs.cols(),
74 actualLhs.data(),
75 actualLhs.outerStride(),
76 actualRhs);
77
78 if (!useRhsDirectly) rhs = MappedRhs(actualRhs, rhs.size());
79 }
80};
81
82// the rhs is a matrix
83template <typename Lhs, typename Rhs, int Side, int Mode>
84struct triangular_solver_selector<Lhs, Rhs, Side, Mode, NoUnrolling, Dynamic> {
85 using Scalar = typename Rhs::Scalar;
86 using LhsProductTraits = blas_traits<Lhs>;
87 using ActualLhsType = typename LhsProductTraits::DirectLinearAccessType;
88
89 static EIGEN_DEVICE_FUNC void run(const Lhs& lhs, Rhs& rhs) {
90 add_const_on_value_type_t<ActualLhsType> actualLhs = LhsProductTraits::extract(lhs);
91
92 const Index size = lhs.rows();
93 const Index othersize = Side == OnTheLeft ? rhs.cols() : rhs.rows();
94
95 using BlockingType = internal::gemm_blocking_space<(Rhs::Flags & RowMajorBit) ? RowMajor : ColMajor, Scalar, Scalar,
96 Rhs::MaxRowsAtCompileTime, Rhs::MaxColsAtCompileTime,
97 Lhs::MaxRowsAtCompileTime, 4>;
98
99 // Nothing to solve.
100 if (actualLhs.size() == 0 || rhs.size() == 0) {
101 return;
102 }
103
104 BlockingType blocking(rhs.rows(), rhs.cols(), size, 1, false);
105
106 triangular_solve_matrix<Scalar, Index, Side, Mode, LhsProductTraits::NeedToConjugate,
107 (int(Lhs::Flags) & RowMajorBit) ? RowMajor : ColMajor,
108 (Rhs::Flags & RowMajorBit) ? RowMajor : ColMajor,
109 Rhs::InnerStrideAtCompileTime>::run(size, othersize, &actualLhs.coeffRef(0, 0),
110 actualLhs.outerStride(), &rhs.coeffRef(0, 0),
111 rhs.innerStride(), rhs.outerStride(), blocking);
112 }
113};
114
115/***************************************************************************
116 * meta-unrolling implementation
117 ***************************************************************************/
118
119template <typename Lhs, typename Rhs, int Mode, int LoopIndex, int Size, bool Stop = LoopIndex == Size>
120struct triangular_solver_unroller;
121
122template <typename Lhs, typename Rhs, int Mode, int LoopIndex, int Size>
123struct triangular_solver_unroller<Lhs, Rhs, Mode, LoopIndex, Size, false> {
124 enum {
125 IsLower = ((Mode & Lower) == Lower),
126 DiagIndex = IsLower ? LoopIndex : Size - LoopIndex - 1,
127 StartIndex = IsLower ? 0 : DiagIndex + 1
128 };
129 static EIGEN_DEVICE_FUNC void run(const Lhs& lhs, Rhs& rhs) {
130 if (LoopIndex > 0)
131 rhs.coeffRef(DiagIndex) -= lhs.row(DiagIndex)
132 .template segment<LoopIndex>(StartIndex)
133 .transpose()
134 .cwiseProduct(rhs.template segment<LoopIndex>(StartIndex))
135 .sum();
136
137 EIGEN_IF_CONSTEXPR (!(Mode & UnitDiag)) rhs.coeffRef(DiagIndex) /= lhs.coeff(DiagIndex, DiagIndex);
138
139 triangular_solver_unroller<Lhs, Rhs, Mode, LoopIndex + 1, Size>::run(lhs, rhs);
140 }
141};
142
143template <typename Lhs, typename Rhs, int Mode, int LoopIndex, int Size>
144struct triangular_solver_unroller<Lhs, Rhs, Mode, LoopIndex, Size, true> {
145 static EIGEN_DEVICE_FUNC void run(const Lhs&, Rhs&) {}
146};
147
148template <typename Lhs, typename Rhs, int Mode>
149struct triangular_solver_selector<Lhs, Rhs, OnTheLeft, Mode, CompleteUnrolling, 1> {
150 static EIGEN_DEVICE_FUNC void run(const Lhs& lhs, Rhs& rhs) {
151 triangular_solver_unroller<Lhs, Rhs, Mode, 0, Rhs::SizeAtCompileTime>::run(lhs, rhs);
152 }
153};
154
155template <typename Lhs, typename Rhs, int Mode>
156struct triangular_solver_selector<Lhs, Rhs, OnTheRight, Mode, CompleteUnrolling, 1> {
157 static EIGEN_DEVICE_FUNC void run(const Lhs& lhs, Rhs& rhs) {
158 Transpose<const Lhs> trLhs(lhs);
159 Transpose<Rhs> trRhs(rhs);
160
161 triangular_solver_unroller<Transpose<const Lhs>, Transpose<Rhs>,
162 ((Mode & Upper) == Upper ? Lower : Upper) | (Mode & UnitDiag), 0,
163 Rhs::SizeAtCompileTime>::run(trLhs, trRhs);
164 }
165};
166
167// What a triangular solve reads its matrix from: the view itself when it must be evaluated, which reads only the
168// triangle, or else its nested expression.
169template <bool EvalLhs>
170struct triangular_solve_lhs_source {
171 template <typename TriangularType>
172 EIGEN_DEVICE_FUNC static const TriangularType& run(const TriangularType& tri) {
173 return tri;
174 }
175};
176
177template <>
178struct triangular_solve_lhs_source<false> {
179 template <typename TriangularType>
180 EIGEN_DEVICE_FUNC static const typename TriangularType::NestedExpression& run(const TriangularType& tri) {
181 return tri.nestedExpression();
182 }
183};
184
185} // end namespace internal
186
187/***************************************************************************
188 * TriangularView methods
189 ***************************************************************************/
190
191#ifndef EIGEN_PARSED_BY_DOXYGEN
192template <typename MatrixType, unsigned int Mode>
193template <int Side, typename OtherDerived>
194EIGEN_DEVICE_FUNC void TriangularViewImpl<MatrixType, Mode, Dense>::solveInPlace(
195 const MatrixBase<OtherDerived>& _other) const {
196 OtherDerived& other = _other.const_cast_derived();
197 EIGEN_INTERNAL_ASSERT_SQUARE(derived());
198 // TODO(C++17): use if constexpr (Side == OnTheLeft) with PRODUCT_SHAPE/SAME_COLS checks directly.
199 EIGEN_INTERNAL_CHECK_SHAPE(
200 (Side == OnTheLeft ? derived().cols() == other.rows() : derived().cols() == other.cols()),
201 YOU_MIXED_MATRICES_OF_DIFFERENT_SIZES,
202 std::conditional_t<Side == OnTheLeft, internal::product_dimensions<MatrixType, OtherDerived>,
203 internal::matching_cols<MatrixType, OtherDerived>>);
204 eigen_assert((!(int(Mode) & int(ZeroDiag))) && bool(int(Mode) & (int(Upper) | int(Lower))));
205 // If solving for a 0x0 matrix, nothing to do, simply return.
206 if (derived().cols() == 0) return;
207
208 enum {
209 OtherFlags = internal::traits<OtherDerived>::Flags,
210 IsRowMajorVector =
211 (OtherFlags & RowMajorBit) && OtherDerived::IsVectorAtCompileTime && OtherDerived::SizeAtCompileTime != 1,
212 copy = IsRowMajorVector || ((OtherFlags & DirectAccessBit) == 0)
213 };
214 using OtherPlainObject =
215 std::conditional_t<IsRowMajorVector, typename internal::plain_matrix_type_column_major<OtherDerived>::type,
216 typename internal::plain_matrix_type<OtherDerived>::type>;
217 using OtherCopy = std::conditional_t<copy, OtherPlainObject, OtherDerived&>;
218 OtherCopy otherCopy(other);
219 using OtherCopyCleaned = std::remove_reference_t<OtherCopy>;
220
221 // The kernels read the matrix blas_traits extracts, without its scalar factor. A unit diagonal does not
222 // scale with that factor, so a scaled matrix is evaluated rather than its factor applied to the solution.
223 // Only the triangle is evaluated: the other coefficients, and an implicit unit diagonal, need not be readable.
224 // The unrolled solver reads the scaled coefficients itself and needs no evaluated copy.
225 constexpr bool EvalLhs =
226 internal::blas_traits<MatrixType>::HasScalarFactor &&
227 int(internal::trsolve_traits<MatrixType, OtherCopyCleaned, Side>::Unrolling) != int(CompleteUnrolling);
228 using Lhs = std::conditional_t<EvalLhs, typename MatrixType::PlainObject, MatrixType>;
229 std::conditional_t<EvalLhs, const Lhs, const MatrixType&> lhs(
230 internal::triangular_solve_lhs_source<EvalLhs>::run(derived()));
231
232 internal::triangular_solver_selector<Lhs, OtherCopyCleaned, Side, Mode>::run(lhs, otherCopy);
233
234 if (copy) other = otherCopy;
235}
236
237template <typename Derived, unsigned int Mode>
238template <int Side, typename Other>
239const internal::triangular_solve_retval<Side, TriangularView<Derived, Mode>, Other>
240TriangularViewImpl<Derived, Mode, Dense>::solve(const MatrixBase<Other>& other) const {
241 return internal::triangular_solve_retval<Side, TriangularViewType, Other>(derived(), other.derived());
242}
243#endif
244
245namespace internal {
246
247template <int Side, typename TriangularType, typename Rhs>
248struct traits<triangular_solve_retval<Side, TriangularType, Rhs> > {
249 using ReturnType = typename internal::plain_matrix_type_column_major<Rhs>::type;
250};
251
252template <int Side, typename TriangularType, typename Rhs>
253struct triangular_solve_retval : public ReturnByValue<triangular_solve_retval<Side, TriangularType, Rhs> > {
254 using Base = ReturnByValue<triangular_solve_retval>;
255
256 triangular_solve_retval(const TriangularType& tri, const Rhs& rhs) : m_triangularMatrix(tri), m_rhs(rhs) {}
257
258 constexpr Index rows() const noexcept { return m_rhs.rows(); }
259 constexpr Index cols() const noexcept { return m_rhs.cols(); }
260
261 template <typename Dest>
262 inline void evalTo(Dest& dst) const {
263 if (!is_same_dense(dst, m_rhs)) dst = m_rhs;
264 m_triangularMatrix.template solveInPlace<Side>(dst);
265 }
266
267 protected:
268 const TriangularType& m_triangularMatrix;
269 typename Rhs::Nested m_rhs;
270};
271
272} // namespace internal
273
274} // end namespace Eigen
275
276#endif // EIGEN_SOLVETRIANGULAR_H
@ ZeroDiag
Definition Constants.h:218
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
@ Aligned
Definition Constants.h:243
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321
@ OnTheLeft
Definition Constants.h:332
@ OnTheRight
Definition Constants.h:334
constexpr unsigned int DirectAccessBit
Definition Constants.h:160
constexpr unsigned int RowMajorBit
Definition Constants.h:71