Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
TriangularInPlace.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2026 Rasmus Munk Larsen <rmlarsen@gmail.com>
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_TRIANGULARINPLACE_H
12#define EIGEN_TRIANGULARINPLACE_H
13
14// IWYU pragma: private
15#include "./InternalHeaderCheck.h"
16
17namespace Eigen {
18
19namespace internal {
20
21// In-place counterparts of LAPACK xTRTRI and xLAUUM. Each overwrites its operand; the only scratch is
22// one block-sized panel, at most 128x128 elements whatever the matrix size, through which the in-place
23// TRMM steps run Eigen's blocked kernel, the same way optimized BLAS implement xTRMM.
24
25// Each triangle runs its column recurrence from xTRTI2/xTRTRI, which bounds the right residual
26// |X T - I| <= c_n u |X||T| (Higham, ASNA 2nd ed., 14.2-14.3). Inverses built from it, as in xPOTRI and
27// xGETRI, rely on that bound. For LLT<Upper>, |X U - I| is the left residual of L = U^*, as in xPOTRI 'U'.
28// Intermediate products overflow in the order of the recurrence, as in xTRTRI. The self-adjoint square exists only
29// for the lower triangle; the upper one runs it on V = U^T, since V^* V = conj(U U^*) = (U U^*)^T.
30
31// Both kernels have the panel-times-trailing-block shape of the Cholesky factorization, so the block
32// size tracks llt_inplace::blocked(), but each has its own floor and its own size below which the
33// unblocked form still wins: TRTRI's blocked step is a TRMM plus a TRSM against a bs-wide panel, and
34// its unblocked form is already a sequence of TRMVs, while LAUUM's is a TRMM plus a HERK and its
35// unblocked form is a sequence of GEMVs against a strided row. Measured on Zen 4 at n = 32..512.
36constexpr Index kTriangularInverseMinBlocked = 64;
37constexpr Index kTriangularInverseMinBlockSize = 24;
38constexpr Index kAdjointSquareMinBlocked = 128;
39constexpr Index kAdjointSquareMinBlockSize = 48;
40
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));
44}
45
46template <typename MatrixType>
47struct triangular_in_place_workspace {
48 using type = Matrix<typename MatrixType::Scalar, Dynamic, Dynamic,
49 (int(traits<MatrixType>::Flags) & RowMajorBit) ? RowMajor : ColMajor>;
50};
51
52// Unblocked lower triangular inverse, columns bottom-up so that the trailing block already holds
53// X22 = L22^-1 when column j is reached: then X(j+1:, j) = -X22 L(j+1:, j) / L(j, j), one TRMV per
54// column rather than the chain of AXPYs a forward substitution per column would run. \a tmp is
55// scratch of at least n - 1 entries, since the TRMV's destination is its own operand.
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;
67 }
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);
72 }
73}
74
75// With a zero-sized fixed dimension there is nothing to invert, and col() is not a vector, so the kernels' column
76// tails would not compile.
77template <unsigned int Mode, typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime == 0, int> = 0>
78EIGEN_DEVICE_FUNC void triangular_inverse_lower(MatrixType&) {}
79
80// Blocked lower triangular inverse, block columns bottom-up as in LAPACK xTRTRI. With
81// L = [[L11, 0], [L21, L22]] the inverse is [[L11^-1, 0], [-L22^-1 L21 L11^-1, L22^-1]]; walking upwards
82// makes X22 = L22^-1 available first, so the large operation is the TRMM X22 L21 rather than a solve
83// against L22, and Eigen's TRMM runs closer to GEMM rate than its TRSM does on a 128-column operand.
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);
93 return;
94 }
95 const Index block_size = triangular_in_place_block_size(n, kTriangularInverseMinBlockSize);
96 // One block-sized panel, whose first column doubles as the TRMV scratch of the unblocked kernel:
97 // that kernel runs on L11 only after the panel's other uses in the same iteration are finished.
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);
103 if (rs > 0) {
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);
106 // L21 <- X22 L21. Row panel r of the product reads only rows <= r of L21, so going upwards
107 // leaves every row a later panel still needs untouched.
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);
115 }
116 L11.template triangularView<Mode>().template solveInPlace<OnTheRight>(L21);
117 L21 = -L21;
118 }
119 auto tmp = work.col(0);
120 triangular_inverse_unblocked<Mode>(L11, tmp);
121 }
122}
123
124// Unblocked upper triangular inverse, columns left to right as in xTRTI2 so that the leading block already holds
125// X11 = U11^-1 when column j is reached: X(0:j, j) = -X11 U(0:j, j) / U(j, j), one TRMV per column. \a tmp is
126// scratch of at least n - 1 entries.
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;
138 }
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);
142 }
143}
144
145template <unsigned int Mode, typename MatrixType, std::enable_if_t<MatrixType::SizeAtCompileTime == 0, int> = 0>
146EIGEN_DEVICE_FUNC void triangular_inverse_upper(MatrixType&) {}
147
148// Blocked upper triangular inverse, block columns left to right as in LAPACK xTRTRI. With
149// U = [[U11, U12], [0, U22]] the inverse is [[U11^-1, -U11^-1 U12 U22^-1], [0, U22^-1]]; walking rightwards
150// makes X11 = U11^-1 available first, so as for the lower kernel the large operation is the TRMM X11 U12.
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);
160 return;
161 }
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);
167 if (k > 0) {
168 Block<MatrixType, Dynamic, Dynamic> U12(mat, 0, k, k, bs);
169 Block<MatrixType, Dynamic, Dynamic> X11(mat, 0, 0, k, k);
170 // U12 <- X11 U12. Row panel r of the product reads only rows >= r of U12, so going downwards
171 // leaves every row a later panel still needs untouched.
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);
179 }
180 U22.template triangularView<Mode>().template solveInPlace<OnTheRight>(U12);
181 U12 = -U12;
182 }
183 auto tmp = work.col(0);
184 triangular_inverse_upper_unblocked<Mode>(U22, tmp);
185 }
186}
187
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);
193 }
194};
195
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);
201 }
202};
203
204// Unblocked lower self-adjoint square: mat <- lower(L^* L). Row i of the result reads column i of L
205// below the diagonal and rows > i of the columns left of it, none of which row i's own update writes.
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());
214 if (i > 0) {
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);
217 }
218 }
219}
220
221// Blocked lower self-adjoint square, left-looking as in LAPACK xLAUUM: block row k of the result is
222// completed against the columns to its left before the trailing block rows consume the factor.
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);
229 return;
230 }
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);
237 if (k > 0) {
238 // A(k:k+bs, 0:k) = sum over rows m >= k of L(m, k:k+bs)^* L(m, 0:k), split at m = k+bs. The
239 // first part is the TRMM L11^* B in place, done by column panels through the workspace.
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);
245 }
246 if (rs > 0) B.noalias() += mat.block(k + bs, k, rs, bs).adjoint() * mat.block(k + bs, 0, rs, k);
247 }
248 triangular_adjoint_square_unblocked(L11);
249 if (rs > 0) {
250 L11.template selfadjointView<Lower>().rankUpdate(mat.block(k + bs, k, rs, bs).adjoint());
251 // Fused complex products can leave a rounding residual in the imaginary diagonal.
252 EIGEN_IF_CONSTEXPR (NumTraits<typename MatrixType::Scalar>::IsComplex) {
253 L11.diagonal() = L11.diagonal().real().template cast<typename MatrixType::Scalar>();
254 }
255 }
256 }
257}
258
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);
264 }
265};
266
267template <int UpLo>
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);
273 }
274};
275
279template <int UpLo, typename MatrixType>
280void triangular_adjoint_square_in_place(MatrixType& mat) {
281 triangular_adjoint_square_selector<UpLo>::run(mat);
282}
283
284} // end namespace internal
285
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());
293}
294#endif
295
296} // end namespace Eigen
297
298#endif // EIGEN_TRIANGULARINPLACE_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