17#ifndef NUMERICAL_EIGEN_HPP
18#define NUMERICAL_EIGEN_HPP
41 inline constexpr double schur_ulp {std::numeric_limits<double>::epsilon()};
64 return std::abs(x.real()) + std::abs(x.imag());
79 [[
nodiscard]]
inline std::complex<double>
times(
const std::complex<double>& a,
80 const std::complex<double>& b)
82 return {(a.real() * b.real()) - (a.imag() * b.imag()), (a.real() * b.imag()) + (a.imag() * b.real())};
94 return std::max(std::abs(x.real()), std::abs(x.imag()));
103 std::vector<std::pair<std::size_t, std::size_t>>
swaps;
108 template <
typename T>
114 for (std::size_t c {0}; c < n; ++c) {
115 std::swap(a[(i * n) + c], a[(j * n) + c]);
117 for (std::size_t r {0}; r < n; ++r) {
118 std::swap(a[(r * n) + i], a[(r * n) + j]);
129 template <
typename T>
140 for (std::size_t i {out.
high}; i-- > out.
low;) {
142 for (std::size_t j {out.
low}; j < out.
high &&
alone; ++j) {
143 alone = j == i || a[(i * n) + j] ==
T {};
156 for (std::size_t j {out.
low}; j < out.
high; ++j) {
158 for (std::size_t i {out.
low}; i < out.
high &&
alone; ++i) {
159 alone = i == j || a[(i * n) + j] ==
T {};
173 for (std::size_t i {out.
low}; i < out.
high; ++i) {
174 for (std::size_t k {out.
low}; k < out.
high; ++k) {
175 gathered[k - out.
low] = a[(k * n) + i];
199 for (std::size_t k {out.
low}; k < n; ++k) {
202 for (std::size_t k {0}; k < out.
high; ++k) {
214 template <
typename T>
218 return balance(a, n,
true,
false);
233 template <
typename T>
240 std::vector<buffer<T>> reflectors(n);
241 for (std::size_t k {low}; k + 2 < high; ++k) {
243 for (std::size_t i {k + 1}; i < high; ++i) {
244 v[i - k - 1] = a[(i * n) + k];
246 if (
scaled_norm(v.data() + 1, v.size() - 1) == 0.0) {
257 for (std::size_t i {0}; i < v.size(); ++i) {
259 const T*
row {a.data() + ((k + 1 + i) * n) + k};
260 for (std::size_t c {0}; c < w.size(); ++c) {
264 for (std::size_t i {0}; i < v.size(); ++i) {
265 const T twice {
static_cast<T>(2) * v[i]};
266 T*
row {a.data() + ((k + 1 + i) * n) + k};
267 for (std::size_t c {0}; c < w.size(); ++c) {
271 for (std::size_t r {0}; r < high; ++r) {
272 T*
row {a.data() + (r * n) + k + 1};
274 for (std::size_t j {0}; j < v.size(); ++j) {
277 s *=
static_cast<T>(2);
278 for (std::size_t j {0}; j < v.size(); ++j) {
282 for (std::size_t i {k + 2}; i < high; ++i) {
283 a[(i * n) + k] =
T {};
285 reflectors[k] = std::move(v);
291 for (std::size_t i {0}; i < n; ++i) {
292 q[(i * n) + i] =
T {1};
294 for (std::size_t k {n}; k-- > 0;) {
300 for (std::size_t i {0}; i < v.size(); ++i) {
302 const T*
row {q.data() + ((k + 1 + i) * n) + k + 1};
303 for (std::size_t c {0}; c < w.size(); ++c) {
307 for (std::size_t i {0}; i < v.size(); ++i) {
308 const T twice {
static_cast<T>(2) * v[i]};
309 T*
row {q.data() + ((k + 1 + i) * n) + k + 1};
310 for (std::size_t c {0}; c < w.size(); ++c) {
316 for (std::size_t i {0}; i < n; ++i) {
317 for (std::size_t j {0}; j < n; ++j) {
318 qt[(j * n) + i] = q[(i * n) + j];
341 return rest == 0.0 &&
alpha.imag() == 0.0;
349 template <
typename T>
363 for (std::size_t i {0}; i < count; ++i) {
371 for (std::size_t i {0}; i < count; ++i) {
401 const auto*
const parts {
reinterpret_cast<const double*
>(
row)};
412 for (std::size_t l {0}; l < count; ++l) {
424 for (std::size_t l {0}; l < count; ++l) {
425 const std::complex<double> x {v[l *
stride]};
427 out.real_side[(2 * l) + 1] = -x.imag();
428 out.imaginary_side[2 * l] = x.imag();
429 out.imaginary_side[(2 * l) + 1] = x.real();
435 template <
typename T>
450 template <
typename T>
457 std::vector<hessenberg_panel<T>>
panels;
458 for (std::size_t k {low}; k + 2 < high;) {
460 const std::size_t m {high - k - 1};
466 for (std::size_t i {0}; i < b; ++i) {
467 const std::size_t j {k + i};
468 for (std::size_t r {0}; r < m; ++r) {
469 column[r] = a[((k + 1 + r) * n) + j];
472 for (std::size_t r {0}; r < m; ++r) {
474 for (std::size_t p {0}; p < i; ++p) {
479 for (std::size_t p {0}; p < i; ++p) {
481 for (std::size_t r {p}; r < m; ++r) {
486 for (std::size_t p {i}; p-- > 0;) {
488 for (std::size_t q {0}; q <= p; ++q) {
493 for (std::size_t r {0}; r < m; ++r) {
495 for (std::size_t p {0}; p < std::min(i, r + 1); ++p) {
503 v[(i * b) + i] =
T {1};
504 for (std::size_t r {i + 1}; r < m; ++r) {
505 v[(r * b) + i] =
column[r];
507 for (std::size_t r {0}; r < m; ++r) {
508 a[((k + 1 + r) * n) + j] = r < i ?
column[r] : (r == i ?
alpha :
T {});
513 y[((k + 1 + r) * b) + i] =
against_v.dot(a.data() + ((k + 1 + r) * n) + j + 1);
515 for (std::size_t p {0}; p < i; ++p) {
517 for (std::size_t r {i}; r < m; ++r) {
522 for (std::size_t r {0}; r < m; ++r) {
524 for (std::size_t p {0}; p < i; ++p) {
525 sum +=
times(
y[((k + 1 + r) * b) + p], w[p]);
527 y[((k + 1 + r) * b) + i] = tau * (
y[((k + 1 + r) * b) + i] -
sum);
529 for (std::size_t p {0}; p < i; ++p) {
531 for (std::size_t q {p}; q < i; ++q) {
534 t[(p * b) + i] = -tau *
sum;
536 t[(i * b) + i] = tau;
539 gemm(k + 1, b, m, a.data() + k + 1, n, v.data(), b,
top.data(), b);
540 for (std::size_t r {0}; r <= k; ++r) {
541 for (std::size_t p {b}; p-- > 0;) {
543 for (std::size_t q {0}; q <= p; ++q) {
546 y[(r * b) + p] =
sum;
549 for (std::size_t r {0}; r <= k; ++r) {
550 for (std::size_t i {1}; i < b; ++i) {
552 for (std::size_t p {0}; p < i; ++p) {
555 a[(r * n) + k + i] -=
sum;
558 const std::size_t
rest {high - k - b};
560 for (std::size_t e {0}; e < high * b; ++e) {
564 for (std::size_t r {0}; r < m; ++r) {
565 for (std::size_t p {0}; p < b; ++p) {
570 const std::size_t columns {n - k - b};
572 gemm(b, columns, m,
v_adjoint.data(), m, a.data() + ((k + 1) * n) + k + b, n,
product.data(), columns);
574 for (std::size_t p {0}; p < b; ++p) {
575 for (std::size_t q {0}; q <= p; ++q) {
576 const T factor {-
conj_of(t[(q * b) + p])};
577 for (std::size_t c {0}; c < columns; ++c) {
582 gemm(m, columns, b, v.data(), b,
scaled.data(), columns, a.data() + ((k + 1) * n) + k + b, n);
584 panels.push_back({k, b, std::move(v), std::move(t)});
592 for (std::size_t i {0}; i < n; ++i) {
593 q[(i * n) + i] =
T {1};
595 for (std::size_t s {
panels.size()}; s-- > 0;) {
598 const std::size_t b {
panel.width};
599 T*
const block {q.data() + ((
panel.first + 1) * n) +
panel.first + 1};
601 for (std::size_t r {0}; r < m; ++r) {
602 for (std::size_t p {0}; p < b; ++p) {
609 for (std::size_t p {0}; p < b; ++p) {
610 for (std::size_t r {p}; r < b; ++r) {
611 const T factor {-
panel.t[(p * b) + r]};
612 for (std::size_t c {0}; c < m; ++c) {
620 for (std::size_t i {0}; i < n; ++i) {
621 for (std::size_t j {0}; j < n; ++j) {
622 qt[(j * n) + i] = q[(i * n) + j];
629 template <
typename T>
650 double rest {count == 3 ? std::hypot(v[1], v[2]) : std::abs(v[1])};
658 for (std::size_t i {0}; i < count; ++i) {
661 rest = count == 3 ? std::hypot(v[1], v[2]) : std::abs(v[1]);
663 const double beta {-std::copysign(std::hypot(v[0],
rest), v[0])};
664 const double tau {(beta - v[0]) / beta};
665 const double scale {1.0 / (v[0] - beta)};
666 for (std::size_t i {1}; i < count; ++i) {
669 v[0] = beta / factor;
687 const double beta {-std::copysign(std::hypot(std::abs(v[0]), std::abs(v[1])), v[0].real())};
688 const std::complex<double> tau {(beta - v[0].real()) / beta, -v[0].
imag() / beta};
689 v[1] = v[1] / (v[0] - beta);
690 v[0] = beta / factor;
716 if (b == 0.0 && c != 0.0) {
723 else if (c != 0.0 && (a - d != 0.0 || std::signbit(b) == std::signbit(c))) {
724 const double temp {a - d};
725 double p {0.5 *
temp};
726 const double bcmax {std::max(std::abs(b), std::abs(c))};
727 const double bcmis {std::min(std::abs(b), std::abs(c)) * std::copysign(1.0, b) * std::copysign(1.0, c)};
728 const double scale {std::max(std::abs(p),
bcmax)};
729 double z {((p / scale) * p) + ((
bcmax / scale) *
bcmis)};
731 z = p + std::copysign(std::sqrt(scale) * std::sqrt(z), p);
734 const double tau {std::hypot(c, z)};
741 const double sigma {b + c};
742 const double tau {std::hypot(sigma,
temp)};
743 out.
cs = std::sqrt(0.5 * (1.0 + (std::abs(sigma) / tau)));
744 out.
sn = -(0.5 * (
temp / tau) / out.
cs) * std::copysign(1.0, sigma);
745 const double aa {(a * out.
cs) + (b * out.
sn)};
746 const double bb {(-a * out.
sn) + (b * out.
cs)};
747 const double cc {(c * out.
cs) + (d * out.
sn)};
748 const double dd {(-c * out.
sn) + (d * out.
cs)};
756 if (c != 0.0 && b != 0.0 && std::signbit(b) == std::signbit(c)) {
757 const double sab {std::sqrt(std::abs(b))};
758 const double sac {std::sqrt(std::abs(c))};
759 const double root {std::copysign(
sab *
sac, c)};
760 const double inverse {1.0 / std::sqrt(std::abs(b + c))};
767 const double cs {(out.
cs *
cs1) - (out.
sn *
sn1)};
771 else if (c != 0.0 && b == 0.0) {
774 const double cs {out.
cs};
783 out.
im1 = std::sqrt(std::abs(b)) * std::sqrt(std::abs(c));
790 template <
typename T>
798 for (std::size_t i {0}; i < count; ++i) {
811 template <
typename T>
827 for (std::size_t j {
from}; j <
to; ++j) {
837 template <
typename T>
849 for (std::size_t j {
from}; j <
to; ++j) {
861 template <
typename T>
871 for (std::size_t r {0}; r < rows; ++r) {
872 T*
const x {first + (r * ld)};
881 template <
typename T>
889 for (std::size_t r {0}; r < rows; ++r) {
890 T*
const x {first + (r * ld)};
898 template <
typename T>
926 const std::size_t n {t.
n};
927 const auto at {[&h, n](std::size_t i, std::size_t j) ->
double& {
return h[(i * n) + j]; }};
930 for (std::size_t end {t.
high}; end > t.
low;) {
931 const std::size_t i {end - 1};
932 std::size_t l {t.
low};
934 for (std::size_t
its {0};
its <= steps; ++
its) {
937 const double sub {std::abs(at(k, k - 1))};
941 double test {std::abs(at(k - 1, k - 1)) + std::abs(at(k, k))};
943 if (k >= t.
low + 2) {
944 test += std::abs(at(k - 1, k - 2));
946 if (k + 1 < t.
high) {
947 test += std::abs(at(k + 1, k));
951 const double ab {std::max(
sub, std::abs(at(k - 1, k)))};
952 const double ba {std::min(
sub, std::abs(at(k - 1, k)))};
953 const double aa {std::max(std::abs(at(k, k)), std::abs(at(k - 1, k - 1) - at(k, k)))};
954 const double bb {std::min(std::abs(at(k, k)), std::abs(at(k - 1, k - 1) - at(k, k)))};
955 const double s {
aa +
ab};
970 const std::size_t first {t.
full ? 0 : l};
971 const std::size_t
last {t.
full ? n : i + 1};
977 const double s {std::abs(at(i, i - 1)) + std::abs(at(i - 1, i - 2))};
978 h11 = (0.75 * s) + at(i, i);
984 const double s {std::abs(at(l + 1, l)) + std::abs(at(l + 2, l + 1))};
985 h11 = (0.75 * s) + at(l, l);
991 h11 = at(i - 1, i - 1);
996 const double s {std::abs(
h11) + std::abs(
h12) + std::abs(
h21) + std::abs(
h22)};
1003 const double root {std::sqrt(std::abs(
det))};
1016 std::size_t m {i - 2};
1019 const double h21s {at(m + 1, m) / (std::abs(at(m, m) -
rt2r) + std::abs(
rt2i) + std::abs(at(m + 1, m)))};
1020 const double scale {std::abs(at(m, m) -
rt2r) + std::abs(
rt2i) + std::abs(at(m + 1, m))};
1021 v[0] = (
h21s * at(m, m + 1)) + ((at(m, m) -
rt1r) * ((at(m, m) -
rt2r) / scale)) - (
rt1i * (
rt2i / scale));
1022 v[1] =
h21s * (at(m, m) + at(m + 1, m + 1) -
rt1r -
rt2r);
1023 v[2] =
h21s * at(m + 2, m + 1);
1024 const double sum {std::abs(v[0]) + std::abs(v[1]) + std::abs(v[2])};
1031 const double above {std::abs(at(m, m - 1)) * (std::abs(v[1]) + std::abs(v[2]))};
1032 const double here {std::abs(v[0]) * (std::abs(at(m - 1, m - 1)) + std::abs(at(m, m)) + std::abs(at(m + 1, m + 1)))};
1037 for (std::size_t
k2 {m};
k2 < i; ++
k2) {
1038 const std::size_t count {std::min<std::size_t>(3, i -
k2 + 1)};
1040 v[0] = at(
k2,
k2 - 1);
1041 v[1] = at(
k2 + 1,
k2 - 1);
1042 v[2] = count == 3 ? at(
k2 + 2,
k2 - 1) : 0.0;
1046 at(
k2,
k2 - 1) = v[0];
1047 at(
k2 + 1,
k2 - 1) = 0.0;
1049 at(
k2 + 2,
k2 - 1) = 0.0;
1053 at(
k2,
k2 - 1) *= 1.0 -
t1;
1055 const double v2 {v[1]};
1056 const double v3 {count == 3 ? v[2] : 0.0};
1057 const double t2 {
t1 *
v2};
1058 const double t3 {
t1 *
v3};
1059 const std::size_t
third {count == 3 ? std::size_t {2} : std::size_t {1}};
1060 double*
a1 {&at(
k2, 0)};
1061 double*
a2 {
a1 + n};
1063 for (std::size_t j {
k2}; j <
last; ++j) {
1069 for (std::size_t j {first}; j <= std::min(
k2 + 3, i); ++j) {
1070 double*
row {&at(j,
k2)};
1076 if (t.
zt !=
nullptr) {
1078 double*
r1 {zt.data() + (
k2 * n)};
1079 double*
r2 {
r1 + n};
1081 for (std::size_t j {t.
low}; j < t.
high; ++j) {
1091 throw convergence_error(
"eigendecomposition: the QR iterations did not converge");
1099 re[i - 1] = block.
re1;
1100 im[i - 1] = block.im1;
1104 rotate(&at(i - 1, i + 1 < n ? i + 1 : i), &at(i, i + 1 < n ? i + 1 : i), n - i - 1, 1, block.cs, block.sn);
1105 rotate(&at(0, i - 1), &at(0, i), i - 1, n, block.cs, block.sn);
1107 if (t.
zt !=
nullptr) {
1109 rotate(zt.data() + ((i - 1) * n) + t.
low, zt.data() + (i * n) + t.
low, t.
high - t.
low, 1, block.cs, block.sn);
1127 buffer<std::complex<double>>& values,
1130 using C = std::complex<double>;
1132 const std::size_t n {t.n};
1133 const auto at {[&h, n](std::size_t i, std::size_t j) -> C& {
return h[(i * n) + j]; }};
1134 const double smallest {std::numeric_limits<double>::min() * (
static_cast<double>(t.high - t.low) /
schur_ulp)};
1136 for (std::size_t end {t.high}; end > t.low;) {
1137 const std::size_t i {end - 1};
1138 std::size_t l {t.low};
1140 for (std::size_t
its {0};
its <= steps; ++
its) {
1142 for (; k > l; --k) {
1149 if (k >= t.low + 2) {
1152 if (k + 1 < t.high) {
1161 const double s {
aa +
ab};
1169 at(l, l - 1) = C {};
1176 const std::size_t first {t.full ? 0 : l};
1177 const std::size_t
last {t.full ? n : i + 1};
1187 const C u {std::sqrt(at(i - 1, i)) * std::sqrt(at(i, i - 1))};
1189 const C x {0.5 * (at(i - 1, i - 1) -
shift)};
1192 C
y {s * std::sqrt(((x / s) * (x / s)) + ((u / s) * (u / s)))};
1193 if (
sx > 0.0 && ((x /
sx).real() *
y.real()) + ((x /
sx).imag() *
y.imag()) < 0.0) {
1196 shift -= u * (u / (x +
y));
1199 std::size_t m {i - 1};
1202 const C
h11 {at(m, m)};
1203 const C
h22 {at(m + 1, m + 1)};
1204 const C
h21 {at(m + 1, m)};
1215 for (std::size_t
k2 {m};
k2 < i; ++
k2) {
1217 v[0] = at(
k2,
k2 - 1);
1218 v[1] = at(
k2 + 1,
k2 - 1);
1222 at(
k2,
k2 - 1) = v[0];
1223 at(
k2 + 1,
k2 - 1) = C {};
1226 at(
k2,
k2 - 1) *= 1.0 - std::conj(
t1);
1231 if (t.zt !=
nullptr) {
1232 C*
const r1 {t.zt->data() + (
k2 * n)};
1238 throw convergence_error(
"eigendecomposition: the QR iterations did not converge");
1240 values[i] = at(i, i);
1251 template <
typename T>
1267 return data[((i - 1) *
ld) + (j - 1)];
1274 return static_cast<std::size_t
>(count);
1306 template <
typename T>
1319 return {1.0, 0.0, f};
1322 return {0.0, std::copysign(1.0, g), std::abs(g)};
1324 const double r {std::copysign(std::hypot(f, g), f)};
1325 return {std::abs(f) / std::abs(r), g / r, r};
1330 const std::complex<double>& g)
1332 using C = std::complex<double>;
1334 return {1.0, C {}, f};
1337 return {0.0, std::conj(g) / std::abs(g), C {std::abs(g)}};
1339 const double size {std::abs(f)};
1340 const double d {std::hypot(size, std::abs(g))};
1341 const C
phase {f / size};
1342 return {size / d,
phase * std::conj(g) / d,
phase * d};
1346 template <
typename T>
1354 for (std::size_t i {0}; i < count; ++i) {
1367 template <
typename T>
1373 const T t11 {t(k, k)};
1374 const T t22 {t(k + 1, k + 1)};
1381 t(k + 1, k + 1) =
t11;
1392 for (std::size_t c {0}; c < count; ++c) {
1393 const double sum {(u[0] * t[c]) + (u[1] * t[ld + c]) + (u[2] * t[(2 * ld) + c])};
1394 t[c] -= tau *
sum * u[0];
1395 t[ld + c] -= tau *
sum * u[1];
1396 t[(2 * ld) + c] -= tau *
sum * u[2];
1407 for (std::size_t r {0}; r < count; ++r) {
1408 double*
const row {t + (r * ld)};
1409 const double sum {(
row[0] * u[0]) + (
row[1] * u[1]) + (
row[2] * u[2])};
1410 row[0] -= tau *
sum * u[0];
1411 row[1] -= tau *
sum * u[1];
1412 row[2] -= tau *
sum * u[2];
1431 double largest {0.0};
1444 for (std::size_t r {0}; r < size; ++r) {
1445 for (std::size_t c {0}; c < size; ++c) {
1446 largest = std::max(largest, std::abs(k[r][c]));
1449 const double floor {std::max(
schur_ulp * largest, std::numeric_limits<double>::min())};
1451 for (std::size_t s {0}; s < size; ++s) {
1454 for (std::size_t r {s}; r < size; ++r) {
1455 for (std::size_t c {s}; c < size; ++c) {
1456 if (std::abs(k[r][c]) > std::abs(k[
pr][
pc])) {
1462 std::swap(k[s], k[
pr]);
1464 for (std::size_t r {0}; r < size; ++r) {
1465 std::swap(k[r][s], k[r][
pc]);
1468 if (std::abs(k[s][s]) < floor) {
1471 for (std::size_t r {s + 1}; r < size; ++r) {
1472 const double factor {k[r][s] / k[s][s]};
1473 for (std::size_t c {s}; c < size; ++c) {
1474 k[r][c] -= factor * k[s][c];
1476 rhs[r] -= factor *
rhs[s];
1480 for (std::size_t s {size}; s-- > 0;) {
1482 for (std::size_t c {s + 1}; c < size; ++c) {
1483 sum -= k[s][c] *
y[c];
1485 y[s] =
sum / k[s][s];
1487 for (std::size_t s {0}; s < size; ++s) {
1501 rotate(&t(j, j + 2), &t(j + 1, j + 2),
count_of(n - j - 1), 1, block.cs, block.sn);
1504 rotate(&qt(j, 1), &qt(j + 1, 1),
count_of(n), 1, block.cs, block.sn);
1519 if (n1 == 1 &&
n2 == 1) {
1527 std::array<double, 16> d {};
1532 dd(i, j) = t(
j1 + i - 1,
j1 + j - 1);
1541 std::array<double, 3>
u1 {};
1542 std::array<double, 3>
u2 {};
1557 residue = std::max({std::abs(
dd(3, 1)), std::abs(
dd(3, 2)), std::abs(
dd(3, 3) -
t11)});
1568 residue = std::max({std::abs(
dd(2, 1)), std::abs(
dd(3, 1)), std::abs(
dd(1, 1) -
t33)});
1577 const double temp {-
tau1 * (at(1, 2) + (
u1[1] * at(2, 2)))};
1578 u2[0] = (-
temp *
u1[1]) - at(2, 2);
1588 residue = std::max({std::abs(
dd(3, 1)), std::abs(
dd(3, 2)), std::abs(
dd(4, 1)), std::abs(
dd(4, 2))});
1636 return j < n && t(j + 1, j) != 0.0 ? 2 : 1;
1661 struct refused : std::exception
1671 if (
nbf == 2 &&
nbl == 1) {
1674 if (
nbf == 1 &&
nbl == 2) {
1689 if (next == 2 && t(
here + 2,
here + 1) == 0.0) {
1714 if (next == 2 && t(
here,
here - 1) == 0.0) {
1758 const std::complex<double>& s1,
1759 const std::complex<double>& s2,
1762 const double sr1 {s1.real()};
1763 const double si1 {s1.imag()};
1764 const double sr2 {s2.real()};
1765 const double si2 {s2.imag()};
1767 const double s {std::abs(h(1, 1) -
sr2) + std::abs(
si2) + std::abs(h(2, 1))};
1773 const double h21s {h(2, 1) / s};
1774 v[0] = (
h21s * h(1, 2)) + ((h(1, 1) -
sr1) * ((h(1, 1) -
sr2) / s)) - (
si1 * (
si2 / s));
1775 v[1] =
h21s * (h(1, 1) + h(2, 2) -
sr1 -
sr2);
1778 const double s {std::abs(h(1, 1) -
sr2) + std::abs(
si2) + std::abs(h(2, 1)) + std::abs(h(3, 1))};
1785 const double h21s {h(2, 1) / s};
1786 const double h31s {h(3, 1) / s};
1787 v[0] = ((h(1, 1) -
sr1) * ((h(1, 1) -
sr2) / s)) - (
si1 * (
si2 / s)) + (h(1, 2) *
h21s) + (h(1, 3) *
h31s);
1788 v[1] = (
h21s * (h(1, 1) + h(2, 2) -
sr1 -
sr2)) + (h(2, 3) *
h31s);
1789 v[2] = (
h31s * (h(1, 1) + h(3, 3) -
sr1 -
sr2)) + (
h21s * h(3, 2));
1795 const std::complex<double>& s1,
1796 const std::complex<double>& s2,
1797 std::complex<double>* v)
1799 using C = std::complex<double>;
1807 const C
h21s {h(2, 1) / s};
1808 v[0] = (
h21s * h(1, 2)) + ((h(1, 1) - s1) * ((h(1, 1) - s2) / s));
1809 v[1] =
h21s * (h(1, 1) + h(2, 2) - s1 - s2);
1819 const C
h21s {h(2, 1) / s};
1820 const C
h31s {h(3, 1) / s};
1821 v[0] = ((h(1, 1) - s1) * ((h(1, 1) - s2) / s)) + (
h21s * h(1, 2)) + (
h31s * h(1, 3));
1822 v[1] = (
h21s * (h(1, 1) + h(2, 2) - s1 - s2)) + (
h31s * h(2, 3));
1823 v[2] = (
h31s * (h(1, 1) + h(3, 3) - s1 - s2)) + (
h21s * h(3, 2));
1833 if (s[i].
imag() != -s[i + 1].
imag()) {
1834 const std::complex<double> first {s[i]};
1836 s[i + 1] = s[i + 2];
1845 const std::complex<double>& )
1858 const std::complex<double>& )
1865 template <
typename T>
1872 if (h(k + 1, k) ==
T {}) {
1878 if (k >=
ktop + d) {
1881 if (k <=
kbot - d - 1) {
1893 const double scale {
h11 +
h12};
1902 template <
typename T>
1923 template <
typename T>
1927 std::complex<double>* s,
1935 const double smallest {std::numeric_limits<double>::min() * (
static_cast<double>(n) /
schur_ulp)};
1957 reflect_three_rows(&zt(k + 1, 1), &zt(k + 2, 1), &zt(k + 3, 1),
count_of(low - 1),
count_of(high), v(1, m), v(2, m), v(3, m),
false);
1960 reflect_two_rows(&zt(k + 1, 1), &zt(k + 2, 1),
count_of(low - 1),
count_of(high), v(1, m), v(2, m),
false);
1974 if (k ==
ktop - 1) {
1975 std::array<T, 2>
column {};
1982 T beta {h(k + 1, k)};
1983 v(2,
m22) = h(k + 2, k);
1989 reflect_two_rows(&h(k + 1, 1), &h(k + 2, 1),
count_of(k),
count_of(
jbot), v(1,
m22), v(2,
m22),
true);
1996 reflect_two_rows(&
ut(
kms + 1, 1), &
ut(
kms + 2, 1),
from,
count_of(
kdu), v(1,
m22), v(2,
m22),
false);
2002 if (k ==
ktop - 1) {
2003 std::array<T, 3>
column {};
2012 const T sum {v(1, m) * v(3, m) * h(k + 3, k + 2)};
2016 T beta {h(k + 1, k)};
2017 v(2, m) = h(k + 2, k);
2018 v(3, m) = h(k + 3, k);
2023 double fill {std::numeric_limits<double>::infinity()};
2024 std::array<T, 3>
fresh {};
2027 if (h(k + 3, k) ==
T {} && h(k + 3, k + 2) !=
T {}) {
2047 reflect_three_columns(&h(
jtop, k + 1),
count_of(std::min(
kbot, k + 3) -
jtop + 1),
count_of(n), v(1, m), v(2, m), v(3, m));
2055 reflect_three_rows(&h(k + 1, 1), &h(k + 2, 1), &h(k + 3, 1),
count_of(std::max(
ktop,
krcol + (2 * m)) - 1),
count_of(
jbot), v(1, m),
2056 v(2, m), v(3, m),
true);
2064 reflect_three_rows(&
ut(
kms + 1, 1), &
ut(
kms + 2, 1), &
ut(
kms + 3, 1),
count_of(
i2 - 1),
count_of(
i4), v(1, m), v(2, m), v(3, m),
false);
2099 for (std::size_t r {0}; r < rows; ++r) {
2103 if (
target.zt !=
nullptr) {
2111 const std::size_t width {
count_of(high - low + 1)};
2121 template <
typename T>
2123 std::complex<double>* w,
2129 std::complex<double>* w)
2134 for (std::size_t i {t.
low}; i < t.
high; ++i) {
2135 w[i] = std::complex<double> {re[i], im[i]};
2141 std::complex<double>* w)
2145 std::copy(values.begin() +
static_cast<std::ptrdiff_t
>(t.low), values.begin() +
static_cast<std::ptrdiff_t
>(t.high), w + t.low);
2159 std::complex<double>* w)
2162 return k == i + 1 ? std::abs(t(i, i)) : std::abs(t(i, i)) + (std::sqrt(std::abs(t(i + 1, i))) * std::sqrt(std::abs(t(i, i + 1))));
2168 double foo {order == 1 ? std::abs(t(
ns,
ns)) : size(
ns - 1,
ns + 1)};
2172 const double spike {order == 1 ? std::abs(s *
vt(
ns, 1)) : std::max(std::abs(s *
vt(
ns, 1)), std::abs(s *
vt(
ns - 1, 1)))};
2182 bool sorted {
false};
2191 const double evi {size(i, k)};
2192 const double evk {k ==
kend ? std::abs(t(k, k)) : size(k, next(k,
kend))};
2206 if (i == 1 || t(i, i - 1) == 0.0) {
2207 w[i - 1] = std::complex<double> {t(i, i), 0.0};
2211 double a {t(i - 1, i - 1)};
2212 double b {t(i - 1, i)};
2213 double c {t(i, i - 1)};
2216 w[i - 2] = std::complex<double> {block.
re1, block.im1};
2217 w[i - 1] = std::complex<double> {block.re2, block.im2};
2228 const std::complex<double>& s,
2230 std::complex<double>* w)
2278 template <
typename T>
2283 std::complex<double>* w,
2288 const double smallest {std::numeric_limits<double>::min() * (
static_cast<double>(n) /
schur_ulp)};
2302 for (
lapack_index j {std::max<lapack_index>(1, i - 1)}; j <=
jw; ++j) {
2320 t(
jw,
jw - 2) =
T {};
2372 std::copy(rows.begin(), rows.end(),
vt_store.begin());
2378 for (
lapack_index j {std::max<lapack_index>(1, i - 1)}; j <=
jw; ++j) {
2395 for (std::size_t r {0}; r < rows; ++r) {
2403 for (std::size_t r {0}; r < width; ++r) {
2407 if (
target.zt !=
nullptr) {
2413 for (std::size_t r {0}; r < width; ++r) {
2427 else if (
nh >= 3000) {
2430 else if (
nh >= 590) {
2433 else if (
nh >= 150) {
2434 ns = std::max<lapack_index>(10,
nh /
static_cast<lapack_index>(std::lround(std::log2(
static_cast<double>(
nh)))));
2436 else if (
nh >= 60) {
2439 else if (
nh >= 30) {
2442 return std::max<lapack_index>(2,
ns - (
ns % 2));
2449 return nh <= 500 ?
ns : 3 *
ns / 2;
2455 std::complex<double>* w,
2461 const double ss {std::abs(h(i, i - 1)) + std::abs(h(i - 1, i - 2))};
2462 double a {(0.75 *
ss) + h(i, i)};
2464 double c {-0.4375 *
ss};
2467 w[i - 2] = std::complex<double> {block.
re1, block.im1};
2468 w[i - 1] = std::complex<double> {block.re2, block.im2};
2476 std::complex<double>* w,
2482 w[i - 1] = h(i, i) + (0.75 *
modulus_1(h(i, i - 1)));
2483 w[i - 2] = w[i - 1];
2495 if (w[i - 1].
imag() != -w[i - 2].
imag()) {
2496 const std::complex<double>
last {w[i - 1]};
2497 w[i - 1] = w[i - 2];
2498 w[i - 2] = w[i - 3];
2508 const std::complex<double>& )
2518 return kbot -
ks + 1 == 2 && w[
kbot - 1].imag() == 0.0;
2525 const std::complex<double>& )
2527 return kbot -
ks + 1 == 2;
2543 template <
typename T>
2545 std::complex<double>* w,
2558 nsr = std::max<lapack_index>(2,
nsr - (
nsr % 2));
2611 for (
lapack_index j {std::max<lapack_index>(1, i - 1)}; j <=
ns; ++j) {
2612 lower(i, j) = h(
ks + i - 1,
ks + j - 1);
2619 bool sorted {
false};
2624 std::swap(w[i - 1], w[i]);
2649 throw convergence_error(
"eigendecomposition: the QR iterations did not converge");
2665 for (std::size_t i {t.
low}; i < t.
high; ++i) {
2666 re[i] = w[i].real();
2667 im[i] = w[i].imag();
2673 buffer<std::complex<double>>& values,
2688 template <
typename S>
2694 for (std::size_t q {1}; q < 4; ++q) {
2697 const std::size_t
pr {p / 2};
2698 const std::size_t
pc {p % 2};
2701 const S u12 {m[(
pr * 2) + 1 -
pc]};
2708 double factor {1.0};
2723 template <
typename S>
2732 template <
typename S,
typename P>
2739 double factor {1.0};
2757 std::size_t
to)
const
2774 for (std::size_t l {
from}; l <=
to; ++l) {
2792 std::size_t
to)
const
2799 const std::complex<double>& value)
2801 re[j] = value.real();
2802 im[j] = value.imag();
2810 for (std::size_t l {
from}; l <=
to; ++l) {
2830 std::size_t
to)
const
2832 const auto*
const parts {
reinterpret_cast<const double*
>(
row)};
2833 const std::size_t count {2 * (
to -
from + 1)};
2840 const std::complex<double>& value)
2859 for (std::size_t l {2 *
from}; l <= (2 *
to) + 1; ++l) {
2873 std::size_t largest {0};
2874 for (std::size_t r {0}; r < n; ++r) {
2876 largest = std::norm(v[r]) > std::norm(v[largest]) ? r : largest;
2878 std::complex<double>
turn {std::conj(v[largest]) / std::abs(v[largest])};
2879 if (
signed_real && std::signbit(v[largest].real())) {
2882 for (std::size_t r {0}; r < n; ++r) {
2885 v[largest] = std::complex<double> {v[largest].real(), 0.0};
2894 template <
typename T,
typename X>
2899 typename X::scalar
lambda,
2903 using S =
typename X::scalar;
2904 for (std::size_t j {k}; j > 0;) {
2905 if constexpr (std::is_floating_point_v<T>) {
2906 if (j >= 2 && t[((j - 1) * n) + j - 2] != 0.0) {
2907 const S m[4] {
S {t[((j - 2) * n) + j - 2]} -
lambda,
S {t[((j - 2) * n) + j - 1]},
S {t[((j - 1) * n) + j - 2]},
2908 S {t[((j - 1) * n) + j - 1]} -
lambda};
2909 S r[2] {-x.dot(t.data() + ((j - 2) * n), j,
top), -x.dot(t.data() + ((j - 1) * n), j,
top)};
2911 if (factor != 1.0) {
2912 x.scale(j,
top, factor);
2920 const auto [value, factor] {
divided(-x.dot(t.data() + ((j - 1) * n), j,
top),
S {t[((j - 1) * n) + j - 1]} -
lambda, floor)};
2921 if (factor != 1.0) {
2922 x.scale(j,
top, factor);
2924 x.set(j - 1, value);
2933 return std::max<std::size_t>(1, (n * n) / 6);
2939 std::size_t n)
noexcept
2951 using C = std::complex<double>;
2952 const double smallest {std::numeric_limits<double>::min() * (
static_cast<double>(n) /
schur_ulp)};
2957 const C
lambda {t[(k * n) + k]};
2960 for (std::size_t l {0}; l <= k; ++l) {
2961 xt[(k * n) + l] = x.get(l);
2984 using C = std::complex<double>;
2985 const double smallest {std::numeric_limits<double>::min() * (
static_cast<double>(n) /
schur_ulp)};
2989 const double floor {std::max(
schur_ulp * (std::abs(re[k]) + std::abs(im[k])),
smallest)};
2990 double*
row_re {out.re.data() + (k * n)};
2991 double*
row_im {out.im.data() + (k * n)};
2996 std::copy(x.x.begin(), x.x.begin() +
static_cast<std::ptrdiff_t
>(k + 1),
row_re);
2998 else if (im[k] > 0.0) {
3000 const double b {t[(k * n) + k + 1]};
3001 const double c {t[((k + 1) * n) + k]};
3002 y.set(k, std::abs(b) >= std::abs(c) ? C {1.0} : C {-im[k] / c});
3003 y.set(k + 1, std::abs(b) >= std::abs(c) ? C {0.0, im[k] / b} : C {0.0, 1.0});
3005 for (std::size_t l {0}; l <= k + 1; ++l) {
3017 template <
typename T>
3024 gemm(n, n, n,
xt.data(), n, zt.data(), n,
vt.data(), n);
3035 template <
typename T>
3040 for (std::size_t p {0}; p < n; ++p) {
3041 for (std::size_t q {0}; q < n; ++q) {
3042 s[(p * n) + q] =
conj_of(t[((n - 1 - q) * n) + (n - 1 - p)]);
3050 template <
typename T>
3055 for (std::size_t j {0}; j < n; ++j) {
3056 for (std::size_t l {0}; l < n; ++l) {
3057 out[(j * n) + l] = w[((n - 1 - j) * n) + (n - 1 - l)];
3065 template <
typename T>
3081 template <
typename T>
3086 const std::size_t n {a.
rows()};
3087 if (a.
cols() != n) {
3093 std::vector<std::size_t> permutation(n);
3094 for (std::size_t c {0}; c < n; ++c) {
3096 for (
auto swap {
balanced.swaps.rbegin()}; swap !=
balanced.swaps.rend(); ++swap) {
3097 at = at == swap->first ? swap->second : at == swap->second ? swap->first : at;
3099 permutation[c] = at;
3111 template <
double_field T>
3152 double largest {0.0};
3153 for (std::size_t i {0}; i <
n_; ++i) {
3154 for (std::size_t j {0}; j <
n_; ++j) {
3160 const double scale {largest == 0.0 ? 1.0 : std::ldexp(1.0, std::ilogb(largest))};
3177 if constexpr (std::is_floating_point_v<T>) {
3180 for (std::size_t i {0}; i <
n_; ++i) {
3181 re[i] = a[(i *
n_) + i];
3184 for (std::size_t i {0}; i <
n_; ++i) {
3185 values[i] = std::complex<double> {re[i] * scale, im[i] * scale};
3192 for (std::size_t e {0}; e <
n_ *
n_; ++e) {
3193 rows[e] = std::complex<double> {
vre[e],
vim[e]};
3203 for (std::size_t k {0}; k <
n_; ++k) {
3212 for (std::size_t i {0}; i <
n_; ++i) {
3216 for (std::size_t i {0}; i <
n_; ++i) {
3277 const std::complex<double>& value,
3280 if (value.imag() == 0.0) {
3282 for (std::size_t r {0}; r <
n_; ++r) {
3283 row[r] = std::complex<double> {
row[r].real() /
norm, 0.0};
3286 else if (value.imag() > 0.0) {
3294 const std::complex<double>& value,
3297 if (value.imag() < 0.0) {
3298 const std::complex<double>* first {
row -
n_};
3299 for (std::size_t r {0}; r <
n_; ++r) {
3300 row[r] = std::conj(first[r]);
3307 const std::complex<double>& ,
3308 const std::complex<double>& )
const noexcept
3315 const std::complex<double>& ,
3316 const std::complex<double>& )
const
3332 std::complex<double>*
row {rows.data() + (c *
n_)};
3336 for (std::size_t s {
balanced.swaps.size()}; s-- > 0;) {
3379 std::vector<std::complex<double>> values(n);
3380 for (std::size_t k {0}; k < n; ++k) {
3381 const double a {t[(k * n) + k]};
3382 if (k + 1 < n && t[((k + 1) * n) + k] != 0.0) {
3383 const double im {std::sqrt(std::abs(t[(k * n) + k + 1])) * std::sqrt(std::abs(t[((k + 1) * n) + k]))};
3384 values[k] = std::complex<double> {a, im};
3385 values[k + 1] = std::complex<double> {a, -im};
3389 values[k] = std::complex<double> {a, 0.0};
3399 std::vector<std::complex<double>> values(n);
3400 for (std::size_t k {0}; k < n; ++k) {
3401 values[k] = t[(k * n) + k];
3421 std::type_identity<std::complex<double>> )
3434 std::type_identity<double> )
3436 std::size_t count {0};
3438 for (std::size_t k {0}; k <
after.size(); ++k) {
3440 const bool pair {
after[k].imag() != 0.0};
3445 throw convergence_error(
"Schur form: leading eigenvalues do not satisfy the selection");
3461 template <
typename T>
3465 const std::vector<bool>&
chosen)
3480 throw convergence_error(
"Schur form: eigenvalues could not be separated for reordering");
3499 template <
double_field T>
3517 const std::size_t n {
input.rows()};
3518 if (
input.cols() != n) {
3519 throw dimension_error(
"Schur decomposition requires a square matrix");
3522 double largest {0.0};
3523 for (std::size_t i {0}; i < n; ++i) {
3524 for (std::size_t j {0}; j < n; ++j) {
3529 const double scale {largest == 0.0 ? 1.0 : std::ldexp(1.0, std::ilogb(largest))};
3542 for (std::size_t s {
isolated.swaps.size()}; s-- > 0;) {
3543 const auto [i, j] {
isolated.swaps[s]};
3544 for (std::size_t c {0}; c < n; ++c) {
3545 std::swap(zt[(c * n) + i], zt[(c * n) + j]);
3559 template <
typename Select>
3560 requires std::predicate<Select&, const std::complex<double>&>
3582 const std::size_t n {t_.rows()};
3583 if (
chosen.size() != n) {
3584 throw dimension_error(
"Schur reordering requires one choice per eigenvalue");
3588 std::size_t
moved {0};
3610 const std::vector<std::complex<double>>
before {values()};
3612 for (std::size_t k {0}; k <
before.size(); ++k) {
3634 return std::move(t_);
3646 return std::move(z_);
3664 return {std::move(s.
t_), std::move(s.
z_), leading};
3671 leading_(
form.leading)
3676 std::size_t leading_ {0};
3694 template <
typename T>
3701 : n_(lower.cols()), width_(lower.rows() - 1), data_((width_ + 2) * n_, T {})
3703 for (std::size_t d {0}; d <= width_; ++d) {
3704 for (std::size_t j {0}; j + d < n_; ++j) {
3705 data_[(d * n_) + j] = lower(d, j);
3712 [[nodiscard]] T
get(std::size_t i,
3713 std::size_t k)
const
3715 return data_[((i - k) * n_) + k];
3723 data_[((i - k) * n_) + k] = value;
3726 [[nodiscard]] std::size_t
order() const noexcept
3731 [[nodiscard]] std::size_t
width() const noexcept
3746 template <
typename T>
3753 const std::size_t n {a.
order()};
3754 const std::size_t q {p + 1};
3755 for (std::size_t k {p >= a.
width() ? p - a.
width() : 0}; k < p; ++k) {
3756 const T x {a.
get(p, k)};
3757 const T y {a.
get(q, k)};
3758 a.
set(p, k, (c * x) +
times(s, y));
3761 for (std::size_t k {q + 1}; k <= std::min(n - 1, q + a.
width()); ++k) {
3762 const T x {a.
get(k, p)};
3763 const T y {a.
get(k, q)};
3765 a.
set(k, q, (c * y) -
times(s, x));
3769 const T b {a.
get(q, p)};
3772 a.
set(p, p, T {(c * c * app) + cross + (ss * aqq)});
3773 a.
set(q, q, T {(ss * app) - cross + (c * c * aqq)});
3775 if (!turned.empty()) {
3783 template <
typename T>
3800 template <
typename T>
3804 if (lower.
rows() == 0) {
3805 throw dimension_error(
"band_tridiagonal: a band of at least one diagonal");
3807 const std::size_t n {lower.
cols()};
3808 const std::size_t u {std::min(lower.
rows() - 1, n == 0 ? std::size_t {0} : n - 1)};
3811 buffer<T> turned(basis ? n * n : 0, T {});
3812 for (std::size_t i {0}; basis && i < n; ++i) {
3813 turned[(i * n) + i] = T {1};
3815 const auto annihilate = [&](std::size_t row, std::size_t column) {
3817 detail::rotate_band(a, row - 1, g.c, g.s, turned);
3818 a.set(row - 1, column, g.r);
3819 a.set(row, column, T {});
3821 for (std::size_t j {0}; u > 1 && j + 2 < n; ++j) {
3822 for (std::size_t k {std::min(u, n - 1 - j)}; k >= 2; --k) {
3823 annihilate(j + k, j);
3824 for (std::size_t row {j + k + u}, column {j + k - 1}; row < n; column = row - 1, row += u) {
3825 annihilate(row, column);
3832 for (std::size_t j {0}; j < n; ++j) {
3833 diagonal[j] = detail::real_part(a.get(j, j));
3835 for (std::size_t i {0}; i < n; ++i) {
3836 turned[(j * n) + i] = detail::times(turned[(j * n) + i], phase);
3840 const T off {a.get(j + 1, j)};
3841 const double size {std::abs(off)};
3842 off_diagonal[j] = size;
3844 phase = detail::times(phase, off / size);
3851 for (std::size_t i {0}; i < n; ++i) {
3852 for (std::size_t k {0}; k < n; ++k) {
3853 w[(i * n) + k] = turned[(k * n) + i];
3856 form.w =
matrix<T> {n, n, std::move(w)};
Thrown when an iterative algorithm has not converged within its bound of sweeps.
The lower band of a symmetric or Hermitian matrix of order n and half-bandwidth width,...
std::size_t width() const noexcept
< The half-bandwidth.
std::size_t order() const noexcept
< The order n.
T get(std::size_t i, std::size_t k) const
Entry (i, k) of the lower triangle, within the bulge's diagonal (0 ≤ i − k ≤ width + 1: all a reducti...
void set(std::size_t i, std::size_t k, const T &value)
Sets entry (i, k) of the lower triangle (i ≥ k, within the bulge's diagonal).
band_work(const matrix< T > &lower)
The band of lower, its (d, j) entry the matrix's (j + d, j), the bulge's diagonal zero.
Thrown when an operation's operands have incompatible shapes.
The eigenvalues, and optionally the right eigenvectors, of a general square matrix,...
void finish(std::complex< double > *row, const std::complex< double > &value, double) const
Normalises the eigenvector row (a row of Vᵀ) of a real matrix's eigenvalue value, as dgeev: a real on...
matrix< std::complex< double > > left_vectors_
The left eigenvectors as columns.
matrix< std::complex< double > > vectors_
The eigenvectors as columns.
bool real_
Whether all eigenvalues are real.
matrix< std::complex< double > > finished(buffer< std::complex< double > > rows, const detail::balancing &balanced, bool left) const
The vectors of the rows rows (each a vector of the balanced matrix) in the input's basis,...
eigen_decomposition(const matrix< T > &input, bool vectors=true, bool left=false)
Decomposes input.
const vector< std::complex< double > > & values() const noexcept
The eigenvalues, in the order of the Schur form.
const matrix< std::complex< double > > & left_vectors() const noexcept
The left eigenvectors as columns, ordered to match values (empty where they were not computed): colum...
void conjugate_second(std::complex< double > *, const std::complex< double > &, const std::complex< double > &) const noexcept
No pairs in a complex matrix's eigenvectors.
const matrix< std::complex< double > > & vectors() const &noexcept
The eigenvectors as columns, ordered to match values (empty where they were not computed).
void finish(std::complex< double > *row, const std::complex< double > &, const std::complex< double > &) const
Normalises the eigenvector row of a complex matrix, as zgeev: to unit norm, its largest component rea...
void conjugate_second(std::complex< double > *row, const std::complex< double > &value, double) const
A real matrix's pair's second eigenvector row (value's imaginary part negative): the first's,...
bool real() const noexcept
Whether every eigenvalue is real (a real matrix's whose Schur form has no 2 × 2 block): its vectors a...
std::size_t n_
The matrix order.
vector< std::complex< double > > values_
The eigenvalues.
matrix< std::complex< double > > vectors() &&
The eigenvectors, moved out of an expiring decomposition.
eigen_decomposition(matrix< T > &&input, bool vectors=true, bool left=false)
Decomposes input in its own storage, an expiring matrix's elements taken over: its scaled copy is mad...
A dense, row-major matrix of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
std::size_t rows() const noexcept
The number of rows.
std::size_t cols() const noexcept
The number of columns.
The Schur decomposition A = Z T Zᴴ of a square matrix, as scipy.linalg.schur (LAPACK's dgees/zgees): ...
std::vector< std::complex< double > > values() const
The eigenvalues, in T's order: its diagonal, a real 2 × 2 block a conjugate pair, the positive first.
matrix< T > t_
The Schur form.
matrix< T > z() &&
Z, moved out of an expiring decomposition.
matrix< T > z_
The Schur vectors.
matrix< T > t() &&
T, moved out of an expiring decomposition.
schur_decomposition(const matrix< T > &input)
Decomposes input.
schur_decomposition(const matrix< T > &input, Select select)
Decomposes input, then moves the eigenvalues for which select holds to the leading block of T (sort),...
schur_decomposition(matrix< T > &&input)
Decomposes input in its own storage, an expiring matrix's elements taken over.
const matrix< T > & t() const &noexcept
T, upper quasi-triangular (real) or triangular (complex).
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen (one per eigenvalue, in values's order) are set to the ...
std::size_t leading() const noexcept
The eigenvalues the selecting constructor moved to the leading block (its sdim); 0 otherwise.
const matrix< T > & z() const &noexcept
Z, the Schur vectors as columns.
std::size_t sort(const detail::eigenvalue_selection &select)
The eigenvalues for which select holds moved to the leading block (reorder), as dgees/zgees sort them...
schur_decomposition(sorted_form form)
The decomposition form holds.
static sorted_form sorted(schur_decomposition s, const detail::eigenvalue_selection &select)
s sorted by select (sort), taken apart for the constructor that holds the count.
A dense vector of T with value semantics.
The scalar types NumericAL's factorisations and solvers take: a field of floating-point numbers,...
Matrix factorisations and the algorithms built on them.
buffer< T > hessenberg_unblocked(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
Reduces the active block low … high − 1 of the balanced row-major n × n a to upper Hessenberg form by...
T reflector_tau(T &alpha, T *x, std::size_t count)
The Householder reflection H = I − τ v vᴴ, v = (1, v₁…), with Hᴴ (α, x) = (β, 0) and β real,...
void reflect_columns_3(const std::array< double, 3 > &u, double tau, double *t, std::size_t ld, std::size_t count)
The same from the right, to the count × 3 columns at t.
buffer< T > reversed_rows(const buffer< T > &w, std::size_t n)
Row j of the rows w (n × n) its row n − 1 − j, its entries in reverse order: J applied to each of rev...
constexpr double back_substitution_limit
The modulus an eigenvector's components are kept under during the back-substitution: the sums stay fi...
buffer< T > reversed_adjoint(const buffer< T > &t, std::size_t n)
S = J Tᴴ J of the upper (quasi-)triangular t (row-major n × n, J the reversal): upper (quasi-)triangu...
void reflect_three_rows(T *r1, T *r2, T *r3, std::size_t from, std::size_t to, const T &tau, const T &v2, const T &v3, bool adjoint)
A reflection I − τ v vᴴ, v = (1, v₂, v₃), on the entries from … to − 1 of three rows: its adjoint fro...
void bulge_column(one_based< double > h, lapack_index count, const std::complex< double > &s1, const std::complex< double > &s2, double *v)
A multiple of the first column of (H − s₁ I)(H − s₂ I) for the leading 2 × 2 or 3 × 3 (count) of the ...
void multishift_schur(const schur_target< T > &target, std::complex< double > *w, bool recursive, lapack_index steps=0)
The Schur form of target's active block by the multishift QR algorithm with aggressive early deflatio...
void normalize_vector(std::complex< double > *v, std::size_t n, bool signed_real)
Scales v to unit Euclidean norm and turns it so that its first component of largest modulus is real: ...
void reflect_two_rows(T *r1, T *r2, std::size_t from, std::size_t to, const T &tau, const T &v2, bool adjoint)
reflect_three_rows for a reflection of two entries, v = (1, v₂), on two rows: its own loop,...
buffer< T > hessenberg_blocked(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
hessenberg_unblocked by panels of hessenberg_block columns, as LAPACK's dgehrd and dlahr2: a panel's ...
buffer< T > hessenberg(buffer< T > &a, std::size_t n, std::size_t low, std::size_t high, bool form)
hessenberg_blocked from an active order of hessenberg_crossover, else hessenberg_unblocked.
void exchange(buffer< T > &a, std::size_t n, std::size_t i, std::size_t j)
Exchanges rows i and j, then columns i and j, of the row-major n × n a: a similarity.
std::size_t vector_work(std::size_t n) noexcept
A triangular solve's work for parallel_for over the n eigenvectors: k²/2 products for vector k,...
void reflect_three_columns(T *first, std::size_t rows, std::size_t ld, const T &tau, const T &v2, const T &v3)
A reflection I − τ v vᴴ, v = (1, v₂, v₃), from the right on rows rows (ld apart) of the three columns...
constexpr std::size_t hessenberg_crossover
The active order from which hessenberg reduces by panels.
std::complex< R > scaled(R c, const std::complex< R > &v) noexcept
c · v of a real c and a complex v: each part's product, rounded.
carried_t< T > real_part(const T &x)
The real part of a real (or general) scalar, in carried_t.
std::function< bool(const std::complex< double > &)> eigenvalue_selection
A choice among eigenvalues, as scipy.linalg.schur's sort makes it: true where one is to lead.
std::size_t count_of(lapack_index count)
A count as an unsigned size (never negative where it is taken).
void whole_schur_form(const schur_target< double > &t, std::size_t steps)
The real Schur form of the whole of t (its eigenvalues not kept), steps its iterations' bound.
void reflect_two_columns(T *first, std::size_t rows, std::size_t ld, const T &tau, const T &v2)
The same for a reflection of two entries, v = (1, v₂), on two columns.
void vigilant_deflation(one_based< T > h, lapack_index k, lapack_index ktop, lapack_index kbot, double smallest)
H(k + 1, k) set to zero where the deflation criterion of Ahues and Tisseur holds, as the sweep of dla...
void chase_bulges(const schur_target< T > &target, lapack_index ktop, lapack_index kbot, std::complex< double > *s, lapack_index count, bool accumulate)
One small-bulge multishift QR sweep over the active block ktop … kbot of target's Hessenberg matrix w...
double solve_block(const S(&m)[4], S(&r)[2], double floor)
Solves [a b; c d] x = r in place of r by Gaussian elimination with complete pivoting,...
constexpr std::size_t hessenberg_block
The columns of a panel of hessenberg_blocked.
constexpr double schur_ulp
The relative spacing LAPACK's ‘dlamch('P’)` names: the roundoff a QR sweep judges a subdiagonal by.
void pair_for_sweep(std::complex< double > *w, lapack_index ks, lapack_index kbot, double)
A real matrix's shifts brought into pairs, each a conjugate pair or two reals, as dlaqr0 does before ...
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
void exchange_diagonal(one_based< T > t, one_based< T > qt, lapack_index n, lapack_index k)
Exchanges the diagonal entries k and k + 1 of the upper triangular (or quasi-triangular,...
void reflect_from_left(T *x, std::size_t stride, const T &tau, const T &v2, const T &v3)
The adjoint I − τ̄ v vᴴ of a reflection of three entries from the left on one column (x three entries...
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::size_t selected_leading(const std::vector< std::complex< double > > &, const eigenvalue_selection &, std::size_t moved, std::type_identity< std::complex< double > >)
The count of a complex Schur form's sort, as zgees takes trsen's: the eigenvalues it moved.
real_operand operand_of(const double *v, std::size_t stride, std::size_t count)
The count entries stride apart at v as a real_operand.
bool two_real_shifts(const std::complex< double > *w, lapack_index ks, lapack_index kbot, double)
Whether a real matrix's sweep is down to two shifts, both real: then the one nearer the corner serves...
void small_sylvester(const one_based< double > &tl, const one_based< double > &tr, const one_based< double > &b, lapack_index n1, lapack_index n2, double(&x)[4])
The solution X (n1 × n2, row-major in x) of TL X − X TR = B, n1 and n2 at most 2, by Gaussian elimina...
auto times(const A &a, const B &b)
a · b.
lapack_index block_order(one_based< double > t, lapack_index n, lapack_index j)
The order of the diagonal block of the quasi-triangular t that starts at j: 2 where a subdiagonal ent...
std::size_t balanced_index(std::size_t task, std::size_t n) noexcept
The eigenvector task of n solves, the short ones and the long ones in turn (0, n − 1,...
bool exchange_blocks(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index j1, lapack_index n1, lapack_index n2)
Exchanges the adjacent diagonal blocks of the real quasi-triangular t at j1, of orders n1 then n2,...
std::ptrdiff_t lapack_index
A signed index from 1, as LAPACK's: the multishift sweep starts its bulges in phantom columns above t...
buffer< T > back_transformed(const buffer< T > &xt, const buffer< T > &zt, std::size_t n)
Vᵀ = Xᵀ Zᵀ, row-major n × n, through the matrix product kernel.
bool reorder(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index ifst, lapack_index &ilst)
Moves the diagonal block of the real quasi-triangular t at ifst to ilst by exchanges of adjacent bloc...
constexpr lapack_index multishift_crossover
LAPACK's nmin: the active order below which dlaqr0's iterations skip a sweep after enough deflation.
real_eigenvectors real_vectors(const buffer< double > &t, const buffer< double > &re, const buffer< double > &im, std::size_t n)
The eigenvectors of the real quasi-triangular t (row-major n × n, its 2 × 2 blocks standard) as the r...
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
bool already_reduced(double, double rest)
Whether (α, x), of tail norm rest, is already (β, 0) with β real: for a real one, its tail zero.
deflation_count early_deflation(const schur_target< T > &target, lapack_index ktop, lapack_index kbot, lapack_index nw, std::complex< double > *w, bool recursive)
Aggressive early deflation, as LAPACK's dlaqr3 and zlaqr3: the trailing nw × nw window of the active ...
standard_block standardize_block(double &a, double &b, double &c, double &d)
The Schur factorisation of the real 2 × 2 block [a b; c d], as LAPACK's dlanv2: [a b; c d] ← [cs −sn;...
plane_rotation< double > givens(double f, double g)
The rotation that takes (f, g) to (r, 0), as LAPACK's dlartg: r of f's sign.
double as_scalar(const std::complex< double > &s, double)
The shift s as the matrix's scalar: a real matrix's are real where they are used one by one.
double small_reflector(double(&v)[3], std::size_t count)
The Householder reflection I − τ v vᵀ, v = (1, x…), that takes (α, x…) to (β, 0…),...
constexpr lapack_index exceptional_after
The iterations without deflation after which the shifts are exceptional (kexsh).
carried_t< T > rescale_tiny(buffer< T > &x)
Scales x by rescue_factor of its largest magnitude, exactly, so that a Householder vector built from ...
void plain_schur(const schur_target< double > &t, std::complex< double > *w)
The Schur form of t's active block by real_schur, its eigenvalues to w (one per row of t).
void standardize_at(one_based< double > t, one_based< double > qt, lapack_index n, lapack_index j)
The standard form of the 2 × 2 block at j of the quasi-triangular t, its rotation carried to the rest...
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.
void complex_schur(const schur_target< std::complex< double > > &t, buffer< std::complex< double > > &values, std::size_t steps)
The complex Schur form of the upper Hessenberg t's active block, as LAPACK's zlahqr: the shifted QR a...
lapack_index recommended_window(lapack_index nh, lapack_index ns)
The deflation window LAPACK's iparmq recommends for an active block of order nh and ns shifts.
std::size_t move_leading(buffer< T > &t, buffer< T > &qt, std::size_t n, const std::vector< bool > &chosen)
Moves the eigenvalues of the Schur form t whose entries of chosen are set to its leading block,...
double modulus_1(double x)
|x| of a real x: what modulus_1 of a complex one stands for.
double dot_product(const double *x, const double *y, std::size_t count)
Σ x[i] · y[i] for double, as subtract_product chooses its units (in another order of summation there,...
double largest_part(double x)
|x| of a real x.
lapack_index undeflated(one_based< double > t, one_based< double > vt, lapack_index jw, double s, double smallest, std::complex< double > *w)
The eigenvalues of the real Schur form t (jw × jw) of a deflation window that do not deflate,...
T phase_of(const T &x)
The unit-modulus factor of x: x / |x| (its sign, for a real scalar), and 1 at 0. A subnormal x is sca...
void pair_shifts(std::complex< double > *s, lapack_index count, double)
Arranges a real matrix's shifts so that each pair is a conjugate pair or two reals,...
void real_schur(const schur_target< double > &t, buffer< double > &re, buffer< double > &im, std::size_t steps)
The real Schur form of the upper Hessenberg t's active block, as LAPACK's dlahqr: Francis's implicit ...
void rotate_band(band_work< T > &a, std::size_t p, double c, const T &s, buffer< T > &turned)
A ← G A Gᴴ of the band a, G the rotation [c s; −s̄ c] on rows and columns p and p + 1: the two rows w...
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
balancing balance(buffer< T > &a, std::size_t n, bool permute=true, bool scale=true)
Balances the row-major n × n a in place, as LAPACK's ‘dgebal('B’): rows with no off-diagonal entry in...
std::vector< std::complex< double > > schur_values(const double *t, std::size_t n)
The eigenvalues of the real quasi-triangular t (n × n, row-major), in its order: a 2 × 2 block of sta...
scaled_quotient< S > divided(S r, P pivot, double floor)
r / pivot, a pivot below floor taken as floor, r scaled first where the quotient would pass back_subs...
void rotate_pair(T *x, T *y, std::size_t count, std::size_t stride, double c, const T &s)
(x, y) ← (c x + s y, c y − s̄ x) over count pairs stride apart.
carried_t< T > scaled_norm(const T *x, std::size_t count)
The Euclidean norm of the count elements at x, by norm_at_scale for this type.
void solve_upward(const buffer< T > &t, std::size_t n, std::size_t k, std::size_t top, typename X::scalar lambda, double floor, X &x)
Solves (T − λ I) x = 0 upward from the component k, rows k − 1 … 0 of the row-major quasi-triangular ...
void rotate(T *x, T *y, std::size_t count, std::size_t stride, double cs, double sn)
(x, y) ← (cs x + sn y, cs y − sn x) over count pairs stride apart: a plane rotation.
std::complex< double > complex_reflector(std::complex< double >(&v)[2])
The Householder reflection I − τ v vᴴ, v = (1, x), whose adjoint takes (α, x) to (β,...
constexpr double balance_limit
The largest power of two a balancing scales a row or a column by, either way: the matrix enters at a ...
buffer< std::complex< double > > complex_vectors(const buffer< std::complex< double > > &t, std::size_t n)
The eigenvectors of the complex upper triangular t (row-major n × n) as the rows of Xᵀ: row k is x wi...
void exceptional_shifts(one_based< double > h, std::complex< double > *w, lapack_index ks, lapack_index kbot, lapack_index ktop)
Exceptional shifts for a real matrix, as dlaqr0's after kexsh iterations without deflation: from the ...
constexpr lapack_index nibble
The share of the window, in percent, whose deflation makes the sweep unnecessary (nibble).
void schur_form(const schur_target< double > &t, buffer< double > &re, buffer< double > &im, std::size_t steps)
The real Schur form of t's active block: real_schur below multishift_from, else multishift_schur,...
constexpr std::size_t schur_steps_per_order
The iterations one eigenvalue (or pair) may take per unit of the active order, as dlahqr's 30.
balancing isolate(buffer< T > &a, std::size_t n)
Isolates eigenvalues of the row-major n × n a in place by permutations alone, as LAPACK's ‘dgebal('P’...
constexpr lapack_index multishift_from(double)
The order from which a real Schur form is taken by multishift_schur, below which real_schur is faster...
lapack_index recommended_shifts(lapack_index nh)
The shifts LAPACK's iparmq recommends for an active block of order nh.
void reflect_rows_3(const std::array< double, 3 > &u, double tau, double *t, std::size_t ld, std::size_t count)
H = I − τ u uᵀ of three entries applied from the left to the 3 × count rows at t (row stride ld).
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
constexpr lapack_index window_growth
The iterations without deflation after which the window grows (kexnw).
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 ...
vector< std::complex< double > > eigenvalues(const matrix< T > &a)
The eigenvalues alone of the square a, as numpy.linalg.eigvals.
tensor< T > take(const tensor< T > &t, const tensor< std::int64_t > &indices, std::size_t axis, take_mode mode)
The elements of t at indices along axis, as numpy.take: the result's shape t's with the axis replaced...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
balanced_matrix< T > matrix_balance(const matrix< T > &a, bool permute=true, bool scale=true)
The square a balanced, as scipy.linalg.matrix_balance(a, permute, scale, separate=True) (LAPACK's dge...
tensor< T > diagonal(const tensor< T > &t, std::ptrdiff_t offset)
The offset diagonal of each matrix of t (its last two axes), as numpy.linalg.diagonal: above the main...
matrix< T > inverse(matrix< T > a)
The inverse of a square matrix.
band_tridiagonal_form< T > band_tridiagonal(const matrix< T > &lower, bool basis)
Reduces the real symmetric or complex Hermitian band matrix whose lower form is lower ((u + 1) × n,...
A matrix balanced, B = T⁻¹ A T with T = P D (matrix_balance).
matrix< T > b
The balanced matrix.
vector< double > scale
The diagonal of D, powers of two (1 outside the scaled block).
std::vector< std::size_t > permutation
P e_c = e_{permutation[c]}.
How a matrix was balanced: swaps, in the order they were applied, then the scaling of the active bloc...
std::vector< std::pair< std::size_t, std::size_t > > swaps
Rows and columns exchanged, in order.
std::size_t high
One past its last.
buffer< double > scale
The diagonal D of D⁻¹ A D (1 outside).
std::size_t low
The active block's first row and column.
A complex vector that rows are summed against, kept as (re, −im) and (im, re) pairs: a complex row,...
std::complex< double > dot(const std::complex< double > *row) const
Σ row[l] v[l].
buffer< double > real_side
(re, −im) per entry.
buffer< double > imaginary_side
(im, re) per entry.
What early_deflation found: the eigenvalues left as shifts, and those deflated.
lapack_index shifts
Undeflated: the shifts, at the bottom of the active block.
lapack_index deflated
Deflated below them.
One panel of hessenberg_blocked, Q_panel = I − V T Vᴴ.
buffer< T > t
T, row-major width × width, upper triangular.
std::size_t width
Its columns.
buffer< T > v
V, row-major (high − first − 1) × width, unit lower trapezoidal.
std::size_t first
The panel's first column; its reflectors act on rows first + 1 … high − 1.
A complex matrix's eigenvector during its back-substitution, kept as (re, −im) and (im,...
void set(std::size_t j, const std::complex< double > &value)
Sets component j to value.
buffer< double > real_side
(re, −im) per component: a row against it gives the product's real part.
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
std::complex< double > scalar
Its components.
std::complex< double > dot(const std::complex< double > *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
std::complex< double > get(std::size_t j) const
Component j.
buffer< double > imaginary_side
(im, re) per component: its imaginary part.
A row-major matrix read through indices from 1, (1, 1) its first entry.
lapack_index ld
The distance between rows.
T & operator()(lapack_index i, lapack_index j) const
The entry of row i and column j (from 1).
one_based(T *first, lapack_index distance)
The matrix whose first entry is at first, its rows distance apart.
A plane rotation [c s; −s̄ c] and what it leaves of its first argument.
A real eigenvector during its back-substitution, the sums of rows against it by dot_product.
double scalar
Its components.
void set(std::size_t j, double value)
Sets component j to value.
double dot(const double *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
buffer< double > x
The components.
A real matrix's eigenvectors before their back-transformation: Xᵀ's real and imaginary parts.
buffer< double > im
Im Xᵀ, zero where every eigenvalue is real.
buffer< double > re
Re Xᵀ, row-major n × n.
A real vector that rows are summed against by dot_product.
double dot(const double *row) const
Σ row[l] v[l].
buffer< double > v
The vector.
A quotient of divided and the factor its dividend was scaled by: a type of its own,...
double factor
The dividend's scaling, 1 where none was needed.
Where a QR sweep applies its reflections: the rows and columns it updates, and Z.
std::size_t low
The active block's first row.
bool full
Whether the whole Schur form is wanted (else the active block alone).
buffer< T > * h
The Hessenberg matrix, row-major.
std::size_t high
One past its last.
buffer< T > * zt
The Schur vectors to accumulate, transposed (row-major Zᵀ), or none.
A real matrix's complex eigenvector during its back-substitution, its real and imaginary parts apart:...
void scale(std::size_t from, std::size_t to, double factor)
Scales the components from … to by factor.
buffer< double > im
The imaginary parts.
void set(std::size_t j, const std::complex< double > &value)
Sets component j to value.
std::complex< double > dot(const double *row, std::size_t from, std::size_t to) const
Σ_{l = from…to} row[l] x[l].
buffer< double > re
The real parts.
std::complex< double > scalar
Its components.
The rotation standardize_block found, and the eigenvalues of the block it standardised.
double re2
The second's real part.
double re1
The first eigenvalue's real part.
double im1
Its imaginary part (positive for a complex pair).
double im2
Its imaginary part (−im1).