11#ifndef EIGEN_TRIANGULARINPLACE_H
12#define EIGEN_TRIANGULARINPLACE_H
15#include "./InternalHeaderCheck.h"
36constexpr Index kTriangularInverseMinBlocked = 64;
37constexpr Index kTriangularInverseMinBlockSize = 24;
38constexpr Index kAdjointSquareMinBlocked = 128;
39constexpr Index kAdjointSquareMinBlockSize = 48;
41EIGEN_DEVICE_FUNC
inline Index triangular_in_place_block_size(Index size, Index min_block_size) {
42 const Index block_size = ((size / 8) / 8) * 8;
43 return numext::mini(numext::maxi(block_size, min_block_size), Index(128));
46template <
typename MatrixType>
47struct triangular_in_place_workspace {
48 using type = Matrix<
typename MatrixType::Scalar, Dynamic, Dynamic,
56template <
unsigned int Mode,
typename MatrixType,
typename VectorType>
57EIGEN_DEVICE_FUNC
void triangular_inverse_unblocked(MatrixType& mat, VectorType& tmp) {
58 using Scalar =
typename MatrixType::Scalar;
59 constexpr bool kUnitDiag = (Mode &
UnitDiag) != 0;
60 const Index n = mat.rows();
61 eigen_internal_assert(n < 2 || tmp.size() >= n - 1);
62 for (Index j = n - 1; j >= 0; --j) {
63 Scalar xj = Scalar(1);
64 EIGEN_IF_CONSTEXPR (!kUnitDiag) {
65 xj = Scalar(1) / mat.coeff(j, j);
66 mat.coeffRef(j, j) = xj;
68 const Index rs = n - j - 1;
69 if (rs == 0)
continue;
70 tmp.head(rs).noalias() = mat.block(j + 1, j + 1, rs, rs).template triangularView<Mode>() * mat.col(j).tail(rs);
71 mat.col(j).tail(rs) = -xj * tmp.head(rs);
77template <
unsigned int Mode,
typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime == 0,
int> = 0>
78EIGEN_DEVICE_FUNC
void triangular_inverse_lower(MatrixType&) {}
84template <
unsigned int Mode,
typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime != 0,
int> = 0>
85EIGEN_DEVICE_FUNC
void triangular_inverse_lower(MatrixType& mat) {
86 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
87 const Index n = mat.rows();
88 if (n < kTriangularInverseMinBlocked) {
89 using Scalar =
typename MatrixType::Scalar;
90 ei_declare_aligned_stack_constructed_variable(Scalar, tmp_data, numext::maxi(n, Index(1)), 0);
91 Map<Matrix<Scalar, Dynamic, 1> > tmp(tmp_data, n);
92 triangular_inverse_unblocked<Mode>(mat, tmp);
95 const Index block_size = triangular_in_place_block_size(n, kTriangularInverseMinBlockSize);
98 typename triangular_in_place_workspace<MatrixType>::type work(block_size, block_size);
99 for (Index k = ((n - 1) / block_size) * block_size; k >= 0; k -= block_size) {
100 const Index bs = numext::mini(block_size, n - k);
101 const Index rs = n - k - bs;
102 Block<MatrixType, Dynamic, Dynamic> L11(mat, k, k, bs, bs);
104 Block<MatrixType, Dynamic, Dynamic> L21(mat, k + bs, k, rs, bs);
105 Block<MatrixType, Dynamic, Dynamic> X22(mat, k + bs, k + bs, rs, rs);
108 for (Index r_end = rs; r_end > 0; r_end -= block_size) {
109 const Index r = numext::maxi(Index(0), r_end - block_size);
110 const Index h = r_end - r;
111 work.topLeftCorner(h, bs) = L21.middleRows(r, h);
112 L21.middleRows(r, h).noalias() =
113 X22.block(r, r, h, h).template triangularView<Mode>() * work.topLeftCorner(h, bs);
114 if (r > 0) L21.middleRows(r, h).noalias() += X22.block(r, 0, h, r) * L21.topRows(r);
116 L11.template triangularView<Mode>().template solveInPlace<OnTheRight>(L21);
119 auto tmp = work.col(0);
120 triangular_inverse_unblocked<Mode>(L11, tmp);
127template <
unsigned int Mode,
typename MatrixType,
typename VectorType>
128EIGEN_DEVICE_FUNC
void triangular_inverse_upper_unblocked(MatrixType& mat, VectorType& tmp) {
129 using Scalar =
typename MatrixType::Scalar;
130 constexpr bool kUnitDiag = (Mode &
UnitDiag) != 0;
131 const Index n = mat.rows();
132 eigen_internal_assert(n < 2 || tmp.size() >= n - 1);
133 for (Index j = 0; j < n; ++j) {
134 Scalar xj = Scalar(1);
135 EIGEN_IF_CONSTEXPR (!kUnitDiag) {
136 xj = Scalar(1) / mat.coeff(j, j);
137 mat.coeffRef(j, j) = xj;
139 if (j == 0)
continue;
140 tmp.head(j).noalias() = mat.topLeftCorner(j, j).template triangularView<Mode>() * mat.col(j).head(j);
141 mat.col(j).head(j) = -xj * tmp.head(j);
145template <
unsigned int Mode,
typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime == 0,
int> = 0>
146EIGEN_DEVICE_FUNC
void triangular_inverse_upper(MatrixType&) {}
151template <
unsigned int Mode,
typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime != 0,
int> = 0>
152EIGEN_DEVICE_FUNC
void triangular_inverse_upper(MatrixType& mat) {
153 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
154 const Index n = mat.rows();
155 if (n < kTriangularInverseMinBlocked) {
156 using Scalar =
typename MatrixType::Scalar;
157 ei_declare_aligned_stack_constructed_variable(Scalar, tmp_data, numext::maxi(n, Index(1)), 0);
158 Map<Matrix<Scalar, Dynamic, 1> > tmp(tmp_data, n);
159 triangular_inverse_upper_unblocked<Mode>(mat, tmp);
162 const Index block_size = triangular_in_place_block_size(n, kTriangularInverseMinBlockSize);
163 typename triangular_in_place_workspace<MatrixType>::type work(block_size, block_size);
164 for (Index k = 0; k < n; k += block_size) {
165 const Index bs = numext::mini(block_size, n - k);
166 Block<MatrixType, Dynamic, Dynamic> U22(mat, k, k, bs, bs);
168 Block<MatrixType, Dynamic, Dynamic> U12(mat, 0, k, k, bs);
169 Block<MatrixType, Dynamic, Dynamic> X11(mat, 0, 0, k, k);
172 for (Index r = 0; r < k; r += block_size) {
173 const Index h = numext::mini(block_size, k - r);
174 const Index below = k - r - h;
175 work.topLeftCorner(h, bs) = U12.middleRows(r, h);
176 U12.middleRows(r, h).noalias() =
177 X11.block(r, r, h, h).template triangularView<Mode>() * work.topLeftCorner(h, bs);
178 if (below > 0) U12.middleRows(r, h).noalias() += X11.block(r, r + h, h, below) * U12.bottomRows(below);
180 U22.template triangularView<Mode>().template solveInPlace<OnTheRight>(U12);
183 auto tmp = work.col(0);
184 triangular_inverse_upper_unblocked<Mode>(U22, tmp);
188template <
unsigned int Mode,
bool IsLower = (
int(Mode) &
int(Lower)) != 0>
189struct triangular_inverse_selector {
190 template <
typename MatrixType>
191 EIGEN_DEVICE_FUNC
static void run(MatrixType& mat) {
192 triangular_inverse_lower<Mode>(mat);
196template <
unsigned int Mode>
197struct triangular_inverse_selector<Mode, false> {
198 template <
typename MatrixType>
199 EIGEN_DEVICE_FUNC
static void run(MatrixType& mat) {
200 triangular_inverse_upper<Mode>(mat);
206template <
typename MatrixType>
207void triangular_adjoint_square_unblocked(MatrixType& mat) {
208 using Scalar =
typename MatrixType::Scalar;
209 const Index n = mat.rows();
210 for (Index i = 0; i < n; ++i) {
211 const Scalar lii = mat.coeff(i, i);
212 const Index rs = n - i - 1;
213 mat.coeffRef(i, i) = Scalar(mat.col(i).tail(n - i).squaredNorm());
215 mat.row(i).head(i) *= numext::conj(lii);
216 if (rs > 0) mat.row(i).head(i).noalias() += mat.col(i).tail(rs).adjoint() * mat.bottomLeftCorner(rs, i);
223template <
typename MatrixType>
224void triangular_adjoint_square_lower(MatrixType& mat) {
225 EIGEN_INTERNAL_ASSERT_SQUARE(mat);
226 const Index n = mat.rows();
227 if (n < kAdjointSquareMinBlocked) {
228 triangular_adjoint_square_unblocked(mat);
231 const Index block_size = triangular_in_place_block_size(n, kAdjointSquareMinBlockSize);
232 typename triangular_in_place_workspace<MatrixType>::type work(block_size, block_size);
233 for (Index k = 0; k < n; k += block_size) {
234 const Index bs = numext::mini(block_size, n - k);
235 const Index rs = n - k - bs;
236 Block<MatrixType, Dynamic, Dynamic> L11(mat, k, k, bs, bs);
240 Block<MatrixType, Dynamic, Dynamic> B(mat, k, 0, bs, k);
241 for (Index c = 0; c < k; c += block_size) {
242 const Index w = numext::mini(block_size, k - c);
243 work.topLeftCorner(bs, w) = B.middleCols(c, w);
244 B.middleCols(c, w).noalias() = L11.adjoint().template triangularView<Upper>() * work.topLeftCorner(bs, w);
246 if (rs > 0) B.noalias() += mat.block(k + bs, k, rs, bs).adjoint() * mat.block(k + bs, 0, rs, k);
248 triangular_adjoint_square_unblocked(L11);
250 L11.template selfadjointView<Lower>().rankUpdate(mat.block(k + bs, k, rs, bs).adjoint());
252 EIGEN_IF_CONSTEXPR (NumTraits<typename MatrixType::Scalar>::IsComplex) {
253 L11.diagonal() = L11.diagonal().real().template cast<typename MatrixType::Scalar>();
259template <
int UpLo,
bool IsLower = (
int(UpLo) &
int(Lower)) != 0>
260struct triangular_adjoint_square_selector {
261 template <
typename MatrixType>
262 static void run(MatrixType& mat) {
263 triangular_adjoint_square_lower(mat);
268struct triangular_adjoint_square_selector<UpLo, false> {
269 template <
typename MatrixType>
270 static void run(MatrixType& mat) {
271 Transpose<MatrixType> matt(mat);
272 triangular_adjoint_square_lower(matt);
279template <
int UpLo,
typename MatrixType>
280void triangular_adjoint_square_in_place(MatrixType& mat) {
281 triangular_adjoint_square_selector<UpLo>::run(mat);
286#ifndef EIGEN_PARSED_BY_DOXYGEN
287template <
typename MatrixType,
unsigned int Mode>
288EIGEN_DEVICE_FUNC
void TriangularViewImpl<MatrixType, Mode, Dense>::inverseInPlace() {
289 EIGEN_STATIC_ASSERT_LVALUE(MatrixType)
290 EIGEN_STATIC_ASSERT((
int(Mode) &
int(
Upper |
Lower)) != 0 && (
int(Mode) &
int(
ZeroDiag)) == 0, PROGRAMMING_ERROR)
291 EIGEN_INTERNAL_ASSERT_SQUARE(derived());
292 internal::triangular_inverse_selector<Mode>::run(derived().nestedExpression());
@ 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