8#ifndef NUMERICAL_LDL_HPP
9#define NUMERICAL_LDL_HPP
34 return std::abs(z.real()) + std::abs(z.imag());
49 return hermitian ? std::abs(z.real()) :
pivot_size(z);
63 return hermitian ? std::conj(z) : z;
78 return hermitian ? std::complex<double> {z.real()} : z;
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];
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) {
112 buffer<std::complex<double>>& w)
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]);
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) {
125 row[i] = C {
row[i].real() + (x * w[i]).real()};
136 template <
typename T>
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);
150 for (std::size_t i {k + 2}; i < n; ++i) {
151 T*
const row {a.data() + (i * n)};
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]);
158 row[k + 1] = w[(2 * i) + 1];
167 buffer<std::complex<double>>& w)
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);
180 for (std::size_t i {k + 2}; i < n; ++i) {
181 C*
const row {a.data() + (i * n)};
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]));
188 row[k + 1] = w[(2 * i) + 1];
189 row[i] = C {
row[i].real()};
215 buffer<std::complex<double>>& w)
225 else if (hermitian) {
245 template <
typename T>
250 std::size_t
from = 0)
252 const double alpha {(1.0 + std::sqrt(17.0)) / 8.0};
253 std::vector<std::ptrdiff_t> pivots(n);
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};
260 std::size_t
imax {k};
262 for (std::size_t i {k + 1}; i < n; ++i) {
275 for (std::size_t j {k}; j <
imax; ++j) {
278 for (std::size_t i {
imax + 1}; i < n; ++i) {
286 const std::size_t
kk {k +
step - 1};
288 for (std::size_t i {pivot + 1}; i < n; ++i) {
289 std::swap(at(i,
kk), at(i, pivot));
291 for (std::size_t j {
kk + 1}; j < pivot; ++j) {
299 at(pivot, pivot) = t;
302 std::swap(at(k + 1, k), at(pivot, k));
311 const auto origin {
static_cast<std::ptrdiff_t
>(pivot + 1)};
312 pivots[k] =
step == 1 ? origin : -origin;
314 pivots[k + 1] = -origin;
340 template <
typename T>
347 std::vector<std::ptrdiff_t>& pivots)
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]; };
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) {
356 for (std::size_t p {0}; p <
kw; ++p) {
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);
371 std::size_t
step {1};
372 std::size_t pivot {k};
374 std::size_t
imax {k};
376 for (std::size_t i {k + 1}; i < n; ++i) {
384 for (std::size_t i {k}; i < n; ++i) {
385 at(i, k) =
wt(i,
kw);
390 for (std::size_t j {k}; j <
imax; ++j) {
393 for (std::size_t i {
imax}; i < n; ++i) {
400 for (std::size_t i {k}; i < n; ++i) {
408 for (std::size_t i {k}; i < n; ++i) {
417 const std::size_t
kk {k +
step - 1};
420 for (std::size_t j {
kk + 1}; j < pivot; ++j) {
423 for (std::size_t i {pivot + 1}; i < n; ++i) {
424 at(i, pivot) = at(i,
kk);
426 for (std::size_t j {
k0}; j <
kk; ++j) {
427 std::swap(at(
kk, j), at(pivot, j));
429 for (std::size_t j {0}; j <=
kk -
k0; ++j) {
430 std::swap(
wt(
kk, j),
wt(pivot, j));
434 for (std::size_t i {k}; i < n; ++i) {
435 at(i, k) =
wt(i,
kw);
437 const T r {
T {1.0} / at(k, k)};
438 for (std::size_t i {k + 1}; i < n; ++i) {
448 for (std::size_t j {k + 2}; j < n; ++j) {
450 at(j, k + 1) = s * ((
d22 *
wt(j,
kw + 1)) -
wt(j,
kw));
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);
457 const auto origin {
static_cast<std::ptrdiff_t
>(pivot + 1)};
458 pivots[k] =
step == 1 ? origin : -origin;
460 pivots[k + 1] = -origin;
475 template <
typename T>
481 std::vector<std::ptrdiff_t> pivots(n);
488 const std::size_t
rest {n - end};
489 const std::size_t depth {end -
k0};
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];
499 T *
trailing {a.data() + (end * n) + end};
501 if constexpr (std::is_same_v<T, double>) {
513 for (std::size_t i {0}; i <
rest; ++i) {
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)) {
526 std::swap(a[(
jp * n) + c], a[(
jj * n) + c]);
533 std::copy(
tail.begin() +
static_cast<std::ptrdiff_t
>(
k0),
tail.end(), pivots.begin() +
static_cast<std::ptrdiff_t
>(
k0));
547 template <
double_field T>
563 bool hermitian =
true)
570 const std::size_t n {
n_};
572 for (std::size_t i {0}; i < n; ++i) {
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);
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)];
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)};
617 const std::vector<std::ptrdiff_t>&
ipiv,
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});
628 const std::ptrdiff_t value {
ipiv[index]};
630 swaps[index] = swaps[
static_cast<std::size_t
>(value - 1)];
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;
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) {
649 l[(i * n) + j] =
ldu[(i * n) + j];
653 for (std::size_t start {0}; start < n;) {
654 const int order {blocks[start]};
656 const std::size_t below {start + 1};
657 const T entry {lower ?
ldu[(below * n) + start] :
ldu[(start * n) + below]};
660 l[lower ? (below * n) + start : (start * n) + below] =
T {};
662 start +=
static_cast<std::size_t
>(order);
664 std::vector<std::size_t> order(n);
665 std::iota(order.begin(), order.end(), std::size_t {0});
668 const std::size_t
target {swaps[index]};
672 std::size_t first {lower ? index : 0};
673 std::size_t
last {lower ? n : index + 1};
674 if (blocks[index] == (lower ? 0 : 2)) {
675 first -= lower ? 1 : 0;
676 last += lower ? 0 : 1;
678 for (std::size_t j {first}; j <
last; ++j) {
679 std::swap(l[(
target * n) + j], l[(index * n) + j]);
681 std::swap(order[
target], order[index]);
684 for (std::size_t i {0}; i < n; ++i) {
Thrown when an operation's operands have incompatible shapes.
The symmetric indefinite factorisation of a symmetric or Hermitian matrix, as scipy....
matrix< T > l_
L, permuted.
std::vector< std::size_t > permutation_
The rows' order making L triangular.
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,...
const std::vector< std::size_t > & permutation() const noexcept
The rows' order that makes factor triangular (SciPy's perm).
const matrix< T > & d() const noexcept
D, block diagonal (blocks of order 1 and 2).
const matrix< T > & factor() const noexcept
L, permuted (SciPy's lu): L[permutation()] is triangular with a unit diagonal.
ldl_decomposition(const matrix< T > &a, bool lower=true, bool hermitian=true)
Factorises a, of which only the triangle lower names is read.
A dense, row-major matrix of T with value semantics.
std::size_t cols() const noexcept
The number of columns.
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...
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,...
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.
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|.
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 ← ...
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.
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...
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,...
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...
double diagonal_kept(double x, bool)
A real x as it is.
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...
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,...
constexpr std::size_t ldl_block
The columns of one panel of the blocked factorisation (bunch_kaufman_blocked_lower),...
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,...
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,...
double conjugated_if(double x, bool)
A real x as it is.
double diagonal_size(double x, bool)
A real diagonal entry's measure, |x|, whatever hermitian.
The NumericAL public API.
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...
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...