NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
ldl.hpp
Go to the documentation of this file.
1
8#ifndef NUMERICAL_LDL_HPP
9#define NUMERICAL_LDL_HPP
10
11#include <cmath>
12#include <complex>
13#include <concepts>
14#include <cstddef>
15#include <numeric>
16#include <utility>
17#include <vector>
18
19#include "factorizations.hpp"
20
21namespace numerical {
22
23 namespace detail {
24
26 [[nodiscard]] inline double pivot_size(double x)
27 {
28 return std::abs(x);
29 }
30
32 [[nodiscard]] inline double pivot_size(const std::complex<double>& z)
33 {
34 return std::abs(z.real()) + std::abs(z.imag());
35 }
36
38 [[nodiscard]] inline double diagonal_size(double x,
39 bool /*hermitian*/)
40 {
41 return std::abs(x);
42 }
43
46 [[nodiscard]] inline double diagonal_size(const std::complex<double>& z,
47 bool hermitian)
48 {
49 return hermitian ? std::abs(z.real()) : pivot_size(z);
50 }
51
53 [[nodiscard]] inline double conjugated_if(double x,
54 bool /*hermitian*/)
55 {
56 return x;
57 }
58
60 [[nodiscard]] inline std::complex<double> conjugated_if(const std::complex<double>& z,
61 bool hermitian)
62 {
63 return hermitian ? std::conj(z) : z;
64 }
65
67 [[nodiscard]] inline double diagonal_kept(double x,
68 bool /*hermitian*/)
69 {
70 return x;
71 }
72
75 [[nodiscard]] inline std::complex<double> diagonal_kept(const std::complex<double>& z,
76 bool hermitian)
77 {
78 return hermitian ? std::complex<double> {z.real()} : z;
79 }
80
87 template <typename T>
89 std::size_t n,
90 std::size_t k,
91 buffer<T>& w)
92 {
93 const T r {T {1.0} / a[(k * n) + k]};
94 for (std::size_t j {k + 1}; j < n; ++j) {
95 w[j] = -r * a[(j * n) + k];
96 }
97 for (std::size_t i {k + 1}; i < n; ++i) {
98 const T x {a[(i * n) + k]};
99 T* const row {a.data() + (i * n)};
100 for (std::size_t j {k + 1}; j <= i; ++j) {
101 row[j] += x * w[j];
102 }
103 row[k] = x * r;
104 }
105 }
106
109 inline void hermitian_rank_one(buffer<std::complex<double>>& a,
110 std::size_t n,
111 std::size_t k,
112 buffer<std::complex<double>>& w)
113 {
114 using C = std::complex<double>;
115 const double r {1.0 / a[(k * n) + k].real()};
116 for (std::size_t j {k + 1}; j < n; ++j) {
117 w[j] = -r * std::conj(a[(j * n) + k]);
118 }
119 for (std::size_t i {k + 1}; i < n; ++i) {
120 const C x {a[(i * n) + k]};
121 C* const row {a.data() + (i * n)};
122 for (std::size_t j {k + 1}; j < i; ++j) {
123 row[j] += x * w[j];
124 }
125 row[i] = C {row[i].real() + (x * w[i]).real()};
126 row[k] = x * r;
127 }
128 }
129
136 template <typename T>
138 std::size_t n,
139 std::size_t k,
140 buffer<T>& w)
141 {
142 const T d21 {a[((k + 1) * n) + k]};
143 const T d11 {a[((k + 1) * n) + k + 1] / d21};
144 const T d22 {a[(k * n) + k] / d21};
145 const T t {T {1.0} / ((d11 * d22) - T {1.0})};
146 for (std::size_t j {k + 2}; j < n; ++j) {
147 w[2 * j] = t * (((d11 * a[(j * n) + k]) - a[(j * n) + k + 1]) / d21);
148 w[(2 * j) + 1] = t * (((d22 * a[(j * n) + k + 1]) - a[(j * n) + k]) / d21);
149 }
150 for (std::size_t i {k + 2}; i < n; ++i) {
151 T* const row {a.data() + (i * n)};
152 const T x {row[k]};
153 const T y {row[k + 1]};
154 for (std::size_t j {k + 2}; j <= i; ++j) {
155 row[j] = row[j] - (x * w[2 * j]) - (y * w[(2 * j) + 1]);
156 }
157 row[k] = w[2 * i];
158 row[k + 1] = w[(2 * i) + 1];
159 }
160 }
161
164 inline void hermitian_rank_two(buffer<std::complex<double>>& a,
165 std::size_t n,
166 std::size_t k,
167 buffer<std::complex<double>>& w)
168 {
169 using C = std::complex<double>;
170 const C below {a[((k + 1) * n) + k]};
171 const double d {std::hypot(below.real(), below.imag())};
172 const double d11 {a[((k + 1) * n) + k + 1].real() / d};
173 const double d22 {a[(k * n) + k].real() / d};
174 const double t {1.0 / ((d11 * d22) - 1.0)};
175 const C d21 {below / d};
176 for (std::size_t j {k + 2}; j < n; ++j) {
177 w[2 * j] = t * (((d11 * a[(j * n) + k]) - (d21 * a[(j * n) + k + 1])) / d);
178 w[(2 * j) + 1] = t * (((d22 * a[(j * n) + k + 1]) - (std::conj(d21) * a[(j * n) + k])) / d);
179 }
180 for (std::size_t i {k + 2}; i < n; ++i) {
181 C* const row {a.data() + (i * n)};
182 const C x {row[k]};
183 const C y {row[k + 1]};
184 for (std::size_t j {k + 2}; j <= i; ++j) {
185 row[j] = row[j] - (x * std::conj(w[2 * j])) - (y * std::conj(w[(2 * j) + 1]));
186 }
187 row[k] = w[2 * i];
188 row[k + 1] = w[(2 * i) + 1];
189 row[i] = C {row[i].real()};
190 }
191 }
192
195 std::size_t n,
196 std::size_t k,
197 std::size_t step,
198 bool /*hermitian*/,
200 {
201 if (step == 1) {
202 symmetric_rank_one(a, n, k, w);
203 }
204 else {
205 symmetric_rank_two(a, n, k, w);
206 }
207 }
208
210 inline void eliminate_pivot(buffer<std::complex<double>>& a,
211 std::size_t n,
212 std::size_t k,
213 std::size_t step,
214 bool hermitian,
215 buffer<std::complex<double>>& w)
216 {
217 if (step == 1) {
218 if (hermitian) {
219 hermitian_rank_one(a, n, k, w);
220 }
221 else {
222 symmetric_rank_one(a, n, k, w);
223 }
224 }
225 else if (hermitian) {
226 hermitian_rank_two(a, n, k, w);
227 }
228 else {
229 symmetric_rank_two(a, n, k, w);
230 }
231 }
232
245 template <typename T>
246 [[nodiscard]] std::vector<std::ptrdiff_t> bunch_kaufman_lower(buffer<T>& a,
247 std::size_t n,
248 bool hermitian,
249 bool last_on_ties,
250 std::size_t from = 0)
251 {
252 const double alpha {(1.0 + std::sqrt(17.0)) / 8.0};
253 std::vector<std::ptrdiff_t> pivots(n);
254 buffer<T> w(2 * n); // the rank updates' factors
255 const auto at = [&a, n](std::size_t i, std::size_t j) -> T& { return a[(i * n) + j]; };
256 for (std::size_t k {from}; k < n;) {
257 std::size_t step {1};
258 std::size_t pivot {k};
259 const double absakk {diagonal_size(at(k, k), hermitian)};
260 std::size_t imax {k};
261 double colmax {0.0};
262 for (std::size_t i {k + 1}; i < n; ++i) {
263 const double size {pivot_size(at(i, k))};
264 if (size > colmax || (last_on_ties && size == colmax && i > k + 1)) {
265 colmax = size;
266 imax = i;
267 }
268 }
269 if (std::max(absakk, colmax) == 0.0 || std::isnan(absakk)) { // a zero (or NaN) column: no elimination
270 at(k, k) = diagonal_kept(at(k, k), hermitian);
271 }
272 else {
273 if (absakk < alpha * colmax) {
274 double rowmax {0.0}; // the largest entry of row and column imax off the diagonal
275 for (std::size_t j {k}; j < imax; ++j) {
276 rowmax = std::max(rowmax, pivot_size(at(imax, j)));
277 }
278 for (std::size_t i {imax + 1}; i < n; ++i) {
279 rowmax = std::max(rowmax, pivot_size(at(i, imax)));
280 }
281 if (absakk < alpha * colmax * (colmax / rowmax)) {
282 pivot = imax;
283 step = diagonal_size(at(imax, imax), hermitian) >= alpha * rowmax ? 1 : 2;
284 }
285 }
286 const std::size_t kk {k + step - 1};
287 if (pivot != kk) { // rows and columns kk and pivot exchanged in the lower triangle
288 for (std::size_t i {pivot + 1}; i < n; ++i) {
289 std::swap(at(i, kk), at(i, pivot));
290 }
291 for (std::size_t j {kk + 1}; j < pivot; ++j) {
292 const T t {conjugated_if(at(j, kk), hermitian)};
293 at(j, kk) = conjugated_if(at(pivot, j), hermitian);
294 at(pivot, j) = t;
295 }
296 at(pivot, kk) = conjugated_if(at(pivot, kk), hermitian);
297 const T t {diagonal_kept(at(kk, kk), hermitian)};
298 at(kk, kk) = diagonal_kept(at(pivot, pivot), hermitian);
299 at(pivot, pivot) = t;
300 if (step == 2) {
301 at(k, k) = diagonal_kept(at(k, k), hermitian);
302 std::swap(at(k + 1, k), at(pivot, k));
303 }
304 }
305 else {
306 at(k, k) = diagonal_kept(at(k, k), hermitian);
307 at(kk, kk) = diagonal_kept(at(kk, kk), hermitian);
308 }
309 eliminate_pivot(a, n, k, step, hermitian, w);
310 }
311 const auto origin {static_cast<std::ptrdiff_t>(pivot + 1)};
312 pivots[k] = step == 1 ? origin : -origin;
313 if (step == 2) {
314 pivots[k + 1] = -origin;
315 }
316 k += step;
317 }
318 return pivots;
319 }
320
323 inline constexpr std::size_t ldl_block {64};
324
329 inline constexpr std::size_t ldl_blocked_least {384};
330
340 template <typename T>
342 std::size_t n,
343 std::size_t k0,
344 bool hermitian,
345 bool last_on_ties,
346 buffer<T>& w,
347 std::vector<std::ptrdiff_t>& pivots)
348 {
349 const double alpha {(1.0 + std::sqrt(17.0)) / 8.0};
350 const auto at = [&a, n](std::size_t i, std::size_t j) -> T& { return a[(i * n) + j]; };
351 const auto wt = [&w](std::size_t i, std::size_t j) -> T& { return w[(i * ldl_block) + j]; };
352 // column c of W (rows from k) less the panel's columns before kw: A(i, k0 + p) W(r, p)ᴴ, r the row whose W is read
353 const auto bring_up = [&](std::size_t k, std::size_t c, std::size_t r, std::size_t kw) {
354 for (std::size_t i {k}; i < n; ++i) {
355 T sum {wt(i, c)};
356 for (std::size_t p {0}; p < kw; ++p) {
357 sum -= at(i, k0 + p) * conjugated_if(wt(r, p), hermitian);
358 }
359 wt(i, c) = sum;
360 }
361 };
362 std::size_t k {k0};
363 while (k - k0 + 1 < ldl_block) { // called with more than ldl_block columns left: k + 1 < n throughout
364 const std::size_t kw {k - k0};
365 for (std::size_t i {k}; i < n; ++i) {
366 wt(i, kw) = at(i, k);
367 }
368 wt(k, kw) = diagonal_kept(wt(k, kw), hermitian);
369 bring_up(k, kw, k, kw);
370 wt(k, kw) = diagonal_kept(wt(k, kw), hermitian);
371 std::size_t step {1};
372 std::size_t pivot {k};
373 const double absakk {diagonal_size(wt(k, kw), hermitian)};
374 std::size_t imax {k};
375 double colmax {0.0};
376 for (std::size_t i {k + 1}; i < n; ++i) {
377 const double size {pivot_size(wt(i, kw))};
378 if (size > colmax || (last_on_ties && size == colmax && i > k + 1)) {
379 colmax = size;
380 imax = i;
381 }
382 }
383 if (std::max(absakk, colmax) == 0.0 || std::isnan(absakk)) { // a zero (or NaN) column: no elimination
384 for (std::size_t i {k}; i < n; ++i) {
385 at(i, k) = wt(i, kw);
386 }
387 }
388 else {
389 if (absakk < alpha * colmax) { // column imax brought up to date into W's next column
390 for (std::size_t j {k}; j < imax; ++j) {
391 wt(j, kw + 1) = conjugated_if(at(imax, j), hermitian);
392 }
393 for (std::size_t i {imax}; i < n; ++i) {
394 wt(i, kw + 1) = at(i, imax);
395 }
396 wt(imax, kw + 1) = diagonal_kept(wt(imax, kw + 1), hermitian);
397 bring_up(k, kw + 1, imax, kw);
398 wt(imax, kw + 1) = diagonal_kept(wt(imax, kw + 1), hermitian);
399 double rowmax {0.0}; // the largest entry of row and column imax off the diagonal
400 for (std::size_t i {k}; i < n; ++i) {
401 if (i != imax) {
402 rowmax = std::max(rowmax, pivot_size(wt(i, kw + 1)));
403 }
404 }
405 if (absakk < alpha * colmax * (colmax / rowmax)) {
406 pivot = imax;
407 if (diagonal_size(wt(imax, kw + 1), hermitian) >= alpha * rowmax) {
408 for (std::size_t i {k}; i < n; ++i) {
409 wt(i, kw) = wt(i, kw + 1);
410 }
411 }
412 else {
413 step = 2;
414 }
415 }
416 }
417 const std::size_t kk {k + step - 1};
418 if (pivot != kk) { // the trailing block's rows and columns kk and pivot exchanged, and L's and W's rows
419 at(pivot, pivot) = diagonal_kept(at(kk, kk), hermitian);
420 for (std::size_t j {kk + 1}; j < pivot; ++j) {
421 at(pivot, j) = conjugated_if(at(j, kk), hermitian);
422 }
423 for (std::size_t i {pivot + 1}; i < n; ++i) {
424 at(i, pivot) = at(i, kk);
425 }
426 for (std::size_t j {k0}; j < kk; ++j) { // the panel's columns of L: its updates read them so
427 std::swap(at(kk, j), at(pivot, j));
428 }
429 for (std::size_t j {0}; j <= kk - k0; ++j) {
430 std::swap(wt(kk, j), wt(pivot, j));
431 }
432 }
433 if (step == 1) { // L's column: W's over its diagonal, D's entry on it
434 for (std::size_t i {k}; i < n; ++i) {
435 at(i, k) = wt(i, kw);
436 }
437 const T r {T {1.0} / at(k, k)};
438 for (std::size_t i {k + 1}; i < n; ++i) {
439 at(i, k) *= r;
440 }
441 }
442 else { // L's two columns: W D⁻¹, D21 scaled out
443 const T d21 {wt(k + 1, kw)};
444 const T d11 {wt(k + 1, kw + 1) / d21};
445 const T d22 {wt(k, kw) / conjugated_if(d21, hermitian)};
446 const T t {T {1.0} / ((hermitian ? T {real_part(d11 * d22)} : d11 * d22) - T {1.0})}; // real for a Hermitian D
447 const T s {t / d21};
448 for (std::size_t j {k + 2}; j < n; ++j) {
449 at(j, k) = conjugated_if(s, hermitian) * ((d11 * wt(j, kw)) - wt(j, kw + 1));
450 at(j, k + 1) = s * ((d22 * wt(j, kw + 1)) - wt(j, kw));
451 }
452 at(k, k) = wt(k, kw);
453 at(k + 1, k) = wt(k + 1, kw);
454 at(k + 1, k + 1) = wt(k + 1, kw + 1);
455 }
456 }
457 const auto origin {static_cast<std::ptrdiff_t>(pivot + 1)};
458 pivots[k] = step == 1 ? origin : -origin;
459 if (step == 2) {
460 pivots[k + 1] = -origin;
461 }
462 k += step;
463 }
464 return k;
465 }
466
475 template <typename T>
476 [[nodiscard]] std::vector<std::ptrdiff_t> bunch_kaufman_blocked_lower(buffer<T>& a,
477 std::size_t n,
478 bool hermitian,
479 bool last_on_ties)
480 {
481 std::vector<std::ptrdiff_t> pivots(n);
482 buffer<T> w(n * ldl_block);
485 std::size_t k0 {0};
486 while (n - k0 > ldl_block) { // as sytrf: panels while more than one remains, then sytf2's steps
487 const std::size_t end {factor_ldl_panel(a, n, k0, hermitian, last_on_ties, w, pivots)};
488 const std::size_t rest {n - end};
489 const std::size_t depth {end - k0};
490 // A₂₂ −= L₂₁ W₂₁ᴴ on its lower triangle, [−L₂₁] [W₂₁ᴴ]: a panel leaves columns after it
491 left.resize(rest * depth);
492 right.resize(depth * rest);
493 for (std::size_t i {0}; i < rest; ++i) {
494 for (std::size_t p {0}; p < depth; ++p) {
495 left[(i * depth) + p] = -a[((end + i) * n) + k0 + p];
496 right[(p * rest) + i] = conjugated_if(w[((end + i) * ldl_block) + p], hermitian);
497 }
498 }
499 T * trailing {a.data() + (end * n) + end};
500 bool done {false};
501 if constexpr (std::is_same_v<T, double>) {
502 static_assert(ldl_block - 1 >= gemm_min_depth, "a panel is deep enough for the product's kernel");
503 if (rest * rest >= ((gemm_packed_threshold + depth) - 1) / depth) {
504 gemm_triangle<a_rows, b_rows>(rest, depth, left.data(), depth, right.data(), rest, trailing, n, true);
505 done = true;
506 }
507 }
508 for (std::size_t r0 {0}; !done && r0 < rest; r0 += ldl_block) {
509 const std::size_t rows {std::min(ldl_block, rest - r0)};
510 gemm(rows, r0 + rows, depth, left.data() + (r0 * depth), depth, right.data(), rest, trailing + (r0 * n), n);
511 }
512 if (hermitian) { // the diagonal real, as hetrf keeps it
513 for (std::size_t i {0}; i < rest; ++i) {
514 trailing[(i * n) + i] = diagonal_kept(trailing[(i * n) + i], true);
515 }
516 }
517 // L's panel columns as the steps one by one leave them (ipiv's form): each exchange undone in the columns
518 // before its step, last first
519 auto j {static_cast<std::ptrdiff_t>(end) - 1};
520 while (j > static_cast<std::ptrdiff_t>(k0)) {
521 const auto jj {static_cast<std::size_t>(j)};
522 const std::size_t jp {static_cast<std::size_t>(std::abs(pivots[jj])) - 1};
523 j -= pivots[jj] < 0 ? 2 : 1;
524 if (jp != jj && j >= static_cast<std::ptrdiff_t>(k0)) {
525 for (std::size_t c {k0}; c <= static_cast<std::size_t>(j); ++c) {
526 std::swap(a[(jp * n) + c], a[(jj * n) + c]);
527 }
528 }
529 }
530 k0 = end;
531 }
532 std::vector<std::ptrdiff_t> tail {bunch_kaufman_lower(a, n, hermitian, last_on_ties, k0)};
533 std::copy(tail.begin() + static_cast<std::ptrdiff_t>(k0), tail.end(), pivots.begin() + static_cast<std::ptrdiff_t>(k0));
534 return pivots;
535 }
536 } // namespace detail
537
547 template <double_field T>
549 {
550 public:
551
561 explicit ldl_decomposition(const matrix<T>& a,
562 bool lower = true,
563 bool hermitian = true)
564 : n_(a.rows())
565 {
566 if (a.cols() != n_) {
567 throw dimension_error("ldl requires a square matrix");
568 }
569 detail::require_finite(a, "ldl");
570 const std::size_t n {n_};
571 buffer<T> w(n * n);
572 for (std::size_t i {0}; i < n; ++i) { // the upper triangle reversed, J A J, is a lower one searched backwards
573 for (std::size_t j {0}; j < n; ++j) {
574 w[(i * n) + j] = lower ? a(i, j) : a(n - 1 - i, n - 1 - j);
575 }
576 }
577 std::vector<std::ptrdiff_t> found {n >= detail::ldl_blocked_least ? detail::bunch_kaufman_blocked_lower(w, n, hermitian, !lower)
578 : detail::bunch_kaufman_lower(w, n, hermitian, !lower)};
579 buffer<T> ldu(n * n);
580 std::vector<std::ptrdiff_t> ipiv(n);
581 for (std::size_t i {0}; i < n; ++i) {
582 for (std::size_t j {0}; j < n; ++j) {
583 ldu[(i * n) + j] = lower ? w[(i * n) + j] : w[((n - 1 - i) * n) + (n - 1 - j)];
584 }
585 const std::ptrdiff_t p {lower ? found[i] : found[n - 1 - i]};
586 const std::ptrdiff_t row {lower ? std::abs(p) : static_cast<std::ptrdiff_t>(n) + 1 - std::abs(p)};
587 ipiv[i] = p > 0 ? row : -row;
588 }
589 shape(ldu, ipiv, lower, hermitian);
590 }
591
594 {
595 return l_;
596 }
597
600 {
601 return d_;
602 }
603
605 [[nodiscard]] const std::vector<std::size_t>& permutation() const noexcept
606 {
607 return permutation_;
608 }
609
610 private:
611
616 void shape(const buffer<T>& ldu,
617 const std::vector<std::ptrdiff_t>& ipiv,
618 bool lower,
619 bool hermitian)
620 {
621 const std::size_t n {n_};
622 std::vector<std::size_t> swaps(n);
623 std::vector<int> blocks(n, 0);
624 std::iota(swaps.begin(), swaps.end(), std::size_t {0});
625 // the swaps and the blocks' orders, read from the first row of each block (the last for the upper triangle)
626 for (std::size_t visited {0}; visited < n;) {
627 const std::size_t index {lower ? visited : n - 1 - visited};
628 const std::ptrdiff_t value {ipiv[index]};
629 if (value > 0) {
630 swaps[index] = swaps[static_cast<std::size_t>(value - 1)];
631 blocks[index] = 1;
632 ++visited;
633 continue;
634 }
635 // a block of order 2 never starts on the last row it is read from, so the partner row exists; at() lets a
636 // compiler that inlines a matrix of order 1 see it as well
637 const std::size_t partner {lower ? index + 1 : index - 1};
638 swaps.at(partner) = swaps[static_cast<std::size_t>(-value - 1)];
639 blocks[lower ? index : partner] = 2;
640 visited += 2;
641 }
642 buffer<T> d(n * n, T {});
643 buffer<T> l(n * n, T {});
644 for (std::size_t i {0}; i < n; ++i) {
645 d[(i * n) + i] = ldu[(i * n) + i];
646 l[(i * n) + i] = T {1.0};
647 for (std::size_t j {0}; j < n; ++j) {
648 if (lower ? j < i : j > i) {
649 l[(i * n) + j] = ldu[(i * n) + j];
650 }
651 }
652 }
653 for (std::size_t start {0}; start < n;) { // a block of order 2: its off-diagonal entry into D, out of L
654 const int order {blocks[start]}; // a block's order is marked on its first row, the second row's 0
655 if (order == 2) {
656 const std::size_t below {start + 1};
657 const T entry {lower ? ldu[(below * n) + start] : ldu[(start * n) + below]};
658 d[(below * n) + start] = lower ? entry : detail::conjugated_if(entry, hermitian);
659 d[(start * n) + below] = lower ? detail::conjugated_if(entry, hermitian) : entry;
660 l[lower ? (below * n) + start : (start * n) + below] = T {};
661 }
662 start += static_cast<std::size_t>(order);
663 }
664 std::vector<std::size_t> order(n);
665 std::iota(order.begin(), order.end(), std::size_t {0});
666 for (std::size_t visited {0}; visited < n; ++visited) { // the swaps applied to L's rows, as SciPy reads them
667 const std::size_t index {lower ? n - 1 - visited : visited};
668 const std::size_t target {swaps[index]};
669 if (target == index) {
670 continue;
671 }
672 std::size_t first {lower ? index : 0};
673 std::size_t last {lower ? n : index + 1};
674 if (blocks[index] == (lower ? 0 : 2)) { // the second row of a block of order 2: both its columns
675 first -= lower ? 1 : 0;
676 last += lower ? 0 : 1;
677 }
678 for (std::size_t j {first}; j < last; ++j) {
679 std::swap(l[(target * n) + j], l[(index * n) + j]);
680 }
681 std::swap(order[target], order[index]);
682 }
683 permutation_.assign(n, 0);
684 for (std::size_t i {0}; i < n; ++i) { // argsort of a permutation: its inverse
685 permutation_[order[i]] = i;
686 }
687 l_ = matrix<T> {n, n, std::move(l)};
688 d_ = matrix<T> {n, n, std::move(d)};
689 }
690
691 std::size_t n_;
694 std::vector<std::size_t> permutation_;
695 };
696} // namespace numerical
697
698#endif // NUMERICAL_LDL_HPP
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
The symmetric indefinite factorisation of a symmetric or Hermitian matrix, as scipy....
Definition ldl.hpp:549
matrix< T > l_
L, permuted.
Definition ldl.hpp:692
std::vector< std::size_t > permutation_
The rows' order making L triangular.
Definition ldl.hpp:694
void shape(const buffer< T > &ldu, const std::vector< std::ptrdiff_t > &ipiv, bool lower, bool hermitian)
L, D and the permutation from LAPACK's packed factors ldu and ipiv, as SciPy's _ldl_sanitize_ipiv,...
Definition ldl.hpp:616
const std::vector< std::size_t > & permutation() const noexcept
The rows' order that makes factor triangular (SciPy's perm).
Definition ldl.hpp:605
const matrix< T > & d() const noexcept
D, block diagonal (blocks of order 1 and 2).
Definition ldl.hpp:599
const matrix< T > & factor() const noexcept
L, permuted (SciPy's lu): L[permutation()] is triangular with a unit diagonal.
Definition ldl.hpp:593
ldl_decomposition(const matrix< T > &a, bool lower=true, bool hermitian=true)
Factorises a, of which only the triangle lower names is read.
Definition ldl.hpp:561
std::size_t n_
The order.
Definition ldl.hpp:691
A dense, row-major matrix of T with value semantics.
Definition matrix.hpp:36
std::size_t cols() const noexcept
The number of columns.
Definition matrix.hpp:114
The LU, Cholesky and QR factorisations and the symmetric and Hermitian eigen-decompositions.
constexpr std::size_t gemm_packed_threshold
Below this many multiply-adds the plain loop (gemm_rows, by blocks of rows held in registers) runs in...
Definition gemm.hpp:909
void symmetric_rank_two(buffer< T > &a, std::size_t n, std::size_t k, buffer< T > &w)
The trailing matrix's update by a pivot of order 2 at rows k and k + 1, as sytf2: D21 scaled out,...
Definition ldl.hpp:137
void eliminate_pivot(buffer< double > &a, std::size_t n, std::size_t k, std::size_t step, bool, buffer< double > &w)
A real matrix's update by a pivot of order 1 or 2 (step), sytf2's whatever hermitian.
Definition ldl.hpp:194
carried_t< T > real_part(const T &x)
The real part of a real (or general) scalar, in carried_t.
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
double pivot_size(double x)
LAPACK's measure of a real entry, |x|.
Definition ldl.hpp:26
void symmetric_rank_one(buffer< T > &a, std::size_t n, std::size_t k, buffer< T > &w)
The trailing matrix's update by a pivot of order 1 at k, as sytf2 (syr, then L's column scaled): A ← ...
Definition ldl.hpp:88
void gemm(std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
C += A·B, every element of C summed in ascending order of the depth.
Definition gemm.hpp:4583
std::size_t factor_ldl_panel(buffer< T > &a, std::size_t n, std::size_t k0, bool hermitian, bool last_on_ties, buffer< T > &w, std::vector< std::ptrdiff_t > &pivots)
One panel of bunch_kaufman_blocked_lower from column k0, as LAPACK's lasyf and lahef on the lower tri...
Definition ldl.hpp:341
void hermitian_rank_one(buffer< std::complex< double > > &a, std::size_t n, std::size_t k, buffer< std::complex< double > > &w)
As symmetric_rank_one for a Hermitian matrix, as hetf2 (her): d real, A ← A − x xᴴ / d,...
Definition ldl.hpp:109
std::vector< std::ptrdiff_t > bunch_kaufman_blocked_lower(buffer< T > &a, std::size_t n, bool hermitian, bool last_on_ties)
bunch_kaufman_lower by panels, as LAPACK's sytrf and hetrf on the lower triangle: each panel of ldl_b...
Definition ldl.hpp:476
double diagonal_kept(double x, bool)
A real x as it is.
Definition ldl.hpp:67
constexpr std::size_t ldl_blocked_least
The order from which bunch_kaufman_lower runs by panels (bunch_kaufman_blocked_lower): below it the p...
Definition ldl.hpp:329
constexpr std::size_t gemm_min_depth
Below this depth the plain loop runs too: each panel reads and writes its tiles of C once,...
Definition gemm.hpp:915
constexpr std::size_t ldl_block
The columns of one panel of the blocked factorisation (bunch_kaufman_blocked_lower),...
Definition ldl.hpp:323
std::vector< std::ptrdiff_t > bunch_kaufman_lower(buffer< T > &a, std::size_t n, bool hermitian, bool last_on_ties, std::size_t from=0)
Bunch and Kaufman's factorisation of the lower triangle of a (n × n, row-major; entries (i,...
Definition ldl.hpp:246
void hermitian_rank_two(buffer< std::complex< double > > &a, std::size_t n, std::size_t k, buffer< std::complex< double > > &w)
As symmetric_rank_two for a Hermitian matrix, as hetf2: |D21| scaled out in real arithmetic,...
Definition ldl.hpp:164
double conjugated_if(double x, bool)
A real x as it is.
Definition ldl.hpp:53
double diagonal_size(double x, bool)
A real diagonal entry's measure, |x|, whatever hermitian.
Definition ldl.hpp:38
The NumericAL public API.
Definition amx.hpp:44
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...