7#ifndef NUMERICAL_MATRIX_FUNCTIONS_HPP
8#define NUMERICAL_MATRIX_FUNCTIONS_HPP
38 std::transform(a.begin(), a.end(),
moduli.begin(), [](
double x) { return std::abs(x); });
50 for (
const std::complex<double>& z : a) {
51 largest = std::max({largest, std::abs(z.real()), std::abs(z.imag())});
54 if (largest >= std::ldexp(1.0, -500) && largest <= std::ldexp(1.0, 500)) {
55 std::transform(a.begin(), a.end(),
moduli.begin(), [](
const std::complex<double>& z) {
56 const double square {z.real() * z.real()};
57 return std::sqrt(
square + (z.imag() * z.imag()));
61 std::transform(a.begin(), a.end(),
moduli.begin(), [](
const std::complex<double>& z) { return std::abs(z); });
72 for (std::size_t i {0}; i < n; ++i) {
73 for (std::size_t j {0}; j < n; ++j) {
77 return *std::max_element(
sums.begin(),
sums.end());
98 std::fill(next.begin(), next.end(), 0.0);
99 for (std::size_t i {0}; i < n; ++i) {
100 for (std::size_t j {0}; j < n; ++j) {
101 next[j] +=
row[i] *
moduli[(i * n) + j] * scale;
104 std::swap(
row, next);
106 return *std::max_element(
row.begin(),
row.end());
112 template <
typename T>
119 gemm(n, n, n, a.data(), n, b.data(), n, c.data(), n, c_start::zero);
123 template <
typename T>
135 template <
typename T>
147 static constexpr std::array<double, 4>
three {120.0, 60.0, 12.0, 1.0};
148 static constexpr std::array<double, 6>
five {30240.0, 15120.0, 3360.0, 420.0, 30.0, 1.0};
149 static constexpr std::array<double, 8>
seven {17297280.0, 8648640.0, 1995840.0, 277200.0, 25200.0, 1512.0, 56.0, 1.0};
150 static constexpr std::array<double, 10>
nine {17643225600.0, 8821612800.0, 2075673600.0, 302702400.0, 30270240.0,
151 2162160.0, 110880.0, 3960.0, 90.0, 1.0};
152 static constexpr std::array<double, 14>
thirteen {64764752532480000.0, 32382376266240000.0, 7771770303897600.0, 1187353796428800.0,
153 129060195264000.0, 10559470521600.0, 670442572800.0, 33522128640.0,
154 1323241920.0, 40840800.0, 960960.0, 16380.0,
157 case 3:
return three.data();
158 case 5:
return five.data();
159 case 7:
return seven.data();
160 case 9:
return nine.data();
177 const auto order {
static_cast<double>(m)};
178 const double c {std::exp((2.0 * std::lgamma(order + 1.0)) - std::lgamma((2.0 * order) + 1.0) - std::lgamma((2.0 * order) + 2.0))};
184 const double unit {std::ldexp(1.0, -53)};
188 return static_cast<std::size_t
>(std::ceil(std::log2(
alpha /
unit) /
static_cast<double>(2 * m)));
196 template <
typename T>
207 for (std::size_t e {0}; e < n * n; ++e) {
235 odd.assign(n * n,
T {});
236 even.assign(n * n,
T {});
237 for (std::size_t k {2}; k < m; k += 2) {
242 for (std::size_t i {0}; i < n; ++i) {
243 odd[(i * n) + i] +=
T {b[1]};
244 even[(i * n) + i] +=
T {b[0]};
249 for (std::size_t e {0}; e < n * n; ++e) {
255 return lu.solve(
matrix<T> {n, n, std::move(u)}).elements();
259 template <
typename T>
262 if (std::abs(x) < 1e-4) {
266 return std::sinh(x) / x;
281 template <
typename T>
287 for (std::size_t i {0}; i < n; ++i) {
288 const T lambda {
T {scale} *t[(i * n) + i]};
289 x[(i * n) + i] = std::exp(
lambda);
291 const T next {
T {scale} *t[((i + 1) * n) + i + 1]};
298 const double length {
static_cast<double>(std::abs(
gap))};
299 const T log_of {std::log(length)};
302 x[(i * n) + i + 1] =
T {scale} *t[(i * n) + i + 1] *
quotient;
313 template <
typename T>
316 const std::size_t n {a.
rows()};
317 for (std::size_t i {0}; i < n; ++i) {
318 if (a(i, i) !=
conj_of(a(i, i))) {
321 for (std::size_t j {0}; j < i; ++j) {
322 if (a(i, j) !=
conj_of(a(j, i))) {
335 return {std::move(values), std::move(e).vectors()};
343 return {std::move(values), std::move(e).vectors()};
350 template <
typename R,
typename T>
352 const std::vector<R>& f,
355 const std::size_t n {v.
rows()};
358 for (std::size_t i {0}; i < n; ++i) {
359 for (std::size_t k {0}; k < n; ++k) {
360 scaled[(i * n) + k] = R {v(i, k)} *f[k];
369 for (std::size_t i {0}; i < n; ++i) {
370 for (std::size_t k {0}; k < n; ++k) {
371 out[(i * n) + k] = (x(i, k) +
conj_of(x(k, i))) / 2.0;
393 template <
typename T>
394 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
397 const std::size_t n {a.
rows()};
401 detail::require_finite(a,
"expm");
406 const auto [values, vectors] {detail::hermitian_system(a)};
407 std::vector<T> powers(n);
408 for (std::size_t k {0}; k < n; ++k) {
409 powers[k] = T {std::exp(values[k])};
411 return detail::spectral<T>(vectors, powers,
true);
414 bool triangular {
true};
415 for (std::size_t i {1}; i < n && triangular; ++i) {
416 for (std::size_t j {0}; j < i; ++j) {
417 triangular = triangular && a0[(i * n) + j] == T {};
421 const double norm {detail::column_sum_norm(moduli, n)};
422 buffer<T> a2 {detail::square_product(a0, a0, n)};
423 buffer<T> a4 {detail::square_product(a2, a2, n)};
424 buffer<T> a6 {detail::square_product(a4, a2, n)};
425 const double d4 {std::pow(detail::one_norm(a4, n), 1.0 / 4.0)};
426 const double d6 {std::pow(detail::one_norm(a6, n), 1.0 / 6.0)};
427 const double eta1 {std::max(d4, d6)};
428 constexpr std::array<double, 5> theta {1.495585217958292e-2, 2.539398330063230e-1, 9.504178996162932e-1, 2.097847961257068e0,
429 5.371920351148152e0};
431 std::array<const buffer<T>*, 4> powers {&a2, &a4, &a6,
nullptr};
432 if (eta1 <= theta[0] && detail::extra_squarings(moduli, n, 3, 1.0, norm) == 0) {
433 return finish(detail::pade_approximant(a0, powers, n, 3));
435 if (eta1 <= theta[1] && detail::extra_squarings(moduli, n, 5, 1.0, norm) == 0) {
436 return finish(detail::pade_approximant(a0, powers, n, 5));
438 buffer<T> a8 {detail::square_product(a4, a4, n)};
440 const double d8 {std::pow(detail::one_norm(a8, n), 1.0 / 8.0)};
441 const double eta3 {std::max(d6, d8)};
442 if (eta3 <= theta[2] && detail::extra_squarings(moduli, n, 7, 1.0, norm) == 0) {
443 return finish(detail::pade_approximant(a0, powers, n, 7));
445 if (eta3 <= theta[3] && detail::extra_squarings(moduli, n, 9, 1.0, norm) == 0) {
446 return finish(detail::pade_approximant(a0, powers, n, 9));
449 const auto d10 = [&] {
return std::pow(detail::one_norm(detail::square_product(a4, a6, n), n), 1.0 / 10.0); };
450 const double eta5 {eta3 <= theta[4] || d8 >= eta3 ? eta3 : std::min(eta3, std::max(d8, d10()))};
451 std::size_t s {eta5 <= theta[4] ? 0 : static_cast<std::size_t>(std::ceil(std::log2(eta5 / theta[4])))};
452 s += detail::extra_squarings(moduli, n, 13, std::ldexp(1.0, -
static_cast<int>(s)), norm);
456 const int power {
static_cast<int>(s)};
459 for (std::size_t e {0}; e < n * n; ++e) {
460 scaled[e] *= T {std::ldexp(1.0, -power)};
461 a2[e] *= T {std::ldexp(1.0, -2 * power)};
462 a4[e] *= T {std::ldexp(1.0, -4 * power)};
463 a6[e] *= T {std::ldexp(1.0, -6 * power)};
465 buffer<T> x {detail::pade_approximant(scaled, powers, n, 13)};
467 detail::exact_triangular_bands(x, bands, n, std::ldexp(1.0, -power));
470 for (
int j {power - 1}; j >= 0; --j) {
471 detail::square_in_place(x, spare, n);
473 detail::exact_triangular_bands(x, bands, n, std::ldexp(1.0, -j));
476 return finish(std::move(x));
491 inline constexpr std::array<taylor_bound, 35>
taylor_bounds {{{1, 2.29e-16},
543 const std::function<
double(std::size_t)>& power_norm)
545 constexpr std::size_t most_terms {55};
546 constexpr std::size_t most_power {8};
547 constexpr double ell {2.0};
549 const auto consider = [&best](std::size_t m,
double ratio) {
550 const auto s {
static_cast<std::size_t
>(std::ceil(ratio))};
551 if (best.terms == 0 || m * s < best.terms * best.steps) {
555 const double condition {2.0 * ell *
static_cast<double>(most_power * (most_power + 3)) *
taylor_bounds.back().theta
556 /
static_cast<double>(columns * most_terms)};
557 if (norm <= condition) {
559 consider(bound.m, norm / bound.theta);
563 std::vector<double> d(most_power + 2, 0.0);
564 const auto alpha = [&](std::size_t p) {
565 for (
const std::size_t q : {p, p + 1}) {
567 d[q] = power_norm(q);
570 return std::max(d[p], d[p + 1]);
572 for (std::size_t p {2}; p <= most_power; ++p) {
574 if (bound.m + 1 >= p * (p - 1)) {
575 consider(bound.m, alpha(p) / bound.theta);
579 best.steps = std::max<std::size_t>(best.steps, 1);
584 template <
typename T>
589 double largest {0.0};
590 for (std::size_t i {0}; i < n; ++i) {
592 for (std::size_t j {0}; j < k; ++j) {
593 sum += std::abs(x[(i * k) + j]);
595 largest = std::max(largest,
sum);
616 template <
typename T>
617 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
622 const std::size_t n {a.
rows()};
623 if (a.
cols() != n || b.
rows() != n) {
624 throw dimension_error(
"expm_multiply: a square matrix and a block of its rows");
626 detail::require_finite(a,
"expm_multiply");
627 detail::require_finite(b,
"expm_multiply");
628 if (!std::isfinite(t)) {
631 const std::size_t k {b.
cols()};
634 for (std::size_t i {0}; i < n; ++i) {
635 trace += shifted[(i * n) + i];
637 const T mu {n == 0 ? T {} : trace / T {
static_cast<double>(n)}};
638 for (std::size_t i {0}; i < n; ++i) {
639 shifted[(i * n) + i] -= mu;
641 const double norm {n == 0 ? 0.0 : std::abs(t) * detail::one_norm(shifted, n)};
643 if (norm != 0.0 && k != 0) {
645 for (std::size_t i {0}; i < n; ++i) {
646 for (std::size_t j {0}; j < n; ++j) {
647 adjoint[(j * n) + i] = detail::conj_of(shifted[(i * n) + j]);
650 const double scale {std::abs(t)};
651 plan = detail::plan_taylor(norm, k, [&](std::size_t p) {
653 const double estimate {detail::one_norm_estimate<T>(n, [&](T* x,
bool conjugate_transposed) {
654 for (std::size_t r {0}; r < p; ++r) {
655 detail::matrix_times_vector((conjugate_transposed ? adjoint : shifted).data(), n, n, n, x, product.data());
656 std::copy(product.begin(), product.end(), x);
659 return scale * std::pow(estimate, 1.0 /
static_cast<double>(p));
662 constexpr double tol {0x1.0p-53};
666 const T eta {std::exp(T {t} *mu / T {
static_cast<double>(plan.steps)})};
667 for (std::size_t step {0}; step < plan.steps; ++step) {
668 double c1 {detail::row_sum_norm(term, n, k)};
669 for (std::size_t j {0}; j < plan.terms; ++j) {
671 detail::matrix_times_vector(shifted.data(), n, n, n, term.data(), next.data());
674 gemm(n, k, n, shifted.data(), n, term.data(), k, next.data(), k, detail::c_start::zero);
676 const T coefficient {t /
static_cast<double>(plan.steps * (j + 1))};
677 for (std::size_t e {0}; e < n * k; ++e) {
678 term[e] = coefficient * next[e];
681 const double c2 {detail::row_sum_norm(term, n, k)};
682 if (c1 + c2 <= tol * detail::row_sum_norm(f, n, k)) {
698 template <
typename T>
702 for (std::size_t i {0}; i < m.
rows(); ++i) {
703 for (std::size_t j {0}; j < m.
cols(); ++j) {
716 return k + 1 < n && t[((k + 1) * n) + k] != 0.0 ? 2 : 1;
733 template <
typename T>
744 const std::size_t size {rows * cols};
745 std::array<std::array<T, 4>, 4> k {};
746 std::array<T, 4> rhs {};
747 std::array<std::size_t, 4> order {0, 1, 2, 3};
748 for (std::size_t i {0}; i < rows; ++i) {
749 for (std::size_t j {0}; j < cols; ++j) {
750 const std::size_t e {(i * cols) + j};
751 rhs[e] = c[(i * ldc) + j];
752 for (std::size_t p {0}; p < rows; ++p) {
753 k[e][(p * cols) + j] += r[(i * ldr) + p];
755 for (std::size_t q {0}; q < cols; ++q) {
756 k[e][(i * cols) + q] += s[(q * lds) + j];
760 for (std::size_t step {0}; step < size; ++step) {
761 std::size_t pivot_row {step};
762 std::size_t pivot_col {step};
763 double largest {-1.0};
764 for (std::size_t i {step}; i < size; ++i) {
765 for (std::size_t j {step}; j < size; ++j) {
766 if (std::abs(k[i][j]) > largest) {
767 largest = std::abs(k[i][j]);
773 std::swap(k[step], k[pivot_row]);
774 std::swap(rhs[step], rhs[pivot_row]);
775 for (std::size_t i {0}; i < size; ++i) {
776 std::swap(k[i][step], k[i][pivot_col]);
778 std::swap(order[step], order[pivot_col]);
779 if (std::abs(k[step][step]) < smin) {
780 k[step][step] = T {smin};
782 for (std::size_t i {step + 1}; i < size; ++i) {
783 const T factor {k[i][step] / k[step][step]};
784 for (std::size_t j {step}; j < size; ++j) {
785 k[i][j] -= factor * k[step][j];
787 rhs[i] -= factor * rhs[step];
790 std::array<T, 4> y {};
791 for (std::size_t back {size}; back > 0; --back) {
792 const std::size_t i {back - 1};
794 for (std::size_t j {i + 1}; j < size; ++j) {
795 value -= k[i][j] * y[j];
797 y[i] = value / k[i][i];
799 for (std::size_t e {0}; e < size; ++e) {
800 const std::size_t unknown {order[e]};
801 c[((unknown / cols) * ldc) + (unknown % cols)] = y[e];
812 template <
typename T>
819 double largest {0.0};
820 for (
const T& entry : r) {
821 largest = std::max(largest, std::abs(entry));
823 for (
const T& entry : s) {
824 largest = std::max(largest, std::abs(entry));
826 const double smin {std::max(std::numeric_limits<double>::epsilon() * largest, std::numeric_limits<double>::min())};
829 for (std::size_t l {0}; l < n;) {
832 minus_s.resize(l * nl);
833 for (std::size_t q {0}; q < l; ++q) {
834 for (std::size_t j {0}; j < nl; ++j) {
835 minus_s[(q * nl) + j] = -s[(q * n) + l + j];
838 gemm(m, nl, l, f.data(), n, minus_s.data(), nl, f.data() + l, n);
840 columns.resize(nl * m);
841 for (std::size_t end {m}; end > 0;) {
842 const std::size_t kb {end >= 2 &&
schur_block(r, m, end - 2) == 2 ? std::size_t {2} : std::size_t {1}};
843 const std::size_t k0 {end - kb};
844 for (std::size_t i {k0}; i < end; ++i) {
845 for (std::size_t j {0}; j < nl; ++j) {
846 f[(i * n) + l + j] -=
dot_product(r.data() + (i * m) + end, columns.data() + (j * m) + end, m - end);
849 small_sylvester_block(r.data() + (k0 * m) + k0, m, s.data() + (l * n) + l, n, kb, nl, f.data() + (k0 * n) + l, n, smin);
850 for (std::size_t i {k0}; i < end; ++i) {
851 for (std::size_t j {0}; j < nl; ++j) {
852 columns[(j * m) + i] = f[(i * n) + l + j];
874 template <
typename T>
875 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
880 const std::size_t m {a.
rows()};
881 const std::size_t n {b.
rows()};
883 throw dimension_error(
"solve_sylvester requires a square a (m × m), a square b (n × n) and q (m × n)");
885 detail::require_finite(a,
"solve_sylvester");
886 detail::require_finite(b,
"solve_sylvester");
887 detail::require_finite(q,
"solve_sylvester");
888 if (m == 0 || n == 0) {
895 matrix<T> f {detail::adjoint_of(u) * q * v};
897 detail::triangular_sylvester(
buffer<T>(left.t().begin(), left.t().end()), m,
buffer<T>(right.t().begin(), right.t().end()), n, y);
898 return u *
matrix<T> {m, n, std::move(y)} *detail::adjoint_of(v);
913 template <
typename T>
914 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
918 const std::size_t n {a.
rows()};
920 throw dimension_error(
"solve_continuous_lyapunov requires a square a and q of its shape");
922 detail::require_finite(a,
"solve_continuous_lyapunov");
923 detail::require_finite(q,
"solve_continuous_lyapunov");
930 const matrix<T> f {detail::adjoint_of(u) * q * u};
933 for (std::size_t i {0}; i < n; ++i) {
934 for (std::size_t j {0}; j < n; ++j) {
935 y[(i * n) + j] = f(i, n - 1 - j);
936 reversed[(i * n) + j] = detail::conj_of(r(n - 1 - j, n - 1 - i));
939 detail::triangular_sylvester(
buffer<T>(r.begin(), r.end()), n, reversed, n, y);
941 for (std::size_t i {0}; i < n; ++i) {
942 for (std::size_t j {0}; j < n; ++j) {
943 x[(i * n) + j] = y[(i * n) + n - 1 - j];
946 return u *
matrix<T> {n, n, std::move(x)} *detail::adjoint_of(u);
955 static constexpr std::array<double, 21> table {0.0, 2.11e-8, 3.56e-4, 1.08e-2, 6.49e-2, 2.00e-1, 4.37e-1, 7.83e-1, 1.23e0, 1.78e0, 2.42e0,
956 3.13e0, 3.90e0, 4.74e0, 5.63e0, 6.56e0, 7.52e0, 8.53e0, 9.56e0, 1.06e1, 1.17e1};
961 template <
typename T>
966 for (std::size_t e {0}; e < into.size(); ++e) {
967 into[e] += T {coefficient} *term[e];
972 template <
typename T>
979 for (std::size_t e {0}; e <
sum.size(); ++e) {
992 template <
typename T>
1000 for (std::size_t i {0}; i < n; ++i) {
1001 identity[(i * n) + i] = T {1.0};
1037 const auto lower_terms = [&](
const buffer<T>& power,
const buffer<T>& derivative, std::size_t k) {
1043 lower_terms(a6, m6, 6);
1044 lower_terms(a4, m4, 4);
1045 lower_terms(a2, m2, 2);
1050 const std::array<const buffer<T>*, 4> powers {&a2, &a4, &a6, &a8};
1051 const std::array<const buffer<T>*, 4> derivatives {&m2, &m4, &m6, &m8};
1052 for (std::size_t k {m - 1}; k >= 2; k -= 2) {
1053 add_scaled(w, *powers[(k / 2) - 1], b[k + 1]);
1055 add_scaled(lw, *derivatives[(k / 2) - 1], b[k + 1]);
1056 add_scaled(lv, *derivatives[(k / 2) - 1], b[k]);
1066 for (std::size_t k {0}; k < n * n; ++k) {
1067 numerator[k] = u[k] + v[k];
1068 denominator[k] = v[k] - u[k];
1073 for (std::size_t k {0}; k < n * n; ++k) {
1074 difference[k] = lu[k] - lv[k];
1077 for (std::size_t k {0}; k < n * n; ++k) {
1078 derivative_terms[k] = lu[k] + lv[k] + derivative_terms[k];
1080 buffer<T> l {factor.solve(
matrix<T> {n, n, std::move(derivative_terms)}).elements()};
1081 return {std::move(r), std::move(l)};
1104 template <
typename T>
1105 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
1110 const std::size_t n {a.
rows()};
1112 throw dimension_error(
"expm_frechet requires square matrices a and e of one order");
1114 detail::require_finite(a,
"expm_frechet");
1115 detail::require_finite(e,
"expm_frechet");
1119 if (method == frechet_method::block_enlarge) {
1121 for (std::size_t i {0}; i < n; ++i) {
1122 for (std::size_t j {0}; j < n; ++j) {
1123 block[(i * 2 * n) + j] = a(i, j);
1124 block[(i * 2 * n) + n + j] = e(i, j);
1125 block[((n + i) * 2 * n) + n + j] = a(i, j);
1131 for (std::size_t i {0}; i < n; ++i) {
1132 for (std::size_t j {0}; j < n; ++j) {
1133 top[(i * n) + j] = x(i, j);
1134 right[(i * n) + j] = x(i, n + j);
1141 const double norm {detail::one_norm(a0, n)};
1142 for (
const std::size_t m : {std::size_t {3}, std::size_t {5}, std::size_t {7}, std::size_t {9}}) {
1143 if (norm <= detail::frechet_bound(m)) {
1144 auto [r, l] {detail::frechet_pade(a0, e0, n, m)};
1148 const int s {std::max(0,
static_cast<int>(std::ceil(std::log2(norm / detail::frechet_bound(13)))))};
1149 for (std::size_t k {0}; k < n * n; ++k) {
1150 a0[k] *= T {std::ldexp(1.0, -s)};
1151 e0[k] *= T {std::ldexp(1.0, -s)};
1153 auto [r, l] {detail::frechet_pade(a0, e0, n, 13)};
1155 for (
int k {0}; k < s; ++k) {
1156 l = detail::both_products(r, l, n);
1157 detail::square_in_place(r, spare, n);
1170 template <
typename T>
1171 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
1174 const std::size_t n {a.
rows()};
1175 if (a.
cols() != n) {
1178 detail::require_finite(a,
"expm_cond");
1182 const std::size_t columns {n * n};
1184 for (std::size_t i {0}; i < n; ++i) {
1185 for (std::size_t j {0}; j < n; ++j) {
1187 unit[(i * n) + j] = T {1.0};
1189 for (std::size_t q {0}; q < n; ++q) {
1190 for (std::size_t p {0}; p < n; ++p) {
1191 k[(((q * n) + p) * columns) + (i * n) + j] = l(p, q);
1196 const auto frobenius = [](
const matrix<T>& m) {
1198 for (
const T& x : m) {
1199 sum += std::norm(x);
1201 return std::sqrt(
sum);
1204 return kronecker * frobenius(a) / frobenius(
expm(a));
1217 template <
typename T>
1221 const std::vector<std::size_t>& starts)
1223 const std::size_t blocks {starts.size()};
1225 for (std::size_t bj {0}; bj < blocks; ++bj) {
1226 const std::size_t j0 {starts[bj]};
1227 const std::size_t nj {(bj + 1 < blocks ? starts[bj + 1] : n) - j0};
1228 for (std::size_t above {0}; above < bj; ++above) {
1229 const std::size_t bi {bj - above};
1230 const std::size_t i0 {starts[bi - 1]};
1231 const std::size_t ni {starts[bi] - i0};
1232 std::array<T, 4> c {};
1233 for (std::size_t i {0}; i < ni; ++i) {
1234 for (std::size_t j {0}; j < nj; ++j) {
1235 T value {t[((i0 + i) * n) + j0 + j]};
1236 const T*
const row {r.data() + ((i0 + i) * n)};
1237 const T*
const column {columns.data() + (j * n)};
1238 for (std::size_t k {starts[bi]}; k < j0; ++k) {
1239 value -= row[k] * column[k];
1241 c[(i * nj) + j] = value;
1244 if (ni == 1 && nj == 1) {
1245 const T
sum {r[(i0 * n) + i0] + r[(j0 * n) + j0]};
1246 c[0] =
sum == T {} && c[0] == T {} ? T {} : c[0] /
sum;
1249 small_sylvester_block(r.data() + (i0 * n) + i0, n, r.data() + (j0 * n) + j0, n, ni, nj, c.data(), nj, 0.0);
1251 for (std::size_t i {0}; i < ni; ++i) {
1252 for (std::size_t j {0}; j < nj; ++j) {
1253 r[((i0 + i) * n) + j0 + j] = c[(i * nj) + j];
1254 columns[(j * n) + i0 + i] = c[(i * nj) + j];
1269 const std::size_t n {form.
rows()};
1272 std::vector<std::size_t> starts;
1273 for (std::size_t k {0}; k < n; k +=
schur_block(t, n, k)) {
1274 starts.push_back(k);
1276 if (t[(k * n) + k] < 0.0) {
1277 return std::nullopt;
1279 r[(k * n) + k] = std::sqrt(t[(k * n) + k]);
1282 const double theta {t[(k * n) + k]};
1283 const double mu {std::sqrt(std::abs(t[(k * n) + k + 1])) * std::sqrt(std::abs(t[((k + 1) * n) + k]))};
1284 const double alpha {
complex_sqrt(std::complex<double> {theta, mu}).real()};
1285 r[(k * n) + k] = alpha;
1286 r[((k + 1) * n) + k + 1] = alpha;
1287 r[(k * n) + k + 1] = t[(k * n) + k + 1] / (2.0 * alpha);
1288 r[((k + 1) * n) + k] = t[((k + 1) * n) + k] / (2.0 * alpha);
1298 return std::sqrt(x);
1302 [[nodiscard]]
inline std::complex<double>
scalar_sqrt(
const std::complex<double>& z)
1309 template <
typename T>
1314 std::vector<std::size_t> starts(n);
1315 for (std::size_t k {0}; k < n; ++k) {
1334 template <
typename T>
1338 bool singular {
false};
1339 for (std::size_t k {0}; k < n; ++k) {
1340 singular = singular || t[(k * n) + k] == T {};
1346 const auto start = [n, blocks](std::size_t b) {
return b == blocks ? n : b *
square_root_block; };
1347 std::vector<buffer<T>> roots(blocks);
1349 for (std::size_t b {0}; b < blocks; ++b) {
1350 const std::size_t b0 {start(b)};
1351 const std::size_t nb {start(b + 1) - b0};
1353 for (std::size_t i {0}; i < nb; ++i) {
1354 std::copy_n(t.data() + ((b0 + i) * n) + b0, nb, block.data() + (i * nb));
1357 for (std::size_t i {0}; i < nb; ++i) {
1358 std::copy_n(roots[b].data() + (i * nb), nb, r.data() + ((b0 + i) * n) + b0);
1363 for (std::size_t bj {1}; bj < blocks; ++bj) {
1364 const std::size_t j0 {start(bj)};
1365 const std::size_t nj {start(bj + 1) - j0};
1366 for (std::size_t bi {bj}; bi > 0; --bi) {
1367 const std::size_t i0 {start(bi - 1)};
1368 const std::size_t ni {start(bi) - i0};
1370 product.resize(ni * nj);
1371 gemm(ni, nj, j0 - start(bi), r.data() + (i0 * n) + start(bi), n, r.data() + (start(bi) * n) + j0, n, product.data(), nj, c_start::zero);
1372 for (std::size_t i {0}; i < ni; ++i) {
1373 for (std::size_t j {0}; j < nj; ++j) {
1374 f[(i * nj) + j] = t[((i0 + i) * n) + j0 + j] - product[(i * nj) + j];
1378 for (std::size_t i {0}; i < ni; ++i) {
1379 std::copy_n(f.data() + (i * nj), nj, r.data() + ((i0 + i) * n) + j0);
1388 const matrix<std::complex<double>>* z)
1390 const std::size_t n {form.
rows()};
1404 using C = std::complex<double>;
1405 const std::size_t n {t.
rows()};
1408 for (std::size_t e {0}; e < n * n; ++e) {
1409 tc[e] = C {t.
begin()[
static_cast<std::ptrdiff_t
>(e)]};
1410 zc[e] = C {z.
begin()[
static_cast<std::ptrdiff_t
>(e)]};
1412 for (std::size_t k {n}; k > 1; --k) {
1413 const std::size_t m {k - 1};
1414 const C below {tc[(m * n) + m - 1]};
1415 if (below == C {}) {
1420 const double largest {std::max({std::abs(tc[((m - 1) * n) + m - 1]), std::abs(tc[((m - 1) * n) + m]), std::abs(tc[(m * n) + m]),
1422 const double scale {std::ldexp(1.0, -std::ilogb(largest))};
1423 const C a {tc[((m - 1) * n) + m - 1] * scale};
1424 const C b {tc[((m - 1) * n) + m] * scale};
1425 const C d {tc[(m * n) + m] * scale};
1426 const C c_s {below * scale};
1428 const C half {(a - d) / 2.0};
1429 const C mu {half +
complex_sqrt((half * half) + (b * c_s))};
1430 const double r {std::hypot(std::abs(mu), std::abs(c_s))};
1432 const C sn {c_s / r};
1433 for (std::size_t j {m - 1}; j < n; ++j) {
1434 const C upper {tc[((m - 1) * n) + j]};
1435 const C lower {tc[(m * n) + j]};
1436 tc[((m - 1) * n) + j] = (std::conj(c) * upper) + (sn * lower);
1437 tc[(m * n) + j] = (-sn * upper) + (c * lower);
1439 for (std::size_t i {0}; i <= m; ++i) {
1440 const C left {tc[(i * n) + m - 1]};
1441 const C right {tc[(i * n) + m]};
1442 tc[(i * n) + m - 1] = (c * left) + (std::conj(sn) * right);
1443 tc[(i * n) + m] = (-sn * left) + (std::conj(c) * right);
1445 for (std::size_t i {0}; i < n; ++i) {
1446 const C left {zc[(i * n) + m - 1]};
1447 const C right {zc[(i * n) + m]};
1448 zc[(i * n) + m - 1] = (c * left) + (std::conj(sn) * right);
1449 zc[(i * n) + m] = (-sn * left) + (std::conj(c) * right);
1451 tc[(m * n) + m - 1] = C {};
1458 template <
typename T>
1461 for (std::size_t i {1}; i < a.
rows(); ++i) {
1462 for (std::size_t j {0}; j < i; ++j) {
1463 if (a(i, j) != T {}) {
1475 template <
typename T>
1479 std::vector<std::complex<double>> roots(values.size());
1480 for (std::size_t k {0}; k < roots.size(); ++k) {
1481 roots[k] =
complex_sqrt(std::complex<double> {values[k]});
1483 return spectral<std::complex<double>>(vectors, roots, std::all_of(values.begin(), values.end(), [](
double v) { return v >= 0.0; }));
1509 if (a.rows() != a.cols()) {
1512 detail::require_finite(a,
"sqrtm");
1513 if (detail::exactly_hermitian(a)) {
1514 return detail::hermitian_root(a);
1516 if (detail::upper_triangular(a)) {
1517 return detail::complex_square_root(a,
nullptr);
1520 return detail::complex_square_root(s.t(), &s.z());
1536 detail::require_finite(a,
"sqrtm");
1537 if (detail::exactly_hermitian(a)) {
1538 return detail::hermitian_root(a);
1540 if (detail::upper_triangular(a)) {
1542 return detail::complex_square_root(form,
nullptr);
1545 const auto [t, z] {detail::complex_schur_form(s.t(), s.z())};
1546 return detail::complex_square_root(t, &z);
1563 detail::require_finite(a,
"sqrtm");
1564 std::optional<matrix<double>> root;
1565 if (detail::exactly_hermitian(a)) {
1566 const auto [values, vectors] {detail::hermitian_system(a)};
1567 if (!std::all_of(values.begin(), values.end(), [](
double v) { return v >= 0.0; })) {
1568 throw no_real_root_error(
"sqrtm: a real eigenvalue below 0, whose principal square root is complex");
1570 std::vector<double> roots(values.size());
1571 for (std::size_t k {0}; k < roots.size(); ++k) {
1572 roots[k] = std::sqrt(values[k]);
1574 return detail::spectral<double>(vectors, roots,
true);
1576 if (detail::upper_triangular(a)) {
1577 root = detail::real_square_root(a,
nullptr);
1581 root = detail::real_square_root(s.t(), &s.z());
1584 throw no_real_root_error(
"sqrtm: a real eigenvalue below 0, whose principal square root is complex");
1586 return std::move(*root);
1596 const std::uint64_t fraction {(
static_cast<std::uint64_t
>(place) + 1) * std::uint64_t {0x9E3779B97F4A7C15}};
1597 return std::polar(1.0, 2.0 * std::numbers::pi * std::ldexp(
static_cast<double>(fraction >> 11), -53));
1605 const std::vector<std::size_t>& starts,
1606 buffer<std::complex<double>>& x,
1607 const std::complex<double>* sources)
1609 using C = std::complex<double>;
1610 const std::size_t n {t.rows()};
1611 const std::size_t count {starts.size() - 1};
1615 for (std::size_t i {0}; i < n; ++i) {
1616 for (std::size_t j {0}; j < n; ++j) {
1617 form[(i * n) + j] = t(i, j);
1618 columns[(j * n) + i] = t(i, j);
1619 x_columns[(j * n) + i] = x[(i * n) + j];
1626 for (std::size_t d {1}; d < count; ++d) {
1627 for (std::size_t bi {0}; bi + d < count; ++bi) {
1628 const std::size_t bj {bi + d};
1629 const std::size_t i0 {starts[bi]};
1630 const std::size_t pi {starts[bi + 1] - i0};
1631 const std::size_t j0 {starts[bj]};
1632 const std::size_t pj {starts[bj + 1] - j0};
1633 const std::size_t depth {j0 + pj - i0};
1634 rhs.resize(pi * pj);
1635 product.resize(pi * pj);
1637 gemm(pi, pj, depth, x.data() + (i0 * n) + i0, n, form.data() + (i0 * n) + j0, n, rhs.data(), pj, c_start::zero);
1638 gemm(pi, pj, depth, form.data() + (i0 * n) + i0, n, x.data() + (i0 * n) + j0, n, product.data(), pj, c_start::zero);
1641 for (std::size_t i {0}; i < pi; ++i) {
1642 for (std::size_t j {0}; j < pj; ++j) {
1645 const C*
const x_row {x.data() + ((i0 + i) * n)};
1646 const C*
const t_row {form.data() + ((i0 + i) * n)};
1647 const C*
const t_column {columns.data() + ((j0 + j) * n)};
1648 const C*
const x_column {x_columns.data() + ((j0 + j) * n)};
1649 for (std::size_t q {i0}; q < j0 + pj; ++q) {
1650 forward += x_row[q] * t_column[q];
1651 backward += t_row[q] * x_column[q];
1658 for (std::size_t i {0}; i < pi; ++i) {
1659 for (std::size_t j {0}; j < pj; ++j) {
1660 const C source {sources ==
nullptr ? C {} : sources[((i0 + i) * n) + j0 + j]};
1661 rhs[(i * pj) + j] = (rhs[(i * pj) + j] - product[(i * pj) + j]) + source;
1664 left.resize(pi * pi);
1665 right.resize(pj * pj);
1666 for (std::size_t i {0}; i < pi; ++i) {
1667 std::copy_n(form.data() + ((i0 + i) * n) + i0, pi, left.data() + (i * pi));
1669 for (std::size_t i {0}; i < pj; ++i) {
1670 for (std::size_t j {0}; j < pj; ++j) {
1671 right[(i * pj) + j] = -form[((j0 + i) * n) + j0 + j];
1675 for (std::size_t i {0}; i < pi; ++i) {
1676 for (std::size_t j {0}; j < pj; ++j) {
1677 x[((i0 + i) * n) + j0 + j] = rhs[(i * pj) + j];
1678 x_columns[((j0 + j) * n) + i0 + i] = rhs[(i * pj) + j];
1699 const std::vector<std::size_t>& starts,
1700 const buffer<std::complex<double>>& fx,
1703 using C = std::complex<double>;
1704 const std::size_t n {t.rows()};
1708 for (std::size_t e {0}; e < n * n; ++e) {
1709 t_moduli[e] = std::abs(t(e / n, e % n).real()) + std::abs(t(e / n, e % n).imag());
1710 f_moduli[e] = std::abs(fx[e].real()) + std::abs(fx[e].imag());
1711 size = std::max(size, std::abs(fx[e]));
1714 gemm(n, n, n, f_moduli.data(), n, t_moduli.data(), n, moduli.data(), n, c_start::zero);
1715 gemm(n, n, n, t_moduli.data(), n, f_moduli.data(), n, moduli.data(), n, c_start::kept);
1717 for (std::size_t b {0}; b + 1 < starts.size(); ++b) {
1718 for (std::size_t i {starts[b]}; i < starts[b + 1]; ++i) {
1719 for (std::size_t j {starts[b + 1]}; j < n; ++j) {
1720 sources[(i * n) + j] = std::numeric_limits<double>::epsilon() * moduli[(i * n) + j] *
rounding_direction((i * n) + j);
1725 double largest {0.0};
1726 for (
const C& entry :
error) {
1727 largest = std::max(largest, std::abs(entry));
1729 return largest / std::max(size, std::numeric_limits<double>::min());
1737 const double tolerance {std::numeric_limits<double>::epsilon()};
1739 for (std::size_t j {1}; j < t.rows(); ++j) {
1740 double column {0.0};
1741 for (std::size_t i {0}; i < j; ++i) {
1742 column += std::abs(t(i, j));
1744 upper = std::max(upper, column);
1746 return std::min(1.0, std::max(tolerance, (tolerance / (smallest == 0.0 ? tolerance : smallest)) * upper));
1774 return {s.
t(), s.z()};
1788 [[nodiscard]]
inline funm_result funm_from_schur(
const matrix<std::complex<double>>& t,
1789 const matrix<std::complex<double>>& z,
1790 const std::vector<std::complex<double>>& values);
1796 const matrix<std::complex<double>>& z,
1797 const std::vector<std::complex<double>>& values)
1799 using C = std::complex<double>;
1800 const std::size_t n {t.rows()};
1801 if (t.cols() != n || z.rows() != n || z.cols() != n || values.size() != n) {
1802 throw dimension_error(
"funm requires a square Schur form T, Z of its order and one value per eigenvalue");
1804 const double tolerance {std::numeric_limits<double>::epsilon()};
1809 for (std::size_t i {0}; i < n; ++i) {
1810 f[(i * n) + i] = values[i];
1814 for (std::size_t i {0}; i < n; ++i) {
1815 for (std::size_t j {0}; j < n; ++j) {
1816 tc[(j * n) + i] = t(i, j);
1818 fc[(i * n) + i] = values[i];
1820 double smallest {std::abs(t(0, 0))};
1821 for (std::size_t p {1}; p < n; ++p) {
1822 for (std::size_t i {0}; i + p < n; ++i) {
1823 const std::size_t j {i + p};
1824 C
sum {t(i, j) * (f[(j * n) + j] - f[(i * n) + i])};
1827 const C*
const t_row {&t(i, 0)};
1828 const C*
const f_row {f.data() + (i * n)};
1829 const C*
const t_col {tc.data() + (j * n)};
1830 const C*
const f_col {fc.data() + (j * n)};
1831 for (std::size_t k {i + 1}; k < j; ++k) {
1832 left += t_row[k] * f_col[k];
1833 right += f_row[k] * t_col[k];
1835 sum += left - right;
1836 const C gap {t(j, j) - t(i, i)};
1840 f[(i * n) + j] =
sum;
1841 fc[(j * n) + i] =
sum;
1842 smallest = std::min(smallest, std::abs(gap));
1846 for (std::size_t i {0}; i < n; ++i) {
1847 rounding[(i * n) + i] = tolerance * values[i] * detail::rounding_direction(i);
1849 std::vector<std::size_t> places(n + 1);
1850 std::iota(places.begin(), places.end(), std::size_t {0});
1851 const double recurrence {detail::recurrence_error(t, places, f, std::move(rounding))};
1853 double error {std::min(1.0, std::max(detail::parlett_estimate(t, smallest), recurrence))};
1854 double own {recurrence};
1855 for (
const C& x : result) {
1856 const bool finite {(x.real() - x.real()) + (x.imag() - x.imag()) == 0.0};
1857 error = finite ?
error : std::numeric_limits<double>::infinity();
1858 own = finite ? own : std::numeric_limits<double>::infinity();
1865 const matrix<std::complex<double>>& z,
1866 const std::vector<std::complex<double>>& values)
1868 return detail::parlett_function(t, z, values).first;
1875 [[nodiscard]]
inline std::vector<std::size_t>
eigenvalue_clusters(
const std::vector<std::complex<double>>& values,
1878 const std::size_t n {values.size()};
1879 std::vector<std::size_t> id(n);
1880 for (std::size_t i {0}; i < n; ++i) {
1883 for (std::size_t i {0}; i < n; ++i) {
1884 for (std::size_t j {i + 1}; j < n; ++j) {
1885 if (std::abs(values[i] - values[j]) <= delta &&
id[j] !=
id[i]) {
1886 const std::size_t from {
id[j]};
1887 const std::size_t to {
id[i]};
1888 for (std::size_t& k : id) {
1889 k = k == from ? to : k;
1894 std::vector<std::size_t> label(n, n);
1895 std::size_t next {0};
1896 for (std::size_t i {0}; i < n; ++i) {
1897 if (label[
id[i]] == n) {
1898 label[
id[i]] = next++;
1900 id[i] = label[
id[i]];
1922 [[nodiscard]]
inline double cluster_bound(
const std::vector<std::complex<double>>& values,
1926 for (
const std::complex<double>& v : values) {
1927 scale = std::max(scale, std::abs(v));
1929 return share * scale;
1943 const std::size_t count {*std::ranges::max_element(cluster) + 1};
1944 std::vector<std::complex<double>> centre(count);
1945 std::vector<std::size_t> members(count, 0);
1946 for (std::size_t i {0}; i < values.size(); ++i) {
1947 centre[cluster[i]] += values[i];
1948 ++members[cluster[i]];
1950 for (std::size_t c {0}; c < count; ++c) {
1951 centre[c] /=
static_cast<double>(members[c]);
1953 std::vector<double> spread(count, 0.0);
1954 std::vector<double> outside(count, std::numeric_limits<double>::infinity());
1955 for (std::size_t c {0}; c < count; ++c) {
1956 for (std::size_t i {0}; members[c] > 1 && i < values.size(); ++i) {
1957 const double distance {std::abs(values[i] - centre[c])};
1958 if (cluster[i] == c) {
1959 spread[c] = std::max(spread[c], distance);
1962 outside[c] = std::min(outside[c], distance);
1966 for (std::size_t c {0}; c < count; ++c) {
1967 if (!(outside[c] > spread[c])) {
1975 [[nodiscard]]
inline std::vector<std::complex<double>>
diagonal_of(
const matrix<std::complex<double>>& t)
1977 std::vector<std::complex<double>> values(t.rows());
1978 for (std::size_t i {0}; i < t.rows(); ++i) {
1979 values[i] = t(i, i);
2013 using C = std::complex<double>;
2014 const std::size_t n {t.rows()};
2019 for (std::size_t i {0}; i < n; ++i) {
2020 if (i == 0 || cluster[i] != cluster[i - 1]) {
2021 circles.
starts.push_back(i);
2024 const std::size_t blocks {circles.
starts.size()};
2025 circles.
starts.push_back(n);
2026 circles.
centres.assign(blocks, C {});
2027 circles.
radii.assign(blocks, 0.0);
2028 for (std::size_t b {0}; b < blocks; ++b) {
2029 const std::size_t first {circles.
starts[b]};
2030 const std::size_t last {circles.
starts[b + 1]};
2031 if (last - first == 1) {
2035 for (std::size_t i {first}; i < last; ++i) {
2036 centre += values[i];
2038 centre /=
static_cast<double>(last - first);
2039 double spread {0.0};
2040 double outside {std::numeric_limits<double>::infinity()};
2041 double coupling {0.0};
2042 for (std::size_t i {0}; i < n; ++i) {
2043 const bool member {i >= first && i < last};
2044 const double distance {std::abs(values[i] - centre)};
2045 spread = member ? std::max(spread, distance) : spread;
2046 outside = member ? outside : std::min(outside, distance);
2047 for (std::size_t j {i + 1}; member && j < last; ++j) {
2048 coupling = std::max(coupling, std::abs(t(i, j)));
2052 circles.
radii[b] = spread + std::min(std::max({spread, delta, coupling}), (outside - spread) / 2.0);
2061 return std::vector<std::size_t>(
static_cast<std::size_t
>(std::ranges::count_if(circles.
radii, [](
double r) { return r > 0.0; })),
contour_points);
2067 const std::vector<std::size_t>& counts)
2069 std::vector<std::complex<double>> points;
2070 std::size_t drawn {0};
2071 for (std::size_t b {0}; b < circles.
radii.size(); ++b) {
2072 if (circles.
radii[b] > 0.0) {
2073 const std::size_t count {counts.at(drawn++)};
2074 for (std::size_t k {0}; k < count; ++k) {
2075 points.push_back(circles.
centres[b] + std::polar(circles.
radii[b], 2.0 * std::numbers::pi *
static_cast<double>(k) /
static_cast<double>(count)));
2088 matrix<std::complex<double>>& z,
2091 using C = std::complex<double>;
2092 const std::size_t n {t.rows()};
2096 if (*std::max_element(first.begin(), first.end()) + 1 == n) {
2101 std::size_t placed {0};
2102 while (placed < n) {
2103 for (std::size_t i {0}; i < n; ++i) {
2104 values[i] = form[(i * n) + i];
2107 std::vector<bool> chosen(n);
2108 for (std::size_t i {0}; i < n; ++i) {
2109 chosen[i] = i < placed || cluster[i] == cluster[placed];
2131 std::complex<double> centre,
2136 const std::complex<double>* images,
2137 buffer<std::complex<double>>& sum,
2140 using C = std::complex<double>;
2144 const std::size_t terms {((count - from) + step - 1) / step};
2145 const std::size_t batch {std::clamp<std::size_t>(
funm_batch_elements / std::max<std::size_t>(1, p * p), 1, std::max<std::size_t>(1, terms))};
2148 for (std::size_t done {0}; done < terms; done += batch) {
2149 const std::size_t now {std::min(batch, terms - done)};
2151 const std::size_t k {from + ((done + b) * step)};
2152 const C point {centre + std::polar(radius, 2.0 * std::numbers::pi *
static_cast<double>(k) /
static_cast<double>(count))};
2153 C*
const a {shifted.data() + (b * p * p)};
2154 C*
const x {inverses.data() + (b * p * p)};
2155 std::fill(x, x + (p * p), C {});
2156 for (std::size_t i {0}; i < p; ++i) {
2157 for (std::size_t j {i}; j < p; ++j) {
2158 a[(i * p) + j] = (i == j ? point : C {}) - t(first + i, first + j);
2160 x[(i * p) + i] = C {1.0};
2164 for (std::size_t b {0}; b < now; ++b) {
2165 const std::size_t k {from + ((done + b) * step)};
2166 const C point {centre + std::polar(radius, 2.0 * std::numbers::pi *
static_cast<double>(k) /
static_cast<double>(count))};
2167 const C weight {*images++ * (point - centre)};
2168 const C*
const x {inverses.data() + (b * p * p)};
2169 for (std::size_t i {0}; i < p; ++i) {
2170 for (std::size_t j {i}; j < p; ++j) {
2171 const C term {weight * x[(i * p) + j]};
2172 sum[(i * p) + j] += term;
2173 moduli[(i * p) + j] += std::abs(term.real()) + std::abs(term.imag());
2182 [[nodiscard]]
inline std::vector<std::complex<double>>
grid_points(std::complex<double> centre,
2188 std::vector<std::complex<double>> points;
2189 for (std::size_t k {from}; k < count; k += step) {
2190 points.push_back(centre + std::polar(radius, 2.0 * std::numbers::pi *
static_cast<double>(k) /
static_cast<double>(count)));
2205 buffer<std::complex<double>>& half,
2209 const std::complex<double>* diagonal)
2213 double rounding {0.0};
2214 for (std::size_t e {0}; e < p * p; ++e) {
2215 whole[e] /=
static_cast<double>(count);
2216 half[e] /=
static_cast<double>(count) / 2.0;
2217 size = std::max(size, std::abs(whole[e]));
2218 gap = std::max(gap, std::abs(whole[e] - half[e]));
2219 rounding = std::max(rounding, moduli[e]);
2221 for (std::size_t i {0}; i < p; ++i) {
2222 gap = std::max(gap, std::abs(whole[(i * p) + i] -
diagonal[i]));
2224 gap = std::max(gap, std::numeric_limits<double>::epsilon() * rounding /
static_cast<double>(count));
2225 return size > 0.0 ? gap / size : gap;
2235 const buffer<std::complex<double>>& half,
2240 for (std::size_t e {0}; e < whole.size(); ++e) {
2241 error[e] = (whole[e] - half[e]) + (std::numeric_limits<double>::epsilon() * (moduli[e] /
static_cast<double>(count)) *
rounding_direction(e));
2261 [[nodiscard]]
inline std::tuple<buffer<std::complex<double>>, double,
double>
assembled_function(
const matrix<std::complex<double>>& t,
2263 const std::vector<
buffer<std::complex<double>>>& blocks,
2264 const std::vector<
buffer<std::complex<double>>>& errors,
2265 const std::vector<std::complex<double>>& at_eigenvalues)
2267 using C = std::complex<double>;
2268 const std::size_t n {t.rows()};
2269 const std::size_t count {circles.
radii.size()};
2272 for (std::size_t b {0}; b < count; ++b) {
2273 const std::size_t first {circles.
starts[b]};
2274 const std::size_t p {circles.
starts[b + 1] - first};
2276 fx[(first * n) + first] = at_eigenvalues[first];
2277 error[(first * n) + first] = std::numeric_limits<double>::epsilon() * at_eigenvalues[first] *
rounding_direction(first);
2280 for (std::size_t i {0}; i < p; ++i) {
2281 std::copy_n(blocks[b].data() + (i * p), p, fx.data() + ((first + i) * n) + first);
2282 std::copy_n(errors[b].data() + (i * p), p,
error.data() + ((first + i) * n) + first);
2285 double separation {std::numeric_limits<double>::infinity()};
2286 for (std::size_t b {0}; b < count; ++b) {
2287 for (std::size_t i {circles.
starts[b]}; i < circles.
starts[b + 1]; ++i) {
2288 for (std::size_t j {circles.
starts[b + 1]}; j < n; ++j) {
2289 separation = std::min(separation, std::abs(t(i, i) - t(j, j)));
2295 return {std::move(fx), std::min(1.0, std::max(
parlett_estimate(t, separation), estimate)), estimate};
2306 [[nodiscard]]
inline std::tuple<buffer<std::complex<double>>, double, std::vector<double>>
clustered_function(
const matrix<std::complex<double>>& t,
2307 const std::vector<std::complex<double>>& images,
2309 const std::vector<std::size_t>& counts)
2311 using C = std::complex<double>;
2312 const std::size_t n {t.rows()};
2314 const std::size_t drawn {
static_cast<std::size_t
>(std::ranges::count_if(circles.radii, [](
double r) { return r > 0.0; }))};
2315 const bool even {std::ranges::all_of(counts, [](std::size_t c) {
return c >= 2 && c % 2 == 0; })};
2316 if (counts.size() != drawn || !even || images.size() - n != std::accumulate(counts.begin(), counts.end(), std::size_t {0})) {
2317 throw dimension_error(
"funm requires one value per eigenvalue and an even count on each circle");
2319 std::vector<buffer<C>> blocks(circles.radii.size());
2320 std::vector<buffer<C>> errors(circles.radii.size());
2321 std::vector<double> contours;
2322 std::size_t next {n};
2323 for (std::size_t b {0}; b < circles.radii.size(); ++b) {
2324 const std::size_t first {circles.starts[b]};
2325 const std::size_t p {circles.starts[b + 1] - first};
2329 const std::size_t count {counts[contours.size()]};
2332 std::vector<C> even_images;
2333 std::vector<C> odd_images;
2334 for (std::size_t k {0}; k < count; ++k) {
2335 (k % 2 == 0 ? even_images : odd_images).push_back(images[next + k]);
2338 add_circle_terms(t, first, p, circles.centres[b], circles.radii[b], count, 0, 2, even_images.data(), half, moduli);
2339 add_circle_terms(t, first, p, circles.centres[b], circles.radii[b], count, 1, 2, odd_images.data(), odd, moduli);
2341 for (std::size_t e {0}; e < p * p; ++e) {
2342 whole[e] = half[e] + odd[e];
2344 contours.push_back(
circle_integral(whole, half, moduli, p, count, images.data() + first));
2346 blocks[b] = std::move(whole);
2349 const std::vector<C> at_eigenvalues(images.begin(), images.begin() +
static_cast<std::ptrdiff_t
>(n));
2350 auto [fx, estimate, recurrence] {
assembled_function(t, circles, blocks, errors, at_eigenvalues)};
2351 static_cast<void>(recurrence);
2352 const double contour_error {*std::ranges::max_element(contours)};
2353 return {std::move(fx), std::min(1.0, std::max(estimate, contour_error)), std::move(contours)};
2360 std::vector<double>&& contours,
2361 const std::vector<std::complex<double>>& at_eigenvalues)
2363 for (
const std::complex<double>& entry : x) {
2366 for (
const std::complex<double>& image : at_eigenvalues) {
2369 return {std::move(x),
error, std::move(contours)};
2384 bool hermitian {
false};
2385 double share {detail::cluster_share};
2396 template <
typename T>
2397 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2400 using C = std::complex<double>;
2404 detail::require_finite(a,
"funm");
2405 const std::size_t n {a.
rows()};
2407 if (detail::exactly_hermitian(a)) {
2408 const auto [values, vectors] {detail::hermitian_system(a)};
2410 for (std::size_t i {0}; i < n; ++i) {
2411 diagonal[(i * n) + i] = C {values[i]};
2415 plan.
points = detail::diagonal_of(plan.
t);
2419 std::tie(plan.
t, plan.
z) = detail::function_schur_form(a);
2420 plan.
points = detail::diagonal_of(plan.
t);
2421 if (!detail::clusters_separate(plan.
points, plan.
share)) {
2422 plan.
share = detail::cluster_share_fine;
2424 if (detail::gather_clusters(plan.
t, plan.
z, plan.
share)) {
2425 plan.
points = detail::diagonal_of(plan.
t);
2427 plan.
counts = detail::starting_points(circles);
2428 const std::vector<std::complex<double>> around {detail::circle_points(circles, plan.
counts)};
2429 plan.
points.insert(plan.
points.end(), around.begin(), around.end());
2442 const std::vector<std::complex<double>>& images)
2444 using C = std::complex<double>;
2445 const std::size_t n {plan.
t.
rows()};
2446 if (images.size() != plan.
points.size() || images.size() < n) {
2447 throw dimension_error(
"funm requires a square Schur form T, Z of its order and one value per eigenvalue");
2449 const std::vector<C> at_eigenvalues(images.begin(), images.begin() +
static_cast<std::ptrdiff_t
>(n));
2450 if (!plan.
hermitian && images.size() == n) {
2454 double error {std::numeric_limits<double>::epsilon()};
2455 std::vector<double> contours;
2457 x = detail::spectral<C>(plan.
z, at_eigenvalues,
false);
2460 auto [f_of_t, estimate, integrals] {detail::clustered_function(plan.
t, images, plan.
share, plan.
counts)};
2461 x = plan.
z *
matrix<C> {n, n, std::move(f_of_t)} *detail::adjoint_of(plan.
z);
2463 contours = std::move(integrals);
2465 return detail::funm_answer(std::move(x),
error, std::move(contours), at_eigenvalues);
2474 std::vector<std::complex<double>> points {detail::diagonal_of(plan.
t)};
2475 const std::vector<std::complex<double>> around {detail::circle_points(detail::circles_of(plan.
t, plan.
share), plan.
counts)};
2476 points.insert(points.end(), around.begin(), around.end());
2490 plan.
points = detail::diagonal_of(plan.
t);
2491 if (detail::gather_clusters(plan.
t, plan.
z, share)) {
2492 plan.
counts = detail::starting_points(detail::circles_of(plan.
t, share));
2508 template <
typename T>
2509 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2511 const std::function<std::vector<std::complex<double>>(
const std::vector<std::complex<double>>&)>& f)
2513 using C = std::complex<double>;
2518 const auto evaluated = [&f](
const funm_plan& plan) -> std::pair<funm_result, double> {
2519 const std::vector<C> images {f(plan.points)};
2520 const std::size_t n {plan.t.rows()};
2521 if (!plan.hermitian && plan.counts.empty() && images.size() == n) {
2522 return detail::parlett_function(plan.t, plan.z, images);
2524 if (plan.hermitian || plan.counts.empty() || images.size() != plan.points.size()) {
2526 const double own {answer.
error};
2527 return {std::move(answer), own};
2530 std::vector<std::size_t> at;
2531 std::vector<buffer<C>> sums;
2532 std::vector<buffer<C>> halves;
2533 std::vector<buffer<double>> moduli;
2534 for (std::size_t b {0}; b < circles.radii.size(); ++b) {
2535 if (circles.radii[b] > 0.0) {
2539 std::size_t next {n};
2540 for (std::size_t c {0}; c < at.size(); ++c) {
2541 const std::size_t b {at[c]};
2542 const std::size_t p {circles.
starts[b + 1] - circles.starts[b]};
2543 std::vector<C> even_images;
2544 std::vector<C> odd_images;
2545 for (std::size_t k {0}; k < plan.counts[c]; ++k) {
2546 (k % 2 == 0 ? even_images : odd_images).push_back(images[next + k]);
2548 next += plan.counts[c];
2552 detail::add_circle_terms(plan.t, circles.starts[b], p, circles.centres[b], circles.radii[b], plan.counts[c], 0, 2, even_images.data(), half, sizes);
2553 detail::add_circle_terms(plan.t, circles.starts[b], p, circles.centres[b], circles.radii[b], plan.counts[c], 1, 2, odd_images.data(), odd, sizes);
2554 moduli.push_back(std::move(sizes));
2555 for (std::size_t e {0}; e < p * p; ++e) {
2558 sums.push_back(std::move(odd));
2559 halves.push_back(std::move(half));
2561 std::vector<std::size_t> counts {plan.counts};
2562 std::vector<double> errors(at.size());
2563 std::vector<bool> settled(at.size(),
false);
2564 std::vector<buffer<C>> blocks(circles.radii.size());
2565 std::vector<buffer<C>> block_errors(circles.radii.size());
2566 const auto integrals = [&] {
2567 for (std::size_t c {0}; c < at.size(); ++c) {
2568 const std::size_t b {at[c]};
2569 const std::size_t p {circles.starts[b + 1] - circles.starts[b]};
2572 errors[c] = detail::circle_integral(whole, half, moduli[c], p, counts[c], images.data() + circles.starts[b]);
2573 block_errors[b] = detail::circle_error(whole, half, moduli[c], counts[c]);
2574 blocks[b] = std::move(whole);
2579 std::vector<C> points;
2580 std::vector<std::size_t> refined;
2581 for (std::size_t c {0}; c < at.size(); ++c) {
2582 if (!settled[c] && errors[c] > detail::contour_tolerance && 2 * counts[c] <= detail::contour_points_most) {
2583 const std::vector<C> fresh {detail::grid_points(circles.centres[at[c]], circles.radii[at[c]], 2 * counts[c], 1, 2)};
2584 points.insert(points.end(), fresh.begin(), fresh.end());
2585 refined.push_back(c);
2591 if (refined.empty()) {
2594 const std::vector<C> fresh_images {f(points)};
2595 if (fresh_images.size() != points.size()) {
2596 throw dimension_error(
"funm requires f to return one value per point");
2598 const std::vector<double> before {errors};
2599 std::size_t offset {0};
2600 for (
const std::size_t c : refined) {
2601 const std::size_t b {at[c]};
2602 const std::size_t p {circles.starts[b + 1] - circles.starts[b]};
2604 detail::add_circle_terms(plan.t, circles.starts[b], p, circles.centres[b], circles.radii[b], 2 * counts[c], 1, 2, fresh_images.data() + offset, added, moduli[c]);
2605 offset += counts[c];
2606 halves[c] = sums[c];
2607 for (std::size_t e {0}; e < p * p; ++e) {
2608 sums[c][e] += added[e];
2613 for (
const std::size_t c : refined) {
2614 settled[c] = !(errors[c] < 0.5 * before[c]);
2617 const std::vector<C> at_eigenvalues(images.begin(), images.begin() +
static_cast<std::ptrdiff_t
>(n));
2618 auto [f_of_t, estimate, recurrence] {detail::assembled_function(plan.t, circles, blocks, block_errors, at_eigenvalues)};
2619 const double contour_error {*std::ranges::max_element(errors)};
2620 funm_result answer {detail::funm_answer(plan.z *
matrix<C> {n, n, std::move(f_of_t)} *detail::adjoint_of(plan.z),
2621 std::min(1.0, std::max(estimate, contour_error)), std::move(errors), at_eigenvalues)};
2622 const double own {std::isinf(answer.error) ? answer.
error : std::min(1.0, std::max(recurrence, contour_error))};
2623 return {std::move(answer), own};
2626 auto best {evaluated(plan)};
2628 if (plan.share != detail::cluster_share_fine && best.second > detail::funm_fallback_error && !best.first.contours.empty()) {
2629 auto fine {evaluated(
regathered(plan, detail::cluster_share_fine))};
2630 if (fine.second < best.second) {
2631 best = std::move(fine);
2638 if (best.second > detail::funm_fallback_error && !best.first.contours.empty()) {
2639 auto apart {detail::parlett_function(plan.t, plan.z, f(detail::diagonal_of(plan.t)))};
2640 if (apart.second < best.second) {
2641 best = std::move(apart);
2646 double largest {1.0};
2647 for (
const std::complex<double>& value : detail::diagonal_of(plan.t)) {
2648 largest = std::max(largest, std::abs(value));
2650 if (best.second > detail::funm_fallback_error && largest > 1.0) {
2651 auto absolute {evaluated(
regathered(plan, detail::cluster_share / largest))};
2652 if (absolute.second < best.second) {
2653 best = std::move(absolute);
2657 return std::move(best.first);
2668 bool exactly_singular {
false};
2669 bool nearly_singular {
false};
2676 inline constexpr std::array<double, 8>
log_pade_bounds {0.0, 1.59e-5, 2.31e-3, 1.94e-2, 6.21e-2, 1.28e-1, 2.06e-1, 2.88e-1};
2680 inline constexpr std::array<double, 8>
power_pade_bounds {0.0, 1.51e-5, 2.24e-3, 1.88e-2, 6.04e-2, 1.24e-1, 2.00e-1, 2.79e-1};
2684 [[nodiscard]]
inline double unwinding(
const std::complex<double>& z)
2686 return std::ceil((z.imag() - std::numbers::pi) / (2.0 * std::numbers::pi));
2694 [[nodiscard]]
inline std::complex<double>
briggs(std::complex<double> a,
2697 using C = std::complex<double>;
2704 std::size_t remaining {k};
2705 if (std::arg(a) >= std::numbers::pi / 2.0) {
2709 const C z0 {a - C {1.0}};
2711 C product {C {1.0} + a};
2712 for (std::size_t j {1}; j < remaining; ++j) {
2714 product *= C {1.0} + a;
2716 return z0 / product;
2722 const std::complex<double>& l2,
2723 const std::complex<double>& t12,
2726 using C = std::complex<double>;
2730 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2733 const C z {(l2 - l1) / (l2 + l1)};
2737 const double u {
unwinding(log2 - log1)};
2738 const C b {p * (
complex_atanh(z) + (std::numbers::pi * C {0.0, 1.0} *u))};
2745 const std::complex<double>& l2,
2746 const std::complex<double>& t12)
2748 using C = std::complex<double>;
2752 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2755 const C z {(l2 - l1) / (l2 + l1)};
2757 return t12 * C {2.0} *(
complex_atanh(z) + (std::numbers::pi * C {0.0, 1.0} *u)) / (l2 - l1);
2768 const double z0 {a - 1.0};
2770 double product {1.0 + a};
2771 for (std::size_t j {1}; j < k; ++j) {
2775 return z0 / product;
2785 return t12 * p * std::exp((p - 1.0) * std::log(l1));
2787 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2788 return t12 * (std::exp(p * std::log(l2)) - std::exp(p * std::log(l1))) / (l2 - l1);
2790 const double scaled {t12 * std::exp((p / 2.0) * (std::log(l2) + std::log(l1)))};
2791 return scaled * (2.0 * std::sinh(p * std::atanh((l2 - l1) / (l2 + l1))) / (l2 - l1));
2802 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2803 return t12 * (std::log(l2) - std::log(l1)) / (l2 - l1);
2805 return t12 * 2.0 * std::atanh((l2 - l1) / (l2 + l1)) / (l2 - l1);
2815 [[nodiscard]]
inline std::complex<double>
scalar_log(
const std::complex<double>& z)
2824 template <
typename T>
2830 std::size_t n) : shifted_ {t}, n_ {n}
2832 for (std::size_t i {0}; i < n; ++i) {
2833 shifted_[(i * n) + i] -= T {1.0};
2840 while (norms_.size() + 1 < p) {
2842 std::swap(power_, spare_);
2843 norms_.push_back(
one_norm(power_, n_));
2845 return std::pow(norms_[p - 2], 1.0 /
static_cast<double>(p));
2869 for (std::size_t i {0}; i < n; ++i) {
2870 const std::complex<double> lambda {t[(i * n) + i]};
2871 if (!(lambda.real() > 0.0 || lambda.imag() != 0.0)) {
2885 template <
typename T>
2888 const std::array<double, 8>& theta = log_pade_bounds,
2889 const char* name =
"logm")
2891 const auto bound = [&theta](std::size_t m) {
return theta[m]; };
2894 for (std::size_t i {0}; i < n; ++i) {
2897 const auto far = [&
diagonal, &bound]() {
2898 double largest {0.0};
2900 largest = std::max(largest, std::abs(d - T {1.0}));
2902 return largest > bound(7);
2911 for (std::size_t i {0}; i < s0; ++i) {
2916 const double a2 {std::max(norms(2), norms(3))};
2917 std::size_t m {a2 <= bound(1) ? std::size_t {1} : (a2 <= bound(2) ? std::size_t {2} : std::size_t {0})};
2919 const double d3 {norms(3)};
2920 const double d4 {norms(4)};
2921 const double a3 {std::max(d3, d4)};
2922 if (!std::isfinite(a3)) {
2923 throw convergence_error(std::string {name} +
": the square roots of the triangular form are not finite");
2925 if (a3 <= bound(7)) {
2927 while (a3 > bound(j1)) {
2936 if (a3 / 2.0 <= bound(5)) {
2943 const double d5 {norms(5)};
2944 const double eta {std::min(a3, std::max(d4, d5))};
2945 m = eta <= bound(6) ? std::size_t {6} : (eta <= bound(7) ? std::size_t {7} : std::size_t {0});
2952 for (std::size_t i {0}; i < n; ++i) {
2953 t[(i * n) + i] -= T {1.0};
2956 const double p {std::ldexp(1.0, -
static_cast<int>(s))};
2957 for (std::size_t j {0}; j < n; ++j) {
2958 t[(j * n) + j] =
briggs(t0[(j * n) + j], s);
2964 return {std::move(t), s, m};
2973 template <
typename T>
2977 static constexpr std::array<std::array<double, 7>, 7> nodes {{
2979 {0.21132486540518708, 0.7886751345948129},
2980 {0.1127016653792583, 0.5, 0.8872983346207417},
2981 {0.06943184420297371, 0.33000947820757187, 0.6699905217924281, 0.9305681557970262},
2982 {0.04691007703066802, 0.23076534494715845, 0.5, 0.7692346550528415, 0.9530899229693319},
2983 {0.033765242898423975, 0.16939530676686776, 0.3806904069584015, 0.6193095930415985, 0.8306046932331322, 0.966234757101576},
2984 {0.0254460438286207, 0.12923440720030277, 0.2970774243113014, 0.5, 0.7029225756886985, 0.8707655927996972, 0.9745539561713793}}};
2985 static constexpr std::array<std::array<double, 7>, 7> weights {{
2988 {0.2777777777777779, 0.44444444444444414, 0.2777777777777779},
2989 {0.17392742256872679, 0.3260725774312732, 0.3260725774312732, 0.17392742256872679},
2990 {0.11846344252809478, 0.2393143352496831, 0.2844444444444443, 0.2393143352496831, 0.11846344252809478},
2991 {0.08566224618958473, 0.1803807865240696, 0.2339569672863457, 0.2339569672863457, 0.1803807865240696, 0.08566224618958473},
2992 {0.06474248308443482, 0.13985269574463827, 0.19091502525255954, 0.20897959183673465, 0.19091502525255954, 0.13985269574463827,
2993 0.06474248308443482}}};
2998 for (std::size_t q {0}; q < m; ++q) {
2999 const double alpha {weights[m - 1][q]};
3000 const double beta {nodes[m - 1][q]};
3001 for (std::size_t e {0}; e < n * n; ++e) {
3002 shifted[e] = beta * r[e];
3003 term[e] = alpha * r[e];
3005 for (std::size_t i {0}; i < n; ++i) {
3006 shifted[(i * n) + i] += T {1.0};
3009 for (std::size_t e {0}; e < n * n; ++e) {
3013 const double power {std::ldexp(1.0,
static_cast<int>(s))};
3018 for (std::size_t i {0}; i < n; ++i) {
3019 u[(i * n) + i] =
scalar_log(t0[(i * n) + i]);
3021 u[(i * n) + i + 1] =
log_superdiagonal(t0[(i * n) + i], t0[((i + 1) * n) + i + 1], t0[(i * n) + i + 1]);
3031 template <
typename T>
3035 constexpr double tiny {1e-20};
3038 for (std::size_t i {0}; i < n; ++i) {
3039 const T& d {t[(i * n) + i]};
3040 exact = exact || std::abs(d) == 0.0;
3041 near = near || std::abs(d) < tiny;
3044 for (std::size_t i {0}; i < n; ++i) {
3045 t[(i * n) + i] = std::abs(t[(i * n) + i]) == 0.0 ? T {tiny} : t[(i * n) + i];
3048 return {exact, near && !exact};
3082 const double j {
static_cast<double>(i) / 2.0};
3083 return (t - j) / (2.0 * ((2.0 * j) - 1.0));
3085 const double j {(
static_cast<double>(i) - 1.0) / 2.0};
3086 return (-j - t) / (2.0 * ((2.0 * j) + 1.0));
3099 using C = std::complex<double>;
3101 for (std::size_t e {0}; e < n * n; ++e) {
3105 for (std::size_t j {(2 * m) - 1}; j >= 1; --j) {
3106 for (std::size_t e {0}; e < n * n; ++e) {
3109 for (std::size_t i {0}; i < n; ++i) {
3110 y[(i * n) + i] += C {1.0};
3115 for (std::size_t i {0}; i < n; ++i) {
3116 y[(i * n) + i] += C {1.0};
3133 using C = std::complex<double>;
3135 for (std::size_t i {0}; i < n; ++i) {
3136 for (std::size_t j {i + 1}; j < n; ++j) {
3142 for (std::size_t i {0}; i < n; ++i) {
3154 for (std::size_t i {s + 1}; i-- > 0;) {
3159 const double p {std::ldexp(t, -
static_cast<int>(i))};
3160 for (std::size_t j {0}; j < n; ++j) {
3182 for (std::size_t i {0}; i < n; ++i) {
3184 for (std::size_t j {i + 1}; j < n; ++j) {
3195 const std::size_t n {similar.
rows()};
3197 for (std::size_t i {0}; i < n; ++i) {
3198 u[(i * n) + i] = std::pow(similar(i, i), p);
3199 for (std::size_t j {i + 1}; j < n; ++j) {
3208 template <
typename T>
3216 template <
typename T>
3221 return {std::move(v), std::move(similar)};
3234 using C = std::complex<double>;
3235 const std::size_t n {similar.rows()};
3236 buffer<C> upper(similar.begin(), similar.end());
3237 for (std::size_t i {0}; i < n; ++i) {
3238 upper[(i * n) + i] = C {upper[(i * n) + i].real(), 0.0};
3239 for (std::size_t j {0}; j < i; ++j) {
3240 upper[(i * n) + j] = C {};
3255 using C = std::complex<double>;
3257 const std::size_t n {v.rows()};
3259 bool positive {
true};
3260 for (std::size_t i {0}; i < n; ++i) {
3261 positive = positive && s.
similar(i, i) > 0.0;
3269 for (std::size_t k {0}; k < n * n; ++k) {
3270 real[k] = u[k].real();
3271 imaginary[k] = u[k].imag();
3277 for (std::size_t k {0}; k < n * n; ++k) {
3278 power[k] = C {
real_part(k / n, k % n), imaginary_part(k / n, k % n)};
3280 return matrix<C> {n, n, std::move(power)};
3288 const std::size_t n {s.vectors.
rows()};
3296 template <
typename T>
3301 using C = std::complex<double>;
3302 const std::size_t n {a.
rows()};
3317 for (std::size_t i {0}; i < n; ++i) {
3318 if (
triangle[(i * n) + i] == C {}) {
3319 return std::nullopt;
3334 template <
typename T>
3338 const std::size_t n {a.
rows()};
3340 std::optional<matrix<T>> result;
3341 for (
double k {std::abs(e)}; k > 0.0;) {
3342 if (std::fmod(k, 2.0) == 1.0) {
3345 k = std::floor(k / 2.0);
3354 for (std::size_t i {0}; i < n; ++i) {
3355 unit[(i * n) + i] = T {1.0};
3357 return matrix<T> {n, n, std::move(unit)};
3377 template <
typename T>
3378 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3382 using C = std::complex<double>;
3383 const std::size_t n {a.
rows()};
3384 if (a.
cols() != n) {
3385 throw dimension_error(
"fractional_matrix_power requires a square matrix");
3387 detail::require_finite(a,
"fractional_matrix_power");
3388 if (!std::isfinite(p)) {
3389 throw argument_error(
"fractional_matrix_power: the power must be finite");
3394 if (p == std::floor(p)) {
3395 return detail::as_complex(detail::integer_power(a, p));
3399 if (p > 0.0 && detail::exactly_hermitian(a)) {
3400 const auto [values, vectors] {detail::hermitian_system(a)};
3401 std::vector<C> powers(values.size());
3402 for (std::size_t k {0}; k < powers.size(); ++k) {
3403 powers[k] = detail::principal_power(C {values[k]}, p);
3405 return detail::spectral<C>(vectors, powers, std::all_of(values.begin(), values.end(), [](
double v) { return v >= 0.0; }));
3410 std::optional<detail::hermitian_similarity<T>> similarity;
3411 double largest {0.0};
3412 double smallest {0.0};
3413 if (detail::exactly_hermitian(a) && !detail::upper_triangular(a)) {
3414 similarity = detail::similarity_of(a);
3415 smallest = std::numeric_limits<double>::infinity();
3416 for (std::size_t i {0}; i < n; ++i) {
3417 const double magnitude {std::abs(std::real(similarity->similar(i, i)))};
3418 largest = std::max(largest, magnitude);
3419 smallest = std::min(smallest, magnitude);
3425 smallest = sigma[n - 1];
3427 if (smallest != 0.0) {
3428 const double k2 {largest / smallest};
3429 const double p1 {p - std::floor(p)};
3430 const double p2 {p - std::ceil(p)};
3431 const bool below {p1 * std::pow(k2, 1.0 - p1) <= -p2 * k2};
3432 const double whole {below ? std::floor(p) : std::ceil(p)};
3433 if (
const auto remainder {detail::remainder_power(a, below ? p1 : p2, similarity)}) {
3434 return detail::as_complex(detail::integer_power(a, whole)) * *
remainder;
3440 const double fraction {p - std::floor(p)};
3441 const auto power = [fraction](
const std::vector<C>& values) {
3442 std::vector<C> powers(values.size());
3443 std::transform(values.begin(), values.end(), powers.begin(), [fraction](
const C& z) { return detail::principal_power(z, fraction); });
3446 return detail::as_complex(detail::integer_power(a, std::floor(p))) *
funm(a, power).
f;
3453 template <
typename T>
3466 for (std::size_t i {0}; i < t.
rows(); ++i) {
3467 if (t(i, i) < 0.0) {
3478 using C = std::complex<double>;
3491 using C = std::complex<double>;
3521 template <
typename T>
3522 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3525 using C = std::complex<double>;
3526 const std::size_t n {a.
rows()};
3527 if (a.
cols() != n) {
3530 detail::require_finite(a,
"logm");
3534 if (detail::exactly_hermitian(a)) {
3535 const auto [values, vectors] {detail::hermitian_system(a)};
3536 std::vector<C> logs(n);
3537 bool regular {
true};
3538 for (std::size_t k {0}; k < n; ++k) {
3539 regular = regular && std::abs(values[k]) >= 1e-20;
3540 logs[k] = detail::complex_log(C {values[k]});
3543 return {detail::spectral<C>(vectors, logs, values[0] > 0.0),
false,
false};
3546 return detail::general_logm(a);
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.
‖(T − I)ᵖ‖₁^(1/p) of the upper triangular n × n t, p from 2, exactly (SciPy estimates them,...
std::vector< double > norms_
‖(T − I)ᵖ‖₁ for p from 2.
shifted_power_norms(const buffer< T > &t, std::size_t n)
double operator()(std::size_t p)
A standard exception Std that numerical::error tags too, its one what answering for both bases.
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 eigenvalues and eigenvectors of a complex Hermitian matrix.
An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of ...
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.
buffer< T > elements() &&
The elements, row-major, handed over by a matrix about to expire, which is left 0 × 0: a large result...
std::size_t cols() const noexcept
The number of columns.
Thrown when a real matrix has no real principal square root (a real eigenvalue below 0): its root is ...
no_real_root_error(const std::string &message)
Builds the error.
Thrown when a decomposition's input holds an infinite or NaN entry: no factorisation of it means anyt...
The Schur decomposition A = Z T Zᴴ of a square matrix, as scipy.linalg.schur (LAPACK's dgees/zgees): ...
const matrix< T > & t() const &noexcept
T, upper quasi-triangular (real) or triangular (complex).
Thrown when a matrix has no unique solution (it is singular).
The eigenvalues and eigenvectors of a real symmetric matrix.
A dense vector of T with value semantics.
The elementary functions of a complex number of float or double as the GNU C library computes them (N...
The eigenvalues and eigenvectors of a general square matrix.
matrix< std::complex< double > > hermitian_remainder_power(const hermitian_similarity< double > &s, double t)
A^t (−1 < t < 1) of a real symmetric A not triangular from s: V T^t Vᵀ, T the upper triangle of Vᵀ A ...
constexpr std::size_t contour_points_most
The most points on one cluster's circle: funm doubles them from contour_points while the integrals' e...
constexpr double cluster_share_fine
The finer share funm falls back to where clusters at cluster_share leave its estimate past funm_fallb...
std::pair< buffer< T >, buffer< T > > frechet_pade(const buffer< T > &a, const buffer< T > &e, std::size_t n, std::size_t m)
e^A and its Fréchet derivative L(A, E) from the [m/m] Padé approximant, as Al-Mohy and Higham's algor...
double cluster_bound(const std::vector< std::complex< double > > &values, double share)
The clusters' bound: eigenvalues within share of the largest modulus (or of 1) gather (cluster_share,...
std::complex< double > briggs(std::complex< double > a, std::size_t k)
a^(1/2^k) − 1 without the cancellation of the subtraction, as SciPy's _briggs_helper_function (Al-Moh...
std::complex< R > complex_log(const std::complex< R > &z)
log(z): log|z| + i arg(z), log|z| as log1p(|z|² − 1) / 2 near the unit circle (|z|² − 1 exact or almo...
constexpr double contour_tolerance
The integrals' estimate below which funm takes no more points.
std::pair< matrix< std::complex< double > >, matrix< std::complex< double > > > function_schur_form(const matrix< double > &a)
A real matrix's complex Schur form as scipy.linalg.funm takes it: the real form made complex (rsf2csf...
void exact_triangular_bands(buffer< T > &x, const buffer< T > &t, std::size_t n, double scale)
The diagonal and first superdiagonal of exp(scale · T) written exactly into x for the upper triangula...
std::complex< R > complex_sinh(const std::complex< R > &z)
sinh(z): sinh(re) cos(im) + i cosh(re) sin(im) of |re|, the sign of re carried by the cosine; past ex...
void triangular_sylvester(const buffer< T > &r, std::size_t m, const buffer< T > &s, std::size_t n, buffer< T > &f)
Y of R Y + Y S = F in place in f (m × n, row-major) for the upper quasi-triangular (real) or triangul...
buffer< T > pointwise_square_root(const buffer< T > &t, std::size_t n)
The principal square root of the upper triangular n × n row-major t (no real eigenvalue below 0 where...
std::complex< double > principal_power(const std::complex< double > &z, double p)
z to the real power p, principal: exp(p log z) (0 for z = 0 and p > 0).
void solve_upper_blocks(const matrix< std::complex< double > > &t, const std::vector< std::size_t > &starts, buffer< std::complex< double > > &x, const std::complex< double > *sources)
double power_pade_constant(std::size_t i, double t)
The coefficient cᵢ (i ≥ 1) of the continued fraction of (1 − x)ᵗ, as SciPy's _fractional_power_pade_c...
constexpr std::array< double, 8 > power_pade_bounds
The bounds θ_m of the [m/m] Padé approximant of (I − X)ᵗ (Higham and Lin's table 3....
bool upper_triangular(const matrix< T > &a)
Whether the square a is upper triangular: its Schur form as it stands, Z = I (as SciPy takes it,...
double one_norm(const buffer< T > &a, std::size_t n)
The 1-norm of the n × n row-major a (n from 1): its largest column sum of moduli.
std::pair< vector< double >, matrix< double > > hermitian_system(const matrix< double > &a)
The eigenvalues (ascending) and orthonormal eigenvectors of the real symmetric a.
buffer< T > square_product(const buffer< T > &a, const buffer< T > &b, std::size_t n)
The n × n product A B of row-major operands (square_product_into, into storage of its own).
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.
T square(const T &x)
x · x, by the type's own product (a complex one's C Annex G, as the library's *).
matrix< std::complex< double > > hermitian_root(const matrix< T > &a)
The principal square root of the Hermitian a, V √Λ Vᴴ: Hermitian where no eigenvalue is below 0.
constexpr double cluster_share
The share of the largest modulus (or of 1) within which eigenvalues gather (cluster_bound): Davies an...
void small_sylvester_block(const T *r, std::size_t ldr, const T *s, std::size_t lds, std::size_t rows, std::size_t cols, T *c, std::size_t ldc, double smin)
The rows × cols y of R y + y S = c (each at most 2, row-major in c, overwritten) for the diagonal blo...
std::size_t schur_block(const buffer< double > &t, std::size_t n, std::size_t k)
The order of the diagonal block of the upper quasi-triangular t (n × n, row-major) that starts at k: ...
std::tuple< buffer< std::complex< double > >, double, std::vector< double > > clustered_function(const matrix< std::complex< double > > &t, const std::vector< std::complex< double > > &images, double share, const std::vector< std::size_t > &counts)
f(T) of the Schur form t with clusters within share as runs of its diagonal, from images,...
double column_sum_norm(const buffer< double > &moduli, std::size_t n)
The 1-norm of the n × n row-major matrix whose entries' moduli are moduli (n from 1): its largest col...
taylor_plan plan_taylor(double norm, std::size_t columns, const std::function< double(std::size_t)> &power_norm)
Al-Mohy and Higham's code fragment 3.1 (2011), as SciPy's _fragment_3_1 (m_max 55,...
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
bool exactly_hermitian(const matrix< T > &a)
Whether a is Hermitian to the bit (symmetric where real), its diagonal real: a function of it is then...
T sinch(const T &x)
sinh(x) / x, 1 at 0, by its series where x is small.
buffer< T > triangular_square_root(const buffer< T > &t, std::size_t n)
The principal square root of the upper triangular n × n row-major t (no real eigenvalue below 0 where...
logm_result schur_logm(buffer< T > t, std::size_t n, const matrix< T > *z)
log A from the upper triangular n × n t of A = Z T Zᴴ (z, or none where T is A), its zero diagonal en...
constexpr std::size_t square_root_block
The order of the diagonal blocks of triangular_square_root (SciPy's _sqrtm_triu's).
double frechet_bound(std::size_t m)
‖A‖₁ bounds of the [m/m] Padé approximants of the Fréchet derivative of the exponential,...
constexpr std::size_t funm_batch_elements
The elements of one batch of add_circle_terms's points (their p × p inverses, and as many of their sh...
void square_root_columns(const buffer< T > &t, buffer< T > &r, std::size_t n, const std::vector< std::size_t > &starts)
The off-diagonal blocks of the square root r (n × n, row-major) of the upper (quasi-)triangular t,...
std::size_t extra_squarings(const buffer< double > &moduli, std::size_t n, std::size_t m, double scale, double norm)
Al-Mohy and Higham's ℓ(A, m) (2009): the squarings to add so that the [m/m] approximant's backward er...
buffer< std::complex< double > > circle_error(const buffer< std::complex< double > > &whole, const buffer< std::complex< double > > &half, const buffer< double > &moduli, std::size_t count)
The error of a circle's integral whole as recurrence_error carries it above the diagonal: the two rul...
void square_product_into(const buffer< T > &a, const buffer< T > &b, std::size_t n, buffer< T > &c)
The n × n product A B of row-major operands into c, whatever it held (its elements not read,...
double parlett_estimate(const matrix< std::complex< double > > &t, double smallest)
SciPy's estimate for Parlett's recurrence on t: min(1, max(ε, ε ‖strict upper T‖₁ / δ)),...
std::optional< matrix< std::complex< double > > > remainder_power(const matrix< T > &a, double t, const std::optional< hermitian_similarity< T > > &similarity)
A^t (−1 < t < 1) by the Schur form, as SciPy's _remainder_matrix_power: an upper triangular A directl...
double unwinding(const std::complex< double > &z)
ceil((Im z − π) / 2π), the unwinding number of z (SciPy's _unwindk).
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).
std::pair< bool, bool > force_nonsingular(buffer< T > &t, std::size_t n)
The triangular form t made nonsingular as SciPy's _logm_force_nonsingular_triangular_matrix: a zero d...
hermitian_similarity< T > similarity_of(const matrix< T > &a)
hermitian_similarity of the Hermitian a.
std::vector< std::complex< double > > grid_points(std::complex< double > centre, double radius, std::size_t count, std::size_t from, std::size_t step)
The points k = from, from + step, … < count of the grid of count points on the circle (centre,...
double modulus_power_norm(const buffer< double > &moduli, std::size_t n, std::size_t p, double scale)
‖ |A|ᵖ ‖₁ of the n × n row-major moduli |A| (n from 1) times scale, exactly: the row 1ᵀ |scale A|ᵖ by...
bool principal_branch(const buffer< double > &, std::size_t)
log has its principal branch at every diagonal entry of a real triangular form logm keeps real: none ...
matrix< std::complex< double > > complex_square_root(const matrix< std::complex< double > > &form, const matrix< std::complex< double > > *z)
The principal square root of a complex matrix from its Schur form (triangular_square_root).
std::vector< std::size_t > eigenvalue_clusters(const std::vector< std::complex< double > > &values, double delta)
The clusters of values joined where two lie within delta (transitively), numbered by their first memb...
std::vector< std::complex< double > > circle_points(const cluster_circles &circles, const std::vector< std::size_t > &counts)
The points of circles, counts on the circles about clusters of two or more in turn,...
constexpr std::array< taylor_bound, 35 > taylor_bounds
The table of taylor_bound, m ascending.
std::complex< R > complex_exp(const std::complex< R > &z)
exp(z): exp(re) times cos(im) + i sin(im), a real part past exp_bound taken off in steps of it (each ...
buffer< T > both_products(const buffer< T > &p, const buffer< T > &q, std::size_t n)
P Q + Q P of n × n buffers.
std::vector< std::size_t > starting_points(const cluster_circles &circles)
The points to start each circle of circles about a cluster of two or more with: contour_points,...
buffer< std::complex< double > > nearly_diagonal_power(const buffer< std::complex< double > > &t, std::size_t n, double p)
T^t of a triangle t of order n whose strict upper part is a similarity's rounding (Zᴴ A Z,...
bool is_finite_entry(const T &x)
Whether x is finite.
std::complex< double > log_superdiagonal(const std::complex< double > &l1, const std::complex< double > &l2, const std::complex< double > &t12)
The superdiagonal entry of log T for the 2 × 2 upper triangular [[l1, t12], [0, l2]],...
std::complex< R > complex_atanh(const std::complex< R > &z)
atanh(z), as glibc's catanh: C's Annex G for the infinities and NaNs; π/2 and the reciprocal past 16/...
double row_sum_norm(const buffer< T > &x, std::size_t n, std::size_t k)
The largest row sum of moduli of the n × k row-major x (‖X‖∞).
double recurrence_error(const matrix< std::complex< double > > &t, const std::vector< std::size_t > &starts, const buffer< std::complex< double > > &fx, buffer< std::complex< double > > error)
The error of f(T), fx, from the block recurrence (solve_upper_blocks) over the runs starts of t's dia...
buffer< T > pade_approximant(const buffer< T > &a, const std::array< const buffer< T > *, 4 > &powers, std::size_t n, std::size_t m)
The [m/m] Padé approximant (V − U)⁻¹ (V + U) of the exponential of a, its even powers powers (A²,...
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 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,...
const matrix< std::complex< double > > & as_complex(const matrix< std::complex< double > > &a)
a itself: already complex.
constexpr std::size_t contour_points
The trapezoidal rule's points on each circle of Cauchy's integral.
std::complex< R > complex_sqrt(const std::complex< R > &z)
The square root of a complex number, as the GNU C library's csqrt computes it (NumPy's on Linux,...
constexpr double funm_fallback_error
The estimate past which funm tries the finer clusters (SciPy reports a result past it inaccurate).
buffer< T > triangular_log(const buffer< T > &t0, std::size_t n)
The logarithm of the upper triangular t0 (no zero on its diagonal), as SciPy's _logm_triu: R,...
void solve_triangular_in_place(const T *a, std::size_t n, bool lower, triangular_op op, bool unit_diagonal, T *x, std::size_t k)
numerical::solve_triangular on the n × n row-major a, in place in x (n × k, row-major): the triangle ...
constexpr double divided_exponentials_past
The half gap past which exact_triangular_bands divides the difference of the exponentials by the gap:...
const double * pade_coefficients(std::size_t m)
The coefficients b₀ … b_m of the [m/m] Padé approximant of the exponential, as Higham's (2005).
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
std::complex< double > rounding_direction(std::size_t place)
A direction of unit modulus for the rounding of entry place of an estimate's model,...
constexpr std::array< double, 8 > log_pade_bounds
The bounds θ_m of the [m/m] Padé approximant of log(I + X) (Al-Mohy and Higham's table 2....
bool nonnegative_diagonal(const matrix< double > &t)
Whether no diagonal entry of t is below 0.
buffer< std::complex< double > > power_pade(const buffer< std::complex< double > > &x, std::size_t n, double t, std::size_t m)
The [m/m] Padé approximant of (I − X)ᵗ for the upper triangular x, as SciPy's _fractional_power_pade:...
matrix< R > spectral(const matrix< T > &v, const std::vector< R > &f, bool hermitian)
V diag(f) Vᴴ in the arithmetic of R (double only for real v and f), the eigenvectors v orthonormal: o...
std::pair< matrix< std::complex< double > >, matrix< std::complex< double > > > complex_schur_form(const matrix< double > &t, const matrix< double > &z)
The complex Schur form of a real one, as SciPy's rsf2csf: each 2 × 2 block of t (a conjugate pair) tr...
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.
std::optional< matrix< double > > real_square_root(const matrix< double > &form, const matrix< double > *z)
The real principal square root of the real a from its real Schur form (Higham, 1987),...
std::tuple< buffer< T >, std::size_t, std::size_t > inverse_squaring(const buffer< T > &t0, std::size_t n, const std::array< double, 8 > &theta=log_pade_bounds, const char *name="logm")
Al-Mohy and Higham's inverse scaling and squaring (2012, algorithm 4.1) on the upper triangular t0,...
constexpr std::size_t upper_block_product_least
The blocks' size (rows × columns) from which solve_upper_blocks forms a block's terms by gemm: below ...
matrix< T > integer_power(const matrix< T > &a, double e)
a to the integer power e (a finite whole number) by repeated squaring, as numpy.linalg....
std::vector< std::complex< double > > diagonal_of(const matrix< std::complex< double > > &t)
The diagonal of the square t.
bool clusters_separate(const std::vector< std::complex< double > > &values, double share)
Whether the clusters of values within share are sound for circles_of, each cluster's farthest eigenva...
void add_circle_terms(const matrix< std::complex< double > > &t, std::size_t first, std::size_t p, std::complex< double > centre, double radius, std::size_t count, std::size_t from, std::size_t step, const std::complex< double > *images, buffer< std::complex< double > > &sum, buffer< double > &moduli)
Adds to sum, for the points k = from, from + step, … < count of the grid of count points on the circl...
double scalar_sqrt(double x)
√x of a real x at least 0.
void square_in_place(buffer< T > &x, buffer< T > &spare, std::size_t n)
x squared count times, the products alternating between its storage and spare's (resized as needed): ...
logm_result general_logm(const matrix< std::complex< double > > &a)
logm of a complex matrix past its Hermitian path: an upper triangular one directly,...
buffer< double > entry_moduli(const buffer< double > &a)
The moduli of a real matrix's entries.
bool gather_clusters(matrix< std::complex< double > > &t, matrix< std::complex< double > > &z, double share)
Reorders the complex Schur form t, z so each cluster of eigenvalues (eigenvalue_clusters,...
double circle_integral(buffer< std::complex< double > > &whole, buffer< std::complex< double > > &half, const buffer< double > &moduli, std::size_t p, std::size_t count, const std::complex< double > *diagonal)
A circle's integral from its rule's sum over count points, whole, and over the even ones,...
buffer< std::complex< double > > similar_power(const matrix< std::complex< double > > &similar, double t)
T^t for T the upper triangle of similar (Zᴴ A Z, Z a Hermitian A's eigenvectors): the similarity's ro...
std::tuple< buffer< std::complex< double > >, double, double > assembled_function(const matrix< std::complex< double > > &t, const cluster_circles &circles, const std::vector< buffer< std::complex< double > > > &blocks, const std::vector< buffer< std::complex< double > > > &errors, const std::vector< std::complex< double > > &at_eigenvalues)
The blocks of x above its diagonal (n × n, row-major, its diagonal blocks given) by the block recurre...
double scalar_log(double x)
log x of a real x above 0.
void add_scaled(buffer< T > &into, const buffer< T > &term, double coefficient)
into += coefficient · term over the n × n buffers.
std::pair< funm_result, double > parlett_function(const matrix< std::complex< double > > &t, const matrix< std::complex< double > > &z, const std::vector< std::complex< double > > &values)
funm_from_schur with the recurrence's own estimate beside (recurrence_error, without SciPy's floor,...
std::complex< double > fractional_power_superdiagonal(const std::complex< double > &l1, const std::complex< double > &l2, const std::complex< double > &t12, double p)
The superdiagonal entry of T^p for the 2 × 2 upper triangular [[l1, t12], [0, l2]],...
matrix< T > adjoint_of(const matrix< T > &m)
Mᴴ: the transpose, conjugated.
cluster_circles circles_of(const matrix< std::complex< double > > &t, double share)
cluster_circles of the Schur form t whose clusters are runs of its diagonal: a circle about each clus...
funm_result funm_answer(matrix< std::complex< double > > &&x, double error, std::vector< double > &&contours, const std::vector< std::complex< double > > &at_eigenvalues)
x with its estimate error, ∞ where an entry of x or f at an eigenvalue (at_eigenvalues) is not finite...
buffer< std::complex< double > > triangular_power(const buffer< std::complex< double > > &t0, std::size_t n, double t)
T^t (−1 < t < 1) of the upper triangular t0 (no zero on its diagonal), as SciPy's _remainder_matrix_p...
The NumericAL public API.
matrix< T > expm_multiply(const matrix< T > &a, const matrix< T > &b, double t=1.0)
e^{tA} B without forming e^{tA}, as scipy.sparse.linalg.expm_multiply: Al-Mohy and Higham's algorithm...
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...
double expm_cond(const matrix< T > &a)
The relative condition number of the exponential at a in the Frobenius norm, as scipy....
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 ...
logm_result logm(const matrix< T > &a)
The principal logarithm of a square matrix, as scipy.linalg.logm: an upper triangular A directly,...
tensor< T > triangle(const tensor< T > &t, std::ptrdiff_t k, bool lower)
The matrices of t (its last two axes) zero above their k diagonal (lower) or below it (else),...
funm_plan regathered(funm_plan plan, double share)
plan (not Hermitian) with its eigenvalues gathered anew within share of the largest modulus (or of 1)...
matrix< T > transpose(const matrix< T > &m)
The transpose, by blocks of transpose_tile (walked by detail::transpose_piece's pieces),...
matrix< std::complex< double > > sqrtm(const matrix< std::complex< double > > &a)
The principal square root X of a complex square matrix (X² = A, its eigenvalues of nonnegative real p...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
matrix< T > solve_continuous_lyapunov(const matrix< T > &a, const matrix< T > &q)
The solution X of the continuous Lyapunov equation A X + X Aᴴ = Q, as scipy.linalg....
funm_plan plan_funm(const matrix< T > &a)
The funm_plan of a: f is then wanted at its points, and finish_funm completes f(A).
constexpr std::size_t hermitian_expm_least
The order from which expm of a Hermitian matrix takes its eigendecomposition (below,...
frechet_method
How expm_frechet computes: Al-Mohy and Higham's algorithm (SciPy's "SPS"), or the exponential of the ...
@ scaling_pade_squaring
Al-Mohy and Higham's algorithm 6.4.
@ block_enlarge
expm of the 2n × 2n block matrix.
matrix< T > expm(const matrix< T > &a)
The exponential e^A of a square matrix, as scipy.linalg.expm: scaling and squaring of a Padé approxim...
matrix< std::complex< double > > complex_sqrtm(const matrix< double > &a)
The complex principal square root of a real square matrix, as scipy.linalg.sqrtm answers one with a r...
@ backward
The forward transform unscaled, the inverse scaled by 1/n (NumPy's default).
@ forward
The forward transform scaled by 1/n, the inverse unscaled.
funm_result finish_funm(const funm_plan &plan, const std::vector< std::complex< double > > &images)
f(A) from its funm_plan and images, f at the plan's points: a Hermitian A's V f(Λ) Vᴴ,...
funm_result funm(const matrix< T > &a, const std::function< std::vector< std::complex< double > >(const std::vector< std::complex< double > > &)> &f)
A function of a square matrix, as scipy.linalg.funm: plan_funm, f called once with the plan's points ...
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...
std::pair< matrix< T >, matrix< T > > expm_frechet(const matrix< T > &a, const matrix< T > &e, frechet_method method=frechet_method::scaling_pade_squaring)
e^A and the Fréchet derivative L(A, E) of the exponential at a along e, as scipy.linalg....
std::vector< std::complex< double > > funm_points(const funm_plan &plan)
The points where finish_funm wants f for plan (not Hermitian) with its circles' counts: its eigenvalu...
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 > inverse(matrix< T > a)
The inverse of a square matrix.
tensor< T > remainder(const tensor< T > &a, const tensor< T > &b)
a % b element by element, broadcast, as numpy.remainder (Python's: of b's sign; a real by zero fmod's...
matrix< std::complex< double > > fractional_matrix_power(const matrix< T > &a, double p)
A^p for a real p, as scipy.linalg.fractional_matrix_power: a whole p by repeated squaring; for p > 0,...
funm_result funm_from_schur(const matrix< std::complex< double > > &t, const matrix< std::complex< double > > &z, const std::vector< std::complex< double > > &values)
f(A) from the complex Schur form A = Z T Zᴴ and f at T's diagonal (values), as scipy....
The circles of Cauchy's integral about the clusters of the reordered Schur form t (each a run of its ...
std::vector< std::size_t > starts
Each run's first place, then n.
std::vector< std::complex< double > > centres
Each run's eigenvalues' mean.
std::vector< double > radii
Each run's circle's radius; 0 for a single eigenvalue.
A Hermitian matrix A's eigenvectors V (hermitian_system) and Vᴴ A V: its Schur form Λ to the similari...
matrix< T > similar
Vᴴ A V.
Al-Mohy and Higham's θ_m (2011, table 3.1, double precision): the 1-norm of t A up to which m terms o...
The terms m and the steps s of expm_multiply.
Where funm wants f, and the forms it completes: a Hermitian A's eigendecomposition (t Λ,...
std::vector< std::complex< double > > points
Where f is wanted.
double share
The clusters' bound's share (detail::cluster_bound).
bool hermitian
Whether A was Hermitian, T then Λ.
std::vector< std::size_t > counts
The points on each circle, in the circles' order.
matrix< std::complex< double > > t
T (Λ, for a Hermitian A).
matrix< std::complex< double > > z
Z (V).
A function of a square matrix from its complex Schur form, as scipy.linalg.funm forms it: f(A) and th...
matrix< std::complex< double > > f
f(A), complex (SciPy's real part where A is real and it is negligible).
std::vector< double > contours
Each circle's integral's own estimate (half its points against all).
double error
‖err‖₁ / ‖A‖₁ estimated: Parlett's recurrence run again on its errors (detail::recurrence_error),...
The principal logarithm of a square matrix with what SciPy warns of: log A (complex),...
matrix< std::complex< double > > log
log A.