8#ifndef NUMERICAL_GENERALIZED_HPP
9#define NUMERICAL_GENERALIZED_HPP
18#include <initializer_list>
37 return std::abs(z.real()) + std::abs(z.imag());
56 return s[((i - 1) *
n) + (j - 1)];
63 return t[((i - 1) *
n) + (j - 1)];
73 const std::complex<double>&
sine)
76 rotate_pair(m.data() + ((i - 1) *
n) + (first - 1), m.data() + (i *
n) + (first - 1),
last - first + 1, 1, c,
sine);
89 const std::complex<double>&
sine)
91 rotate_pair(m.data() + ((first - 1) *
n) + (j - 1), m.data() + ((first - 1) *
n) + (k - 1),
last - first + 1,
n, c,
sine);
101 const std::complex<double>&
sine)
114 const matrix<std::complex<double>>& b)
116 using C = std::complex<double>;
117 const std::size_t n {a.rows()};
129 for (std::size_t i {0}; i < n; ++i) {
130 form.zt[(i * n) + i] = C {1.0};
158 using C = std::complex<double>;
159 const std::size_t n {f.
n};
160 const double size {std::abs(f.
b(j, j))};
161 if (size > std::numeric_limits<double>::min()) {
162 const C
sign {std::conj(f.
b(j, j) / size)};
163 f.
b(j, j) = C {size};
164 for (std::size_t i {1}; i < j; ++i) {
167 for (std::size_t i {1}; i <= j; ++i) {
170 for (std::size_t i {1}; i <= n; ++i) {
171 f.
zt[((j - 1) * n) + (i - 1)] *=
sign;
177 return {f.
h(j, j), f.
b(j, j)};
192 using C = std::complex<double>;
193 const std::size_t n {f.
n};
194 std::vector<std::pair<C, C>> values(n);
198 const double safmin {std::numeric_limits<double>::min()};
199 const double ulp {std::numeric_limits<double>::epsilon()};
202 for (std::size_t i {1}; i <= n; ++i) {
203 for (std::size_t j {i > 1 ? i - 1 : 1}; j <= n; ++j) {
204 anorm += std::norm(f.
h(i, j));
206 for (std::size_t j {i}; j <= n; ++j) {
207 bnorm += std::norm(f.
b(i, j));
216 std::size_t
ilast {n};
218 std::size_t
iiter {0};
240 for (std::size_t j {
ilast - 1};; --j) {
246 f.
h(j, j - 1) = C {};
249 if (std::abs(f.
b(j, j)) <
btol) {
333 if (
iiter % 10 != 0) {
349 if (
temp2 > 0.0 && ((x /
temp2).real() *
y.real()) + ((x /
temp2).imag() *
y.imag()) < 0.0) {
358 if (
iiter % 20 == 0) {
392 f.
h(j + 1, j - 1) = C {};
398 f.
b(j + 1, j + 1) = g.r;
399 f.
b(j + 1, j) = C {};
411 return std::hypot(std::hypot(std::abs(m[0]), std::abs(m[1])), std::hypot(std::abs(m[2]), std::abs(m[3])));
426 using C = std::complex<double>;
427 using block = std::array<C, 4>;
428 const std::size_t n {f.
n};
429 const block
s0 {f.
h(j, j), f.
h(j, j + 1), f.
h(j + 1, j), f.
h(j + 1, j + 1)};
430 const block
t0 {f.
b(j, j), f.
b(j, j + 1), f.
b(j + 1, j), f.
b(j + 1, j + 1)};
431 const double smlnum {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
434 const C
ff {(
s0[3] *
t0[0]) - (
t0[3] *
s0[0])};
435 const C
gg {(
s0[3] *
t0[1]) - (
t0[3] *
s0[1])};
437 const C
zs {std::conj(-z.s)};
439 const auto columns = [](
const block& m,
double c,
const C&
sine) {
440 return block {(c * m[0]) + (
sine * m[1]), (c * m[1]) - (std::conj(
sine) * m[0]),
441 (c * m[2]) + (
sine * m[3]), (c * m[3]) - (std::conj(
sine) * m[2])};
444 const auto rows = [](
const block& m,
double c,
const C&
sine) {
445 return block {(c * m[0]) + (
sine * m[2]), (c * m[1]) + (
sine * m[3]),
446 (c * m[2]) - (std::conj(
sine) * m[0]), (c * m[3]) - (std::conj(
sine) * m[1])};
448 const block s1 {columns(
s0, z.c,
zs)};
449 const block
t1 {columns(
t0, z.c,
zs)};
450 const bool from_s {std::abs(
s0[3]) * std::abs(
t0[0]) >= std::abs(
s0[0]) * std::abs(
t0[3])};
452 const block s2 {rows(s1, q.c, q.s)};
453 const block
t2 {rows(
t1, q.c, q.s)};
457 const auto residue = [&](
const block&
now,
const block&
was) {
458 const block
back {columns(rows(
now, q.c, -q.s), z.c, -
zs)};
470 f.
h(j + 1, j) = C {};
471 f.
b(j + 1, j) = C {};
491 return s[((i - 1) *
n) + (j - 1)];
498 return t[((i - 1) *
n) + (j - 1)];
512 for (std::size_t j {first}; j <=
last; ++j) {
513 double& x {m[((i - 1) *
n) + (j - 1)]};
514 double&
y {m[((k - 1) *
n) + (j - 1)]};
515 const double t {(c * x) + (
sine *
y)};
532 for (std::size_t i {first}; i <=
last; ++i) {
533 double& x {m[((i - 1) *
n) + (j - 1)]};
534 double&
y {m[((i - 1) *
n) + (k - 1)]};
535 const double t {(c * x) + (
sine *
y)};
562 double fa {std::abs(
ft)};
564 double ha {std::abs(h)};
566 const bool swap {
ha >
fa};
573 const double ga {std::abs(
gt)};
588 if (
fa /
ga < std::numeric_limits<double>::epsilon()) {
599 const double d {
fa -
ha};
600 double l {d ==
fa ? 1.0 : d /
fa};
601 const double m {
gt /
ft};
603 const double mm {m * m};
604 const double tt {t * t};
605 const double s {std::sqrt(
tt +
mm)};
606 const double r {l == 0.0 ? std::abs(m) : std::sqrt((l * l) +
mm)};
607 const double a {0.5 * (s + r)};
611 t = l == 0.0 ? std::copysign(2.0,
ft) * std::copysign(1.0,
gt) : (
gt / std::copysign(d,
ft)) + (m / t);
614 t = ((m / (s + t)) + (m / (r + l))) * (1.0 + a);
616 l = std::sqrt((t * t) + 4.0);
638 tsign = std::copysign(1.0, out.
csr) * std::copysign(1.0, out.
csl) * std::copysign(1.0, f);
640 else if (
pmax == 2) {
641 tsign = std::copysign(1.0, out.
snr) * std::copysign(1.0, out.
csl) * std::copysign(1.0, g);
644 tsign = std::copysign(1.0, out.
snr) * std::copysign(1.0, out.
snl) * std::copysign(1.0, h);
647 out.
ssmin = std::copysign(ssmin,
tsign * std::copysign(1.0, f) * std::copysign(1.0, h));
676 constexpr double fuzzy1 {1.0 + 1.0e-5};
677 return std::max(b.floor, std::max(
fuzzy1 * ((w * b.c2) + b.c3), std::min(b.c4, 0.5 * std::max(w, b.c5))));
711 const double bsize {std::max(std::abs(
b11), std::abs(
b22))};
725 if (std::abs(s1) <= std::abs(s2)) {
744 if (std::abs(
pp *
rtmin) >= 1.0) {
754 r = std::sqrt(std::abs(
discr));
758 const double sum {
pp + std::copysign(r,
pp)};
759 const double diff {
pp - std::copysign(r,
pp)};
787 const double wabs {std::abs(out.
wr1) + std::abs(out.
wi)};
830 return std::hypot(std::hypot(x,
y), z);
844 const double safmin {std::numeric_limits<double>::min()};
845 const double s1 {
pair.scale1};
846 const double wr {
pair.wr1};
847 const double wi {
pair.wi};
848 const double s1inv {1.0 / s1};
855 const double c12 {s1 *
a12};
856 const double c21 {s1 *
a21};
878 const double t1 {std::hypot(
cz,
c21)};
884 const double an {std::abs(
a11) + std::abs(
a12) + std::abs(
a21) + std::abs(
a22)};
885 const double bn {std::abs(
b11) + std::abs(
b22)};
886 const double wabs {std::abs(
wr) + std::abs(wi)};
938 const std::size_t n {f.
n};
954 for (std::size_t j {
ifirst}; j + 2 <=
ilast; ++j) {
956 v[0] = f.
h(j, j - 1);
957 v[1] = f.
h(j + 1, j - 1);
958 v[2] = f.
h(j + 2, j - 1);
960 f.
h(j, j - 1) = v[0];
962 f.
h(j + 1, j - 1) = 0.0;
963 f.
h(j + 2, j - 1) = 0.0;
965 const double t2 {tau * v[1]};
966 const double t3 {tau * v[2]};
967 for (std::size_t
jc {j};
jc <= n; ++
jc) {
968 const double temp {f.
h(j,
jc) + (v[1] * f.
h(j + 1,
jc)) + (v[2] * f.
h(j + 2,
jc))};
972 const double temp2 {f.
b(j,
jc) + (v[1] * f.
b(j + 1,
jc)) + (v[2] * f.
b(j + 2,
jc))};
977 double*
const q0 {f.
qt.data() + ((j - 1) * n)};
978 double*
const q1 {
q0 + n};
979 double*
const q2 {
q1 + n};
980 for (std::size_t r {0}; r < n; ++r) {
981 const double temp {
q0[r] + (v[1] *
q1[r]) + (v[2] *
q2[r])};
991 const double top {std::max(std::abs(f.
b(j + 1, j + 1)), std::abs(f.
b(j + 1, j + 2)))};
992 const double bottom {std::max(std::abs(f.
b(j + 2, j + 1)), std::abs(f.
b(j + 2, j + 2)))};
1004 w11 = f.
b(j + 1, j + 1);
1005 w21 = f.
b(j + 2, j + 1);
1006 w12 = f.
b(j + 1, j + 2);
1007 w22 = f.
b(j + 2, j + 2);
1012 w21 = f.
b(j + 1, j + 1);
1013 w11 = f.
b(j + 2, j + 1);
1014 w22 = f.
b(j + 1, j + 2);
1015 w12 = f.
b(j + 2, j + 2);
1019 if (std::abs(
w12) > std::abs(
w11)) {
1033 if (std::abs(
w22) < std::abs(
u2)) {
1034 scale = std::abs(
w22 /
u2);
1036 if (std::abs(
w11) < std::abs(
u1)) {
1037 scale = std::min(scale, std::abs(
w11 /
u1));
1046 const double t1 {std::sqrt((scale * scale) + (
u1 *
u1) + (
u2 *
u2))};
1047 const double tau2 {1.0 + (scale /
t1)};
1048 const double vs {-1.0 / (scale +
t1)};
1049 const double w2 {
vs *
u1};
1050 const double w3 {
vs *
u2};
1051 const double c2 {
tau2 *
w2};
1052 const double c3 {
tau2 *
w3};
1054 for (std::size_t r {first}; r <=
last; ++r) {
1055 double*
const row {m.data() + ((r - 1) * n) + (j - 1)};
1064 double*
const z0 {f.
zt.data() + ((j - 1) * n)};
1065 double*
const z1 {
z0 + n};
1066 double*
const z2 {
z1 + n};
1067 for (std::size_t r {0}; r < n; ++r) {
1073 f.
b(j + 1, j) = 0.0;
1074 f.
b(j + 2, j) = 0.0;
1077 const std::size_t j {
ilast - 1};
1079 f.
h(j, j - 1) = g.r;
1080 f.
h(j + 1, j - 1) = 0.0;
1081 form::rotate_rows(f.
s, n, j, j + 1, j, n, g.c, g.s);
1082 form::rotate_rows(f.
t, n, j, j + 1, j, n, g.c, g.s);
1083 form::rotate_rows(f.
qt, n, j, j + 1, 1, n, g.c, g.s);
1085 f.
b(j + 1, j + 1) = h.r;
1086 f.
b(j + 1, j) = 0.0;
1087 form::rotate_columns(f.
s, n, j + 1, j, 1,
ilast, h.c, h.s);
1088 form::rotate_columns(f.
t, n, j + 1, j, 1,
ilast - 1, h.c, h.s);
1089 form::rotate_rows(f.
zt, n, j + 1, j, 1, n, h.c, h.s);
1101 const std::size_t n {a.
rows()};
1113 for (std::size_t i {0}; i < n; ++i) {
1114 form.zt[(i * n) + i] = 1.0;
1115 for (std::size_t j {0}; j < i; ++j) {
1116 form.t[(i * n) + j] = 0.0;
1154 const std::size_t n {f.
n};
1155 std::vector<real_pencil_value> values(n);
1159 constexpr double safety {1.0e2};
1160 const double safmin {std::numeric_limits<double>::min()};
1162 const double ulp {std::numeric_limits<double>::epsilon()};
1165 for (std::size_t i {1}; i <= n; ++i) {
1166 for (std::size_t j {i > 1 ? i - 1 : 1}; j <= n; ++j) {
1175 const double maxit {
static_cast<double>(steps)};
1176 std::size_t
ilast {n};
1178 std::size_t
iiter {0};
1182 if (f.
b(j, j) < 0.0) {
1183 for (std::size_t i {1}; i <= j; ++i) {
1184 f.
h(i, j) = -f.
h(i, j);
1185 f.
b(i, j) = -f.
b(i, j);
1187 for (std::size_t i {0}; i < n; ++i) {
1188 f.
zt[((j - 1) * n) + i] = -f.
zt[((j - 1) * n) + i];
1191 values[j - 1] = {f.
h(j, j), 0.0, f.
b(j, j)};
1194 return std::abs(f.
h(j, j - 1)) <= std::max(
safmin,
ulp * (std::abs(f.
h(j, j)) + std::abs(f.
h(j - 1, j - 1))));
1211 for (std::size_t j {
ilast - 1};; --j) {
1217 f.
h(j, j - 1) = 0.0;
1220 if (std::abs(f.
b(j, j)) <
btol) {
1224 double temp {std::abs(f.
h(j, j - 1))};
1225 double temp2 {std::abs(f.
h(j, j))};
1239 form::rotate_rows(f.
s, n,
jch,
jch + 1,
jch + 1, n, g.c, g.s);
1240 form::rotate_rows(f.
t, n,
jch,
jch + 1,
jch + 1, n, g.c, g.s);
1241 form::rotate_rows(f.
qt, n,
jch,
jch + 1, 1, n, g.c, g.s);
1270 form::rotate_rows(f.
t, n,
jch,
jch + 1,
jch + 2, n, g.c, g.s);
1272 form::rotate_rows(f.
s, n,
jch,
jch + 1,
jch - 1, n, g.c, g.s);
1273 form::rotate_rows(f.
qt, n,
jch,
jch + 1, 1, n, g.c, g.s);
1277 form::rotate_columns(f.
s, n,
jch,
jch - 1, 1,
jch, h.c, h.s);
1278 form::rotate_columns(f.
t, n,
jch,
jch - 1, 1,
jch - 1, h.c, h.s);
1279 form::rotate_rows(f.
zt, n,
jch,
jch - 1, 1, n, h.c, h.s);
1297 form::rotate_rows(f.
zt, n,
ilast,
ilast - 1, 1, n, g.c, g.s);
1315 if (
iiter % 10 == 0) {
1330 std::swap(shifts.wr1, shifts.wr2);
1331 std::swap(shifts.scale1, shifts.scale2);
1339 double scale {s1 >
temp ?
temp / s1 : 1.0};
1341 if (std::abs(
wr) >
temp) {
1342 scale = std::min(scale,
temp / std::abs(
wr));
1347 for (std::size_t j {
ilast - 1}; j >
ifirst; --j) {
1348 double small {std::abs(s1 * f.
h(j, j - 1))};
1349 double diag {std::abs((s1 * f.
h(j, j)) - (
wr * f.
b(j, j)))};
1350 const double tempr {std::max(small,
diag)};
1352 small /= std::max(
tempr, std::numeric_limits<double>::min());
1353 diag /= std::max(
tempr, std::numeric_limits<double>::min());
1362 double sine {first.s};
1366 f.
h(j, j - 1) = g.r;
1367 f.
h(j + 1, j - 1) = 0.0;
1371 form::rotate_rows(f.
s, n, j, j + 1, j, n, c,
sine);
1372 form::rotate_rows(f.
t, n, j, j + 1, j, n, c,
sine);
1373 form::rotate_rows(f.
qt, n, j, j + 1, 1, n, c,
sine);
1375 f.
b(j + 1, j + 1) = g.r;
1376 f.
b(j + 1, j) = 0.0;
1377 form::rotate_columns(f.
s, n, j + 1, j, 1, std::min(j + 2,
ilast), g.c, g.s);
1378 form::rotate_columns(f.
t, n, j + 1, j, 1, j, g.c, g.s);
1379 form::rotate_rows(f.
zt, n, j + 1, j, 1, n, g.c, g.s);
1408 for (std::size_t i {1}; i <=
ilast; ++i) {
1412 for (std::size_t i {0}; i < n; ++i) {
1419 if (
pair.wi == 0.0) {
1441 std::array<double, 16>
e {};
1447 return e[(i * 4) + j];
1452 std::size_t j)
const
1454 return e[(i * 4) + j];
1461 for (std::size_t i {0}; i < m; ++i) {
1476 for (std::size_t i {0}; i < m; ++i) {
1477 for (std::size_t j {0}; j < m; ++j) {
1479 for (std::size_t k {0}; k < m; ++k) {
1480 sum += (
tx ? x(k, i) : x(i, k)) * (
ty ?
y(j, k) :
y(k, j));
1496 for (std::size_t i {
r0}; i <
r1; ++i) {
1497 for (std::size_t j {
c0}; j < c1; ++j) {
1514 for (std::size_t j {0}; j < k; ++j) {
1516 for (std::size_t i {j + 1}; i < m; ++i) {
1522 const double alpha {x(j, j)};
1523 const double beta {-std::copysign(std::hypot(
alpha,
rest),
alpha)};
1524 const double tau {(beta -
alpha) / beta};
1525 std::array<double, 4> v {};
1527 for (std::size_t i {j + 1}; i < m; ++i) {
1528 v[i] = x(i, j) / (
alpha - beta);
1530 for (std::size_t c {j}; c < m; ++c) {
1532 for (std::size_t i {j}; i < m; ++i) {
1533 dot += v[i] * x(i, c);
1535 for (std::size_t i {j}; i < m; ++i) {
1536 x(i, c) -= tau * v[i] *
dot;
1539 for (std::size_t r {0}; r < m; ++r) {
1541 for (std::size_t i {j}; i < m; ++i) {
1542 dot += q(r, i) * v[i];
1544 for (std::size_t i {j}; i < m; ++i) {
1545 q(r, i) -= tau *
dot * v[i];
1566 std::array<std::array<double, 2>, 2>& b)
1568 const double safmin {std::numeric_limits<double>::min()};
1569 const double ulp {std::numeric_limits<double>::epsilon()};
1570 const double anorm {std::max({std::abs(a[0][0]) + std::abs(a[1][0]), std::abs(a[0][1]) + std::abs(a[1][1]),
safmin})};
1571 const double bnorm {std::max({std::abs(b[0][0]), std::abs(b[0][1]) + std::abs(b[1][1]),
safmin})};
1572 for (
auto&
row : a) {
1573 for (
double& x :
row) {
1577 b[0][0] *= 1.0 /
bnorm;
1578 b[0][1] *= 1.0 /
bnorm;
1579 b[1][1] *= 1.0 /
bnorm;
1581 const auto rows = [](std::array<std::array<double, 2>, 2>& m,
double c,
double s) {
1582 for (std::size_t j {0}; j < 2; ++j) {
1583 const double t {(c * m[0][j]) + (s * m[1][j])};
1584 m[1][j] = (c * m[1][j]) - (s * m[0][j]);
1588 const auto columns = [](std::array<std::array<double, 2>, 2>& m,
double c,
double s) {
1589 for (std::size_t i {0}; i < 2; ++i) {
1590 const double t {(c * m[i][0]) + (s * m[i][1])};
1591 m[i][1] = (c * m[i][1]) - (s * m[i][0]);
1596 if (std::abs(a[1][0]) <=
ulp) {
1600 else if (std::abs(b[0][0]) <=
ulp) {
1604 rows(a, out.
csl, out.
snl);
1605 rows(b, out.
csl, out.
snl);
1610 else if (std::abs(b[1][1]) <=
ulp) {
1614 columns(a, out.
csr, out.
snr);
1615 columns(b, out.
csr, out.
snr);
1622 if (
pair.wi == 0.0) {
1623 const double h1 {(
pair.scale1 * a[0][0]) - (
pair.wr1 * b[0][0])};
1624 const double h2 {(
pair.scale1 * a[0][1]) - (
pair.wr1 * b[0][1])};
1625 const double h3 {(
pair.scale1 * a[1][1]) - (
pair.wr1 * b[1][1])};
1626 const double rr {std::hypot(
h1,
h2)};
1627 const double qq {std::hypot(
pair.scale1 * a[1][0],
h3)};
1631 columns(a, out.
csr, out.
snr);
1632 columns(b, out.
csr, out.
snr);
1633 const double ha {std::max(std::abs(a[0][0]) + std::abs(a[0][1]), std::abs(a[1][0]) + std::abs(a[1][1]))};
1634 const double hb {std::max(std::abs(b[0][0]) + std::abs(b[0][1]), std::abs(b[1][0]) + std::abs(b[1][1]))};
1638 rows(a, out.
csl, out.
snl);
1639 rows(b, out.
csl, out.
snl);
1649 rows(a, out.
csl, out.
snl);
1650 rows(b, out.
csl, out.
snl);
1651 columns(a, out.
csr, out.
snr);
1652 columns(b, out.
csr, out.
snr);
1657 for (
auto&
row : a) {
1658 for (
double& x :
row) {
1662 for (
auto&
row : b) {
1663 for (
double& x :
row) {
1681 const std::size_t k {n1 *
n2};
1682 const std::size_t size {2 * k};
1683 std::array<std::array<double, 9>, 8> z {};
1684 for (std::size_t i {0}; i < n1; ++i) {
1685 for (std::size_t j {0}; j <
n2; ++j) {
1686 const std::size_t
row {(i *
n2) + j};
1687 for (std::size_t p {0}; p < n1; ++p) {
1688 z[
row][(p *
n2) + j] += s(i, p);
1689 z[
row + k][(p *
n2) + j] += t(i, p);
1691 for (std::size_t q {0}; q <
n2; ++q) {
1692 z[
row][k + (i *
n2) + q] -= s(n1 + q, n1 + j);
1693 z[
row + k][k + (i *
n2) + q] -= t(n1 + q, n1 + j);
1695 z[
row][size] = s(i, n1 + j);
1696 z[
row + k][size] = t(i, n1 + j);
1699 double largest {0.0};
1700 for (std::size_t r {0}; r < size; ++r) {
1701 for (std::size_t c {0}; c < size; ++c) {
1702 largest = std::max(largest, std::abs(z[r][c]));
1705 const double smin {std::max(std::numeric_limits<double>::epsilon() * largest, std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon())};
1706 std::array<std::size_t, 8> order {};
1707 for (std::size_t c {0}; c < size; ++c) {
1710 for (std::size_t p {0}; p < size; ++p) {
1713 for (std::size_t r {p}; r < size; ++r) {
1714 for (std::size_t c {p}; c < size; ++c) {
1715 if (std::abs(z[r][c]) > std::abs(z[
pr][
pc])) {
1721 if (!(std::abs(z[
pr][
pc]) >=
smin)) {
1722 return std::nullopt;
1724 std::swap(z[p], z[
pr]);
1725 for (std::size_t r {0}; r < size; ++r) {
1726 std::swap(z[r][p], z[r][
pc]);
1728 std::swap(order[p], order[
pc]);
1729 for (std::size_t r {p + 1}; r < size; ++r) {
1730 const double factor {z[r][p] / z[p][p]};
1731 for (std::size_t c {p}; c <= size; ++c) {
1732 z[r][c] -= factor * z[p][c];
1736 std::array<double, 8> x {};
1737 for (std::size_t p {size}; p-- > 0;) {
1738 double sum {z[p][size]};
1739 for (std::size_t c {p + 1}; c < size; ++c) {
1740 sum -= z[p][c] * x[c];
1742 x[p] =
sum / z[p][p];
1746 for (std::size_t c {0}; c < size; ++c) {
1747 const std::size_t
unknown {order[c]};
1748 if (!std::isfinite(x[c])) {
1749 return std::nullopt;
1758 return std::pair {r, l};
1781 const double ff {(s(1, 1) * t(0, 0)) - (t(1, 1) * s(0, 0))};
1782 const double gg {(s(1, 1) * t(0, 1)) - (t(1, 1) * s(0, 1))};
1783 const double sa {std::abs(s(1, 1)) * std::abs(t(0, 0))};
1784 const double sb {std::abs(s(0, 0)) * std::abs(t(1, 1))};
1801 if (!(std::abs(s(1, 0)) <=
thresha && std::abs(t(1, 0)) <=
threshb)) {
1802 return std::nullopt;
1820 const std::size_t m {n1 +
n2};
1823 return std::nullopt;
1825 const auto& [r, l] {*
solved};
1827 for (std::size_t j {0}; j <
n2; ++j) {
1828 for (std::size_t i {0}; i < n1; ++i) {
1835 for (std::size_t i {0}; i < n1; ++i) {
1837 for (std::size_t j {0}; j <
n2; ++j) {
1838 rbasis(n1 + j, i) = r(i, j);
1843 for (std::size_t c {0}; c < m; ++c) {
1844 for (std::size_t i {0}; i < n1; ++i) {
1845 ir(
n2 + i, c) =
qn(c, i);
1847 for (std::size_t i {0}; i <
n2; ++i) {
1848 ir(i, c) =
qn(c, n1 + i);
1855 for (std::size_t i {0}; i < m; ++i) {
1856 for (std::size_t j {0}; j < m; ++j) {
1857 flipped(i, j) = t(m - 1 - j, m - 1 - i);
1862 for (std::size_t i {0}; i < m; ++i) {
1863 for (std::size_t j {0}; j < m; ++j) {
1864 qrq(i, j) =
qf(m - 1 - j, m - 1 - i);
1878 return std::nullopt;
1887 for (std::size_t i {1}; i < 4; ++i) {
1888 for (std::size_t j {0}; j < i; ++j) {
1896 std::array<std::array<double, 2>, 2> a {{{s(at, at), s(at, at + 1)}, {s(at + 1, at), s(at + 1, at + 1)}}};
1897 std::array<std::array<double, 2>, 2> b {{{t(at, at), t(at, at + 1)}, {t(at + 1, at), t(at + 1, at + 1)}}};
1899 for (std::size_t i {0}; i < 2; ++i) {
1900 for (std::size_t j {0}; j < 2; ++j) {
1901 s(at + i, at + j) = a[i][j];
1902 t(at + i, at + j) = b[i][j];
1905 left(at, at) = g.csl;
1906 left(at + 1, at) = g.snl;
1907 left(at, at + 1) = -g.snl;
1908 left(at + 1, at + 1) = g.csl;
1909 right(at, at) = g.csr;
1910 right(at + 1, at) = g.snr;
1911 right(at, at + 1) = -g.snr;
1912 right(at + 1, at + 1) = g.csr;
1923 for (std::size_t i {0}; i <
n2; ++i) {
1924 for (std::size_t j {
n2}; j < m; ++j) {
1929 return block_exchange {s, t,
small_product(li,
false,
left,
false, m),
small_product(ir,
true,
right,
false, m)};
1946 const std::size_t n {f.
n};
1947 const std::size_t m {n1 +
n2};
1950 for (std::size_t i {0}; i < m; ++i) {
1951 for (std::size_t j {0}; j < m; ++j) {
1952 s(i, j) = f.
h(
j1 + i,
j1 + j);
1953 t(i, j) = f.
b(
j1 + i,
j1 + j);
1956 const double eps {std::numeric_limits<double>::epsilon()};
1957 const double smlnum {std::numeric_limits<double>::min() /
eps};
1964 for (
const bool of_s : {
true,
false}) {
1967 for (std::size_t i {0}; i < m; ++i) {
1968 for (std::size_t j {0}; j < m; ++j) {
1978 const std::size_t
lead {m == 2 ? 1 :
n2};
1979 for (std::size_t i {0}; i < m; ++i) {
1980 for (std::size_t j {0}; j < m; ++j) {
1981 const bool below {i >=
lead && j <
lead};
1982 f.
h(
j1 + i,
j1 + j) = below ? 0.0 :
plan->s(i, j);
1983 f.
b(
j1 + i,
j1 + j) = below ? 0.0 :
plan->t(i, j);
1988 std::array<double, 4> v {};
1989 for (std::size_t c {0}; c < m; ++c) {
1990 for (std::size_t k {0}; k < m; ++k) {
1991 v[c] += x[((
row - 1) * n) + (
j1 - 1 + k)] * ir(k, c);
1994 for (std::size_t c {0}; c < m; ++c) {
1995 x[((
row - 1) * n) + (
j1 - 1 + c)] = v[c];
2001 std::array<double, 4> v {};
2002 for (std::size_t
r2 {0};
r2 < m; ++
r2) {
2003 for (std::size_t k {0}; k < m; ++k) {
2004 v[
r2] += li(k,
r2) * x[((
j1 - 1 + k) * n) + (
col - 1)];
2007 for (std::size_t
r2 {0};
r2 < m; ++
r2) {
2008 x[((
j1 - 1 +
r2) * n) + (
col - 1)] = v[
r2];
2017 for (std::size_t
row {1};
row <= n; ++
row) {
2018 std::array<double, 4> v {};
2019 for (std::size_t c {0}; c < m; ++c) {
2020 for (std::size_t k {0}; k < m; ++k) {
2021 v[c] +=
xt[((
j1 - 1 + k) * n) + (
row - 1)] * factor(k, c);
2024 for (std::size_t c {0}; c < m; ++c) {
2025 xt[((
j1 - 1 + c) * n) + (
row - 1)] = v[c];
2041 throw convergence_error(
"generalized Schur form: eigenvalues could not be separated for reordering");
2056 const std::size_t n {f.
n};
2060 std::size_t
nbf {
ifst < n && f.
h(
ifst + 1,
ifst) != 0.0 ? std::size_t {2} : std::size_t {1}};
2066 const std::size_t
nbnext {
here >= 3 && f.
h(
here - 1,
here - 2) != 0.0 ? std::size_t {2} : std::size_t {1}};
2101 const std::size_t n {f.
n};
2102 std::vector<real_pencil_value> values(n);
2103 for (std::size_t k {1}; k <= n; ++k) {
2104 if (k < n && f.
h(k + 1, k) != 0.0) {
2105 const pencil_pair pair {
pencil_eigenvalues(f.
h(k, k), f.
h(k, k + 1), f.
h(k + 1, k), f.
h(k + 1, k + 1), f.
b(k, k), f.
b(k, k + 1), f.
b(k + 1, k + 1),
2106 std::numeric_limits<double>::min())};
2112 if (std::signbit(f.
b(k, k))) {
2113 for (std::size_t i {1}; i <= n; ++i) {
2114 f.
h(k, i) = -f.
h(k, i);
2115 f.
b(k, i) = -f.
b(k, i);
2116 f.
qt[((k - 1) * n) + (i - 1)] = -f.
qt[((k - 1) * n) + (i - 1)];
2119 values[k - 1] = {f.
h(k, k), 0.0, f.
b(k, k)};
2131 template <
typename T>
2134 const double smlnum {std::sqrt(std::numeric_limits<double>::min()) / std::numeric_limits<double>::epsilon()};
2137 for (
const T& x : m) {
2138 norm = std::max(
norm,
static_cast<double>(std::abs(x)));
2144 const double factor {
to /
norm};
2146 for (
T& x : entries) {
2153 template <
typename T>
2159 for (
T& x : entries) {
2162 return matrix<T> {n, n, std::move(entries)};
2179 using selection = std::function<
bool (
const std::complex<double>&,
const std::complex<double>&)>;
2188 const matrix<std::complex<double>>& b)
2191 30 * std::
max<std::
size_t>(a.rows(), 1))
2196 const matrix<std::complex<double>>& b,
2199 const std::size_t n {a.rows()};
2200 if (a.cols() != n || b.rows() != n || b.cols() != n) {
2201 throw dimension_error(
"the generalized Schur decomposition requires two square matrices of one order");
2254 const std::size_t n {
form_.
n};
2255 if (
chosen.size() != n) {
2256 throw dimension_error(
"generalized Schur reordering requires one choice per eigenvalue");
2259 std::size_t
moved {0};
2260 for (std::size_t k {0}; k < n; ++k) {
2264 for (std::size_t j {k}; j >
moved; --j) {
2266 throw convergence_error(
"generalized Schur form: eigenvalues could not be separated for reordering");
2271 std::vector<std::pair<std::complex<double>, std::complex<double>>>
standardized(n);
2272 for (std::size_t k {1}; k <= n; ++k) {
2276 form_ = std::move(work);
2285 for (std::size_t k {0}; k <
values_.size(); ++k) {
2295 std::vector<std::pair<std::complex<double>, std::complex<double>>>
raw)
const
2305 std::vector<std::pair<std::complex<double>, std::complex<double>>>
values_;
2323 const matrix<std::complex<double>>& t,
2324 const std::vector<std::pair<std::complex<double>, std::complex<double>>>& values,
2328 using C = std::complex<double>;
2329 const std::size_t n {s.
rows()};
2332 for (
const C& x : s) {
2335 for (
const C& x : t) {
2340 const C
alpha {values[k].first};
2341 const C beta {values[k].second};
2342 C* x {
solved.data() + k};
2344 if (std::abs(
alpha) <= std::numeric_limits<double>::min() && std::abs(beta) <= std::numeric_limits<double>::min()) {
2349 const double smallest {std::max(std::numeric_limits<double>::epsilon() * ((std::abs(beta) *
s_norm) + (std::abs(
alpha) *
t_norm)),
2350 std::numeric_limits<double>::min())};
2351 const auto entry = [&](std::size_t i, std::size_t j) {
return (beta * s(i, j)) - (
alpha * t(i, j)); };
2352 const auto pivot = [&](std::size_t i) {
2353 const C m {
entry(i, i)};
2360 const auto contained = [x, n](std::size_t at, std::size_t first, std::size_t
last) {
2361 const double size {std::max(std::abs(x[at * n].real()), std::abs(x[at * n].
imag()))};
2362 if (size > 0x1p256) {
2363 const double down {std::ldexp(1.0, -std::ilogb(size))};
2364 for (std::size_t r {first}; r <=
last; ++r) {
2370 for (std::size_t i {k}; i-- > 0;) {
2372 for (std::size_t j {i + 1}; j <= k; ++j) {
2375 x[i * n] = -
sum / pivot(i);
2380 for (std::size_t i {k + 1}; i < n; ++i) {
2382 for (std::size_t j {k}; j < i; ++j) {
2383 sum += std::conj(
entry(j, i)) * x[j * n];
2385 x[i * n] = -
sum / std::conj(pivot(i));
2392 for (std::size_t k {0}; k < n; ++k) {
2394 for (std::size_t r {0}; r < n; ++r) {
2395 norm = std::hypot(
norm, std::abs(out[(r * n) + k]));
2397 for (std::size_t r {0}; r < n; ++r) {
2398 out[(r * n) + k] /=
norm;
2401 return matrix<C> {n, n, std::move(out)};
2440 30 * std::
max<std::
size_t>(a.rows(), 1))
2448 const std::size_t n {a.
rows()};
2450 throw dimension_error(
"the generalized Schur decomposition requires two square matrices of one order");
2494 using selection = std::function<
bool (
const std::complex<double>&,
const std::complex<double>&)>;
2507 const std::size_t n {
form_.
n};
2508 if (
chosen.size() != n) {
2509 throw dimension_error(
"generalized Schur reordering requires one choice per eigenvalue");
2512 std::size_t
moved {0};
2513 for (std::size_t k {1}; k <= n; ++k) {
2514 const bool pair {k < n && work.
h(k + 1, k) != 0.0};
2522 form_ = std::move(work);
2531 for (std::size_t k {0}; k <
values_.size(); ++k) {
2546 const double safmin {std::numeric_limits<double>::min()};
2553 const std::size_t n {
form_.
n};
2554 for (std::size_t i {0}; i <
raw.size(); ++i) {
2596 using C = std::complex<double>;
2606 for (std::size_t j {k}; j < n; ++j) {
2607 const C a {m[(k * n) + j]};
2608 const C b {m[((k + 1) * n) + j]};
2609 m[(k * n) + j] = (std::conj(
u0) * a) + (std::conj(
u1) * b);
2610 m[((k + 1) * n) + j] = (-
u1 * a) + (
u0 * b);
2615 for (std::size_t i {0}; i < rows; ++i) {
2616 const C a {m[(i * n) + k]};
2617 const C b {m[(i * n) + k + 1]};
2618 m[(i * n) + k] = (a *
v0) + (b *
v1);
2619 m[(i * n) + k + 1] = (-a * std::conj(
v1)) + (b * std::conj(
v0));
2624 if (s[((k + 1) * n) + k] == C {}) {
2630 const C
lambda {C {value.alphar, value.alphai} / value.beta};
2631 const auto m = [&](std::size_t i, std::size_t j) {
return s[(i * n) + j] - (
lambda * t[(i * n) + j]); };
2632 const bool upper {std::hypot(std::abs(m(k, k)), std::abs(m(k, k + 1))) >= std::hypot(std::abs(m(k + 1, k)), std::abs(m(k + 1, k + 1)))};
2633 C
v0 {
upper ? m(k, k + 1) : m(k + 1, k + 1)};
2634 C
v1 {
upper ? -m(k, k) : -m(k + 1, k)};
2635 const double v_norm {std::hypot(std::abs(
v0), std::abs(
v1))};
2638 C
u0 {(t[(k * n) + k] *
v0) + (t[(k * n) + k + 1] *
v1)};
2639 C
u1 {t[((k + 1) * n) + k + 1] *
v1};
2640 const double u_norm {std::hypot(std::abs(
u0), std::abs(
u1))};
2647 s[((k + 1) * n) + k] = C {};
2648 t[((k + 1) * n) + k] = C {};
2657 std::vector<std::pair<C, C>>
diagonal(n);
2658 for (std::size_t i {0}; i < n; ++i) {
2659 diagonal[i] = {s[(i * n) + i], t[(i * n) + i]};
2676 constexpr double radix {2.0};
2677 const double sfmin1 {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
2684 for (std::size_t i {0}; i < n; ++i) {
2689 for (std::size_t k {0}; k < n; ++k) {
2690 c = std::hypot(c, m[(k * n) + i]);
2691 r = std::hypot(r, m[(i * n) + k]);
2692 ca = std::max(
ca, m[(k * n) + i]);
2693 ra = std::max(
ra, m[(i * n) + k]);
2695 if (c == 0.0 || r == 0.0) {
2698 const double before {c + r};
2700 double g {r /
radix};
2701 while (c < g && std::max({f, c,
ca}) <
sfmax2 && std::min({r, g,
ra}) >
sfmin2) {
2710 while (g >= r && std::max(r,
ra) <
sfmax2 && std::min({f, c, g,
ca}) >
sfmin2) {
2718 const bool too_small {f < 1.0 && scale[i] < 1.0 && f * scale[i] <=
sfmin1};
2719 const bool too_large {f > 1.0 && scale[i] > 1.0 && scale[i] >=
sfmax1 / f};
2725 for (std::size_t k {0}; k < n; ++k) {
2726 m[(i * n) + k] /= f;
2727 m[(k * n) + i] *= f;
2735 template <
typename T>
2738 double largest {0.0};
2739 for (std::size_t j {0}; j < a.
cols(); ++j) {
2741 for (std::size_t i {0}; i < a.
rows(); ++i) {
2742 sum += std::abs(a(i, j));
2744 largest = std::max(largest,
sum);
2750 template <
typename T>
2769 :
"The associated symplectic pencil has eigenvalues too close to the unit circle");
2780 template <
typename T>
2785 const std::size_t m {
top.
rows()};
2788 for (std::size_t i {0}; i < m; ++i) {
2789 for (std::size_t k {i}; k < m; ++k) {
2790 upper[(i * m) + k] = factors(i, k);
2794 if (!(sigma[m - 1] > std::numeric_limits<double>::epsilon() * sigma[0])) {
2809 template <
typename T>
2813 const std::size_t m {terms.
a.rows()};
2814 const std::size_t n {terms.
b.cols()};
2815 const std::size_t order {(2 * m) + n};
2818 const auto e_at = [&terms](std::size_t
row, std::size_t
col) {
2819 return terms.
e !=
nullptr ? (*terms.
e)(
row,
col) :
T {
row ==
col ? 1.0 : 0.0};
2821 for (std::size_t i {0}; i < m; ++i) {
2822 for (std::size_t k {0}; k < m; ++k) {
2823 h[(i * order) + k] = terms.
a(i, k);
2824 h[((m + i) * order) + k] = -terms.
q(i, k);
2825 j[(i * order) + k] =
e_at(i, k);
2829 for (std::size_t k {0}; k < n; ++k) {
2830 h[(i * order) + (2 * m) + k] = terms.
b(i, k);
2832 h[(((2 * m) + k) * order) + m + i] =
conj_of(terms.
b(i, k));
2835 j[(((2 * m) + k) * order) + m + i] = -
conj_of(terms.
b(i, k));
2837 if (terms.
s !=
nullptr) {
2838 h[((m + i) * order) + (2 * m) + k] = -(*terms.
s)(i, k);
2839 h[(((2 * m) + k) * order) + i] =
conj_of((*terms.
s)(i, k));
2843 for (std::size_t i {0}; i < n; ++i) {
2844 for (std::size_t k {0}; k < n; ++k) {
2845 h[(((2 * m) + i) * order) + (2 * m) + k] = terms.
r(i, k);
2848 return {std::move(h), std::move(j)};
2857 template <
typename T>
2864 for (std::size_t i {0}; i < order; ++i) {
2865 for (std::size_t k {0}; k < order; ++k) {
2866 magnitudes[(i * order) + k] = i == k ? 0.0 : std::abs(h[(i * order) + k]) + std::abs(j[(i * order) + k]);
2871 if (std::all_of(
found.begin(),
found.end(), [](
double v) { return std::abs(v - 1.0) <= 1e-8 + 1e-5; })) {
2874 for (std::size_t i {0}; i < m; ++i) {
2875 const double half {std::nearbyint((std::log2(
found[m + i]) - std::log2(
found[i])) / 2.0)};
2876 scale[i] = std::exp2(half);
2877 scale[m + i] = std::exp2(-half);
2879 std::copy(
found.begin() +
static_cast<std::ptrdiff_t
>(2 * m),
found.end(),
2880 scale.begin() +
static_cast<std::ptrdiff_t
>(2 * m));
2881 for (std::size_t i {0}; i < order; ++i) {
2882 for (std::size_t k {0}; k < order; ++k) {
2883 h[(i * order) + k] *= scale[i] / scale[k];
2884 j[(i * order) + k] *= scale[i] / scale[k];
2905 template <
typename T>
2911 const std::size_t m {terms.
a.rows()};
2912 const std::size_t n {terms.
b.cols()};
2913 const std::size_t order {(2 * m) + n};
2917 for (std::size_t i {0}; i < order; ++i) {
2918 std::copy_n(h.data() + (i * order) + (2 * m), n,
last.data() + (i * n));
2924 for (std::size_t t {0}; t < order; ++t) {
2925 std::copy_n(&
deflation(t, n), 2 * m,
kept.data() + (t * 2 * m));
2926 std::copy_n(h.data() + (t * order), 2 * m,
h_left.data() + (t * 2 * m));
2927 std::copy_n(j.data() + (t * order), 2 * m,
j_left.data() + (t * 2 * m));
2932 return (
alpha * std::conj(beta)).real() < 0.0;
2934 :
pencil.sort([](
const std::complex<double>&
alpha,
const std::complex<double>& beta) {
2935 return std::abs(
alpha) < std::abs(beta);
2941 if (terms.
e !=
nullptr) {
2944 for (std::size_t i {0}; i < m; ++i) {
2945 for (std::size_t t {0}; t < m; ++t) {
2946 scaled_e[(i * m) + t] = (*terms.
e)(i, t) * (scale[i] / scale[t]);
2947 upper[(i * m) + t] = u(i, t);
2953 for (std::size_t i {0}; i < m; ++i) {
2954 for (std::size_t k {0}; k < m; ++k) {
2955 stacked[((m + i) * m) + k] = u(m + i, k);
2962 for (std::size_t i {0}; i < m; ++i) {
2963 for (std::size_t k {0}; k < m; ++k) {
2964 u00[(i * m) + k] = u(i, k);
2965 u10[(i * m) + k] = u(m + i, k);
2970 for (std::size_t i {0}; i < m; ++i) {
2971 for (std::size_t k {0}; k < m; ++k) {
2972 out[(i * m) + k] = (x(i, k) +
conj_of(x(k, i))) * (scale[i] * scale[k] / 2.0);
2975 return matrix<T> {m, m, std::move(out)};
2983 const matrix<std::complex<double>>& x,
2986 using C = std::complex<double>;
2989 if (terms.
s !=
nullptr) {
3001 return std::all_of(
xs.begin(),
xs.end(), [](
const matrix<std::complex<double>>* x) {
3002 return std::all_of(x->begin(), x->end(), [](const std::complex<double>& z) { return is_finite_entry(z); });
3012 const matrix<std::complex<double>>& x)
3014 using C = std::complex<double>;
3018 if (terms.
s !=
nullptr) {
3023 return std::isfinite(
error) ?
error : std::numeric_limits<double>::infinity();
3034 matrix<std::complex<double>>&& x)
3036 using C = std::complex<double>;
3041 return std::move(x);
3046 const std::size_t m {x.rows()};
3048 for (std::size_t i {0}; i < m; ++i) {
3049 for (std::size_t k {0}; k < m; ++k) {
3050 stepped[(i * m) + k] = x(i, k) + ((delta(i, k) + std::conj(delta(k, i))) / 2.0);
3058 return std::move(x);
3066 const matrix<std::complex<double>>& )
3068 return std::move(x);
3076 std::transform(x.begin(), x.end(), real.begin(), [](
const std::complex<double>& z) { return z.real(); });
3089 if (
norm_one(x -
adjoint_of(x)) > 100.0 * (std::nextafter(size, std::numeric_limits<double>::infinity()) - size)) {
3090 throw argument_error(std::string {
"Matrix "} + name +
" should be symmetric/hermitian.");
3102 template <
typename T>
3106 const std::size_t order {2 * m};
3108 const auto at {[&h, order](std::size_t i, std::size_t j) {
return std::abs(h[(i * order) + j]); }};
3109 for (
bool moved {
true}; moved;) {
3111 for (std::size_t i {0}; i < m; ++i) {
3112 const std::size_t pair {m + i};
3114 double shrunk {0.0};
3115 const double grown_twice {at(pair, i)};
3116 const double shrunk_twice {at(i, pair)};
3117 for (std::size_t k {0}; k < order; ++k) {
3118 if (k != i && k != pair) {
3119 grown += at(k, i) + at(pair, k);
3120 shrunk += at(i, k) + at(k, pair);
3123 if (!(std::min(grown + grown_twice, shrunk + shrunk_twice) > 0.0)) {
3126 const auto sum {[grown, grown_twice, shrunk, shrunk_twice](
double f) {
return (grown * f) + (grown_twice * f * f) + (shrunk / f) + (shrunk_twice / (f * f)); }};
3128 while (
sum(2.0 * f) <
sum(f)) {
3131 while (
sum(0.5 * f) <
sum(f)) {
3134 if (!(
sum(f) < 0.95 *
sum(1.0))) {
3137 for (std::size_t k {0}; k < order; ++k) {
3138 h[(i * order) + k] /= f;
3139 h[(pair * order) + k] *= f;
3141 for (std::size_t k {0}; k < order; ++k) {
3142 h[(k * order) + i] *= f;
3143 h[(k * order) + pair] /= f;
3164 template <
typename T>
3172 const std::size_t m {a.
rows()};
3178 shift = a - (b * cross);
3179 weight = q - (*s * cross);
3181 const std::size_t order {2 * m};
3183 for (std::size_t i {0}; i < m; ++i) {
3184 for (std::size_t j {0}; j < m; ++j) {
3185 h[(i * order) + j] = shift(i, j);
3186 h[(i * order) + m + j] = -(g(i, j) +
conj_of(g(j, i))) / 2.0;
3187 h[((m + i) * order) + j] = -(weight(i, j) +
conj_of(weight(j, i))) / 2.0;
3188 h[((m + i) * order) + m + j] = -
conj_of(shift(j, i));
3193 const std::vector<std::complex<double>> values {form.values()};
3194 std::vector<bool> chosen(order);
3195 for (std::size_t k {0}; k < order; ++k) {
3196 chosen[k] = values[k].real() < 0.0;
3198 if (form.reorder(chosen) != m) {
3199 throw convergence_error(
"The associated Hamiltonian matrix has eigenvalues too close to the imaginary axis");
3203 for (std::size_t i {0}; i < m; ++i) {
3204 for (std::size_t k {0}; k < m; ++k) {
3205 u11[(i * m) + k] = form.z()(i, k);
3206 u21[(i * m) + k] = form.z()(m + i, k);
3211 for (std::size_t i {0}; i < m; ++i) {
3212 for (std::size_t k {0}; k < m; ++k) {
3213 out[(i * m) + k] = (x(i, k) +
conj_of(x(k, i))) / (2.0 * d[i] * d[k]);
3216 return matrix<T> {m, m, std::move(out)};
3223 template <
typename T>
3233 const char* name {continuous ?
"solve_continuous_are" :
"solve_discrete_are"};
3234 const std::size_t m {a.
rows()};
3235 const std::size_t n {b.
cols()};
3236 const bool e_fits {e ==
nullptr || (e->
rows() == m && e->
cols() == m)};
3237 const bool s_fits {s ==
nullptr || (s->
rows() == m && s->
cols() == n)};
3238 if (m == 0 || n == 0 || a.
cols() != m || b.
rows() != m || q.
rows() != m || q.
cols() != m || r.
rows() != n
3239 || r.
cols() != n || !e_fits || !s_fits) {
3241 +
" requires a square a (m × m, m ≥ 1), b (m × n, n ≥ 1), q (m × m), r (n × n), "
3242 "e (m × m) and s (m × n)");
3244 for (
const matrix<T>* operand : {&a, &b, &q, &r, e, s}) {
3245 if (operand !=
nullptr) {
3255 bool hamiltonian {
false};
3258 if (!(sigma[n - 1] >= std::numeric_limits<double>::epsilon() *
norm_one(cr)) || sigma[n - 1] == 0.0) {
3262 hamiltonian = e ==
nullptr && sigma[n - 1] >= std::sqrt(std::numeric_limits<double>::epsilon()) * sigma[0];
3264 std::optional<matrix<std::complex<double>>> ce;
3265 std::optional<matrix<std::complex<double>>> cs;
3269 if (!(sigma[0] * std::numeric_limits<double>::epsilon() < sigma[m - 1])) {
3276 const riccati_terms terms {ca, cb, cq, cr, ce ? &*ce :
nullptr, cs ? &*cs :
nullptr};
3318 template <
typename T>
3319 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3324 const std::type_identity_t<
matrix<T>>* e =
nullptr,
3325 const std::type_identity_t<
matrix<T>>* s =
nullptr,
3326 bool balanced =
true)
3328 return detail::solve_are(a, b, q, r, e, s, balanced,
true);
3352 template <
typename T>
3353 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3358 const std::type_identity_t<
matrix<T>>* e =
nullptr,
3359 const std::type_identity_t<
matrix<T>>* s =
nullptr,
3360 bool balanced =
true)
3362 return detail::solve_are(a, b, q, r, e, s, balanced,
false);
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Thrown when an iterative algorithm has not converged within its bound of sweeps.
Thrown when an operation's operands have incompatible shapes.
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
The generalized Schur decomposition of a complex pencil A − λ B, A = Q S Zᴴ and B = Q T Zᴴ,...
std::vector< std::pair< std::complex< double >, std::complex< double > > > unscaled(std::vector< std::pair< std::complex< double >, std::complex< double > > > raw) const
The eigenvalues of the scaled form raw taken back: α by A's factor, β by B's.
std::vector< std::pair< std::complex< double >, std::complex< double > > > values_
The eigenvalues as (α, β).
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen are set to the leading diagonal places,...
const std::vector< std::pair< std::complex< double >, std::complex< double > > > & values() const noexcept
The eigenvalues as (α, β), in the diagonals' order: α = S(k, k), β = T(k, k).
generalized_schur(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b)
Decomposes the pencil of a and b.
matrix< std::complex< double > > s() const
S, upper triangular.
std::function< bool(const std::complex< double > &, const std::complex< double > &)> selection
The selection scipy.linalg.ordqz takes: true for (α, β) to lead.
generalized_schur(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b, std::size_t steps)
Decomposes the pencil within steps QZ iterations (zhgeqz's bound 30 n by default).
matrix< std::complex< double > > t() const
T, upper triangular, its diagonal real and non-negative.
detail::qz_form form_
S, T, Q and Z, of the scaled pencil.
matrix< std::complex< double > > q() const
Q, unitary: A = Q S Zᴴ.
double a_back_
The factor taking S back to A's scale.
std::size_t sort(const selection &select)
The eigenvalues select holds moved first (reorder), as scipy.linalg.ordqz(…, sort=…) sorts them.
matrix< std::complex< double > > z() const
Z, unitary.
An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of ...
matrix< T > factors() const &
L and U in one matrix, as LAPACK's dgetrf leaves them: U on and above the diagonal,...
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.
A QR factorisation A = Q R of an m × n matrix, as NumPy's qr, reduced by default.
The generalized real Schur decomposition of a real pencil A − λ B, A = Q S Zᵀ and B = Q T Zᵀ,...
matrix< double > t() const
T, upper triangular, its diagonal non-negative.
double a_back_
The factor taking S back to A's scale.
std::size_t sort(const selection &select)
The eigenvalues select holds moved first (reorder), as scipy.linalg.ordqz(…, sort=…) sorts them.
const std::vector< detail::real_pencil_value > & values() const noexcept
The eigenvalues as (αr, αi, β), in the diagonal's order.
std::function< bool(const std::complex< double > &, const std::complex< double > &)> selection
The selection scipy.linalg.ordqz takes: true for (α, β) to lead, α = αr + i αi.
matrix< double > s() const
S, quasi-triangular.
matrix< double > z() const
Z, orthogonal.
detail::real_qz_form form_
S, T, Q and Z, of the scaled pencil.
real_generalized_schur(const matrix< double > &a, const matrix< double > &b, std::size_t steps)
Decomposes the pencil within steps QZ iterations (dhgeqz's bound 30 n by default).
matrix< double > q() const
Q, orthogonal: A = Q S Zᵀ.
real_generalized_schur(const matrix< double > &a, const matrix< double > &b)
Decomposes the pencil of a and b.
std::vector< detail::real_pencil_value > unscaled(std::vector< detail::real_pencil_value > raw) const
The eigenvalues of the scaled form raw taken back, as dgges takes them: α by A's factor,...
std::vector< detail::real_pencil_value > values_
The eigenvalues.
std::size_t reorder(const std::vector< bool > &chosen)
Moves the eigenvalues whose entries of chosen are set to the leading diagonal places,...
The Schur decomposition A = Z T Zᴴ of a square matrix, as scipy.linalg.schur (LAPACK's dgees/zgees): ...
Thrown when a matrix has no unique solution (it is singular).
A dense vector of T with value semantics.
Functions of a square matrix and the matrix equations solved through Schur forms: the exponential,...
std::pair< matrix< T >, double > pencil_operand_in_range(const matrix< T > &m)
m brought into the range [√safmin / ε, ε / √safmin] of its largest magnitude where it lies outside,...
double pencil_wsize(const pencil_bounds &b, double w) noexcept
dlag2's WSIZE: the divisor that keeps an eigenvalue of magnitude w in range.
void exchange_or_refuse(real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
exchange_real_blocks, a refusal thrown as real_generalized_schur::reorder reports it.
std::optional< std::pair< small_square, small_square > > generalized_sylvester(const small_square &s, const small_square &t, std::size_t n1, std::size_t n2)
The solution (R, L) (n1 × n2 each) of the generalized Sylvester equations S₁₁ R − L S₂₂ = S₁₂,...
small_square small_product(const small_square &x, bool tx, const small_square &y, bool ty, std::size_t m)
op(x) op(y) of order m, op the transpose where tx (ty).
std::optional< block_exchange > plan_single_exchange(small_square s, small_square t, double thresha, double threshb)
Two 1 × 1 blocks' exchange, as LAPACK's dtgex2 makes it: columns turned onto the second eigenvalue's ...
real_qz_form real_hessenberg_triangular(const matrix< double > &a, const matrix< double > &b)
The real a and b to Hessenberg-triangular form, as LAPACK's dgges begins: B = Q R by the QR factorisa...
double norm_one(const matrix< T > &a)
The 1-norm of a: its largest column sum of moduli.
matrix< std::complex< double > > triangular_pencil_vectors(const matrix< std::complex< double > > &s, const matrix< std::complex< double > > &t, const std::vector< std::pair< std::complex< double >, std::complex< double > > > &values, const matrix< std::complex< double > > &basis, bool left)
The right (or, where left, the left) eigenvectors of the triangular pencil (s, t) whose diagonal is v...
buffer< double > scaling_balance(buffer< double > &m, std::size_t n)
The scaling of LAPACK's ‘dgebal('S’)for the non-negativen × n\p m (row-major, scaled in place): rows ...
matrix< T > scaled_back(const buffer< T > &m, std::size_t n, double factor)
The entries of m multiplied by factor, n × n row-major (the scaled form taken back).
std::optional< block_exchange > plan_block_exchange(small_square s, small_square t, std::size_t n1, std::size_t n2, double thresha)
The exchange of blocks of orders n1 and n2 (one of them 2), as LAPACK's dtgex2 makes it: orthogonal b...
double modulus_one(const std::complex< double > &z)
|Re z| + |Im z|, LAPACK's ABS1.
pencil_pair pencil_eigenvalues(double a11, double a12, double a21, double a22, double b11, double b12, double b22, double safmin)
The eigenvalues of the pencil A − w B, A (a11 a12 / a21 a22) and the upper triangular B (b11 b12 / 0 ...
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
void reflect_columns(T *panel, std::size_t height, const buffer< T > &v, std::size_t first, std::size_t from, std::size_t to, const T &s=T {2})
Applies I − s v vᴴ from the left (s 2 for a unit v) to the columns from…to-1 of the column-major pane...
matrix< std::complex< double > > answer_like(matrix< std::complex< double > > &&x, const matrix< std::complex< double > > &)
x itself, for complex operands like.
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::vector< real_pencil_value > real_values(real_qz_form &f)
The eigenvalues of the real generalized Schur form f after a reordering, as LAPACK's dtgsen gives the...
matrix< std::complex< double > > continuous_residual(const riccati_terms &terms, const matrix< std::complex< double > > &x, matrix< std::complex< double > > &closed)
The residual Aᴴ X E + Eᴴ X A − (Eᴴ X B + S) R⁻¹ (Bᴴ X E + Sᴴ) + Q of the continuous equation at the H...
qz_form hessenberg_triangular(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b)
a and b (n × n, row-major) to Hessenberg-triangular form, as LAPACK's zgges begins: B = Q R by the QR...
std::pair< std::complex< double >, std::complex< double > > standardize(qz_form &f, std::size_t j)
T(j, j) made real and non-negative, as zhgeqz standardises it: row j of T and S above the diagonal an...
double frobenius_two(const std::array< std::complex< double >, 4 > &m)
The Frobenius norm of the 2 × 2 block m.
bool exchange_real_blocks(real_qz_form &f, std::size_t j1, std::size_t n1, std::size_t n2)
Exchanges the adjacent diagonal blocks of orders n1 and n2 (1 or 2) at j1 (from 1) of the real genera...
void move_real_block_up(real_qz_form &f, std::size_t ifst, std::size_t ilst)
Moves the diagonal block at ifst (from 1) of the real generalized Schur form f up to ilst,...
matrix< std::complex< double > > newton_refined(const riccati_terms &terms, matrix< std::complex< double > > &&x)
One step of Newton's method on the continuous equation from the Schur method's x (Kleinman,...
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).
void double_shift_sweep(real_qz_form &f, std::size_t ifirst, std::size_t ilast, double ascale, double bscale, double safmin)
One double-shift QZ sweep (Moler and Stewart) on rows and columns ifirst … ilast of f,...
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 continuous_backward_error(const riccati_terms &terms, const matrix< std::complex< double > > &x)
The residual at x of the continuous equation without E (the Hamiltonian's), relative to its terms: ‖R...
double small_reflector(double(&v)[3], std::size_t count)
The Householder reflection I − τ v vᵀ, v = (1, x…), that takes (α, x…) to (β, 0…),...
std::vector< std::pair< std::complex< double >, std::complex< double > > > qz_iteration(qz_form &f, std::size_t steps)
The Hessenberg-triangular f to generalized Schur form, as LAPACK's zhgeqz (Schur form,...
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...
buffer< double > balance_pencil(buffer< T > &h, buffer< T > &j, std::size_t m, std::size_t order)
Balances the pencil (H, J) of order 2m + n as SciPy does: ‘dgebal('S’)scaling of|H| + |J|off the diag...
bool exchange_pencil_diagonal(qz_form &f, std::size_t j)
Exchanges the diagonal entries j and j + 1 (from 1) of the triangular pencil f, as LAPACK's ztgex2: c...
const matrix< std::complex< double > > & as_complex(const matrix< std::complex< double > > &a)
a itself: already complex.
std::pair< buffer< T >, buffer< T > > riccati_pencil(const riccati_operands< T > &terms, bool continuous)
The extended pencil (H, J) of order 2m + n of SciPy's solve_continuous_are (continuous) or solve_disc...
small_square small_qr(small_square x, std::size_t m, std::size_t k)
The orthogonal Q (order m) of the Householder QR factorisation of the first k columns of x (m × k,...
void require_hermitian(const matrix< std::complex< double > > &x, const char *name)
Refuses x (named name in the message) unless Hermitian, as SciPy's _are_validate_args: ‖X − Xᴴ‖₁ with...
buffer< double > balance_hamiltonian(buffer< T > &h, std::size_t m)
The diagonal D of a symplectic balancing of the Hamiltonian h of order 2m (row-major,...
pencil_rotations standardize_pencil(std::array< std::array< double, 2 >, 2 > &a, std::array< std::array< double, 2 >, 2 > &b)
The 2 × 2 pencil (a, b), b upper triangular, standardized, as LAPACK's dlagv2: two real eigenvalues m...
std::pair< real_pencil_value, real_pencil_value > pair_values(real_qz_form &f, std::size_t ilast, const pencil_pair &pair, double b11, double b22)
The conjugate pair of the standardized 2 × 2 block ending at ilast of f (T diagonal,...
void refuse_boundary(bool continuous)
Refuses a Riccati equation whose pencil has eigenvalues on (or too close to) the boundary.
bool entries_finite(std::initializer_list< const matrix< std::complex< double > > * > xs)
Whether every entry of the matrices xs is finite.
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.
double hypot3(double x, double y, double z)
√(x² + y² + z²) without overflow, LAPACK's dlapy3.
matrix< T > riccati(const riccati_operands< T > &terms, bool continuous, bool balanced)
The stabilising solution of the continuous (continuous) or discrete algebraic Riccati equation by Sci...
std::vector< real_pencil_value > real_qz_iteration(real_qz_form &f, std::size_t steps)
The Hessenberg-triangular f to generalized real Schur form, as LAPACK's dhgeqz (Schur form,...
triangle_svd svd_of_triangle(double f, double g, double h)
The SVD of the upper triangular [f g; 0 h], as LAPACK's dlasv2: [csl snl; −snl csl] [f g; 0 h] [csr −...
matrix< T > stabilising_solution(const matrix< T > &top, const matrix< T > &bottom, bool continuous)
X = U₂₁ U₁₁⁻¹ from the m leading Schur vectors' halves top (U₁₁) and bottom (U₂₁) of a Riccati equati...
double small_norm(const small_square &x, std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1)
The Frobenius norm of rows r0 … r1 − 1 and columns c0 … c1 − 1 of x.
matrix< T > adjoint_of(const matrix< T > &m)
Mᴴ: the transpose, conjugated.
matrix< T > hamiltonian_riccati(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *s, bool balanced)
The stabilising solution of the continuous equation without E from the Schur form of the Hamiltonian ...
matrix< T > solve_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const matrix< T > *e, const matrix< T > *s, bool balanced, bool continuous)
The checks of SciPy's _are_validate_args, then riccati on complex operands, the answer real for real ...
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 ...
matrix< std::complex< double > > generalized_eigenvectors(const generalized_schur &d, bool left)
The right (or, where left, the left) eigenvectors of the pencil d decomposes, as LAPACK's ztgevc and ...
T dot(const vector< T > &a, const vector< T > &b)
Dot product.
vector< T > solve(matrix< T > a, const vector< T > &b)
Solves the linear system A x = b for a square A.
tensor< T > diag(const tensor< T > &v, std::ptrdiff_t k)
The square matrix with the vector v on its k diagonal (above the main one for a positive k) and zeros...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
T max(const tensor< T > &t)
The largest element (a NaN, if there is one), of a transpose's elements as they lie (in any order the...
@ complete
Q is m × m, its columns past k a basis of the complement of A's column space; R is m × n.
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 > solve_continuous_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
The stabilising solution X of the continuous algebraic Riccati equation Aᴴ X E + Eᴴ X A − (Eᴴ X B + S...
vector< double > singular_values(const matrix< T > &a)
The singular values of a, descending, without its singular vectors, as numpy.linalg....
matrix< T > solve_sylvester(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q)
The solution X (m × n) of the Sylvester equation A X + X B = Q, as scipy.linalg.solve_sylvester: by B...
matrix< T > solve_discrete_are(const matrix< T > &a, const matrix< T > &b, const matrix< T > &q, const matrix< T > &r, const std::type_identity_t< matrix< T > > *e=nullptr, const std::type_identity_t< matrix< T > > *s=nullptr, bool balanced=true)
The stabilising solution X of the discrete algebraic Riccati equation Aᴴ X A − Eᴴ X E − (Aᴴ X B + S) ...
An exchange of two diagonal blocks as exchange_real_blocks plans it: the blocks after it,...
small_square li
The rows' transform: ‘S’ = LIᵀ S IR,Q ← Q LI`.
small_square ir
The columns': Z ← Z IR.
small_square s
The m × m block of S after the exchange.
The bounds of dlag2's WSIZE (pencil_wsize), fixed by the pencil's scales.
double c5
The eigenvalue's least size counted.
double c2
safmin · max(1, bnorm).
double floor
The divisor's least value.
double c4
The divisor's cap before the eigenvalue's own size.
The eigenvalues of a 2 × 2 pencil, scaled (pencil_eigenvalues): wr1 / scale1 and wr2 / scale2,...
double scale2
The second's.
double scale1
The first's scale.
double wr1
The first's scaled real part.
double wi
The pair's scaled imaginary part, non-negative; 0 for real ones.
The rotations dlagv2 applies to a 2 × 2 pencil: [csl snl; −snl csl] (A, B) [csr −snr; snr csr].
double csl
The left cosine.
double csr
The right cosine.
double snr
The right sine.
A plane rotation [c s; −s̄ c] and what it leaves of its first argument.
A generalized eigenvalue (αr + i αi) / β of a real pencil, as LAPACK's dgges gives it.
double alphai
Its imaginary part: of opposite signs within a conjugate pair, the first positive.
double beta
β ≥ 0, 0 for an infinite eigenvalue.
double alphar
The real part of α.
The operands of an algebraic Riccati equation in the arithmetic of T, e and s absent when null.
A square of order 4 at most, row-major in a fixed stride: the blocks dtgex2 exchanges and its transfo...
double & operator()(std::size_t i, std::size_t j)
The entry (i, j), from 0.
double operator()(std::size_t i, std::size_t j) const
The entry (i, j), from 0.
static small_square identity(std::size_t m)
The identity of order m.
std::array< double, 16 > e
The entries, (i, j) at 4 i + j.
The singular value decomposition of the upper triangular [f g; 0 h] (svd_of_triangle).
double ssmin
The smaller singular value, signed.
double ssmax
The larger, signed.
double snr
The right rotation's sine.
double snl
The left rotation's sine.
The singular value decomposition and what it answers: the singular values, least squares,...