NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
matrix_functions.hpp
Go to the documentation of this file.
1
7#ifndef NUMERICAL_MATRIX_FUNCTIONS_HPP
8#define NUMERICAL_MATRIX_FUNCTIONS_HPP
9
10#include <algorithm>
11#include <array>
12#include <cmath>
13#include <complex>
14#include <concepts>
15#include <cstddef>
16#include <functional>
17#include <limits>
18#include <numeric>
19#include <numbers>
20#include <optional>
21#include <stdexcept>
22#include <string>
23#include <tuple>
24#include <utility>
25#include <vector>
26
27#include "complex_math.hpp"
28#include "eigen.hpp"
29
30namespace numerical {
31
32 namespace detail {
33
36 {
37 buffer<double> moduli(a.size());
38 std::transform(a.begin(), a.end(), moduli.begin(), [](double x) { return std::abs(x); });
39 return moduli;
40 }
41
47 [[nodiscard]] inline buffer<double> entry_moduli(const buffer<std::complex<double>>& a)
48 {
49 double largest {0.0};
50 for (const std::complex<double>& z : a) {
51 largest = std::max({largest, std::abs(z.real()), std::abs(z.imag())});
52 }
53 buffer<double> moduli(a.size());
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()));
58 });
59 }
60 else {
61 std::transform(a.begin(), a.end(), moduli.begin(), [](const std::complex<double>& z) { return std::abs(z); });
62 }
63 return moduli;
64 }
65
69 std::size_t n)
70 {
71 buffer<double> sums(n, 0.0);
72 for (std::size_t i {0}; i < n; ++i) {
73 for (std::size_t j {0}; j < n; ++j) {
74 sums[j] += moduli[(i * n) + j];
75 }
76 }
77 return *std::max_element(sums.begin(), sums.end());
78 }
79
81 template <typename T>
82 [[nodiscard]] double one_norm(const buffer<T>& a,
83 std::size_t n)
84 {
85 return column_sum_norm(entry_moduli(a), n);
86 }
87
91 std::size_t n,
92 std::size_t p,
93 double scale)
94 {
95 buffer<double> row(n, 1.0);
96 buffer<double> next(n, 0.0);
97 for (std::size_t step {0}; step < p; ++step) {
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;
102 }
103 }
104 std::swap(row, next);
105 }
106 return *std::max_element(row.begin(), row.end());
107 }
108
112 template <typename T>
114 const buffer<T>& b,
115 std::size_t n,
116 buffer<T>& c)
117 {
118 c.resize(n * n);
119 gemm(n, n, n, a.data(), n, b.data(), n, c.data(), n, c_start::zero);
120 }
121
123 template <typename T>
125 const buffer<T>& b,
126 std::size_t n)
127 {
128 buffer<T> c;
129 square_product_into(a, b, n, c);
130 return c;
131 }
132
135 template <typename T>
138 std::size_t n)
139 {
140 square_product_into(x, x, n, spare);
141 std::swap(x, spare);
142 }
143
145 [[nodiscard]] inline const double* pade_coefficients(std::size_t m)
146 {
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,
155 182.0, 1.0};
156 switch (m) {
157 case 3: return three.data();
158 case 5: return five.data();
159 case 7: return seven.data();
160 case 9: return nine.data();
161 default: return thirteen.data();
162 }
163 }
164
171 [[nodiscard]] inline std::size_t extra_squarings(const buffer<double>& moduli,
172 std::size_t n,
173 std::size_t m,
174 double scale,
175 double norm)
176 {
177 const auto order {static_cast<double>(m)}; // c = (m!)² / ((2m)! (2m + 1)!), by the logarithms of the factorials
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))};
179 const double scaled_norm {norm * scale};
180 if (scaled_norm == 0.0) {
181 return 0;
182 }
183 const double alpha {c * modulus_power_norm(moduli, n, (2 * m) + 1, scale) / scaled_norm};
184 const double unit {std::ldexp(1.0, -53)};
185 if (alpha <= unit) {
186 return 0;
187 }
188 return static_cast<std::size_t>(std::ceil(std::log2(alpha / unit) / static_cast<double>(2 * m)));
189 }
190
196 template <typename T>
198 const std::array<const buffer<T>*, 4>& powers,
199 std::size_t n,
200 std::size_t m)
201 {
202 const double* const b {pade_coefficients(m)};
203 buffer<T> odd; // the sum U is A times
204 buffer<T> even; // V
205 buffer<T> spare; // a buffer free for U, where one is
206 const auto add = [&](buffer<T>& into, const buffer<T>& power, double coefficient) {
207 for (std::size_t e {0}; e < n * n; ++e) {
208 into[e] += T {coefficient} *power[e];
209 }
210 };
211 if (m == 13) {
212 const buffer<T>& a2 {*powers[0]};
213 const buffer<T>& a4 {*powers[1]};
214 const buffer<T>& a6 {*powers[2]};
215 buffer<T> high_odd(n * n, T {});
216 buffer<T> high_even(n * n, T {});
217 add(high_odd, a6, b[13]);
218 add(high_odd, a4, b[11]);
219 add(high_odd, a2, b[9]);
220 add(high_even, a6, b[12]);
221 add(high_even, a4, b[10]);
222 add(high_even, a2, b[8]);
224 square_product_into(a6, high_even, n, high_odd); // V's sum where U's high terms were
225 even = std::move(high_odd);
226 spare = std::move(high_even); // U's storage, below
227 add(odd, a6, b[7]);
228 add(odd, a4, b[5]);
229 add(odd, a2, b[3]);
230 add(even, a6, b[6]);
231 add(even, a4, b[4]);
232 add(even, a2, b[2]);
233 }
234 else {
235 odd.assign(n * n, T {});
236 even.assign(n * n, T {});
237 for (std::size_t k {2}; k < m; k += 2) { // b_{k+1} A^k into U's sum, b_k A^k into V
238 add(odd, *powers[(k / 2) - 1], b[k + 1]);
239 add(even, *powers[(k / 2) - 1], b[k]);
240 }
241 }
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]};
245 }
246 buffer<T> u {std::move(spare)};
247 square_product_into(a, odd, n, u);
248 odd = buffer<T> {}; // its block kept for the next buffer (the squarings')
249 for (std::size_t e {0}; e < n * n; ++e) { // V + U where U was, V − U where V was
250 const T v {even[e]};
251 even[e] = v - u[e];
252 u[e] = v + u[e];
253 }
254 const lu_decomposition<T> lu {matrix<T> {n, n, std::move(even)}};
255 return lu.solve(matrix<T> {n, n, std::move(u)}).elements();
256 }
257
259 template <typename T>
260 [[nodiscard]] T sinch(const T& x)
261 {
262 if (std::abs(x) < 1e-4) {
263 const T square {x * x};
264 return T {1.0} + (square / T {6.0}) * (T {1.0} + (square / T {20.0}));
265 }
266 return std::sinh(x) / x;
267 }
268
272 inline constexpr double divided_exponentials_past {64.0};
273
281 template <typename T>
283 const buffer<T>& t,
284 std::size_t n,
285 double scale)
286 {
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);
290 if (i + 1 < n) {
291 const T next {T {scale} *t[((i + 1) * n) + i + 1]};
292 const T half_sum {(lambda + next) / T {2.0}};
293 const T half_gap {(lambda - next) / T {2.0}};
294 if (std::abs(half_gap) > divided_exponentials_past) {
295 const T gap {lambda - next};
296 T quotient {(std::exp(lambda) - std::exp(next)) / gap};
297 if (!is_finite_entry(quotient)) { // each exponential divided by the gap's modulus first, then by its phase
298 const double length {static_cast<double>(std::abs(gap))};
299 const T log_of {std::log(length)};
300 quotient = (std::exp(lambda - log_of) - std::exp(next - log_of)) / (gap / T {length});
301 }
302 x[(i * n) + i + 1] = T {scale} *t[(i * n) + i + 1] * quotient;
303 }
304 else {
305 x[(i * n) + i + 1] = T {scale} *t[(i * n) + i + 1] * std::exp(half_sum) * sinch(half_gap);
306 }
307 }
308 }
309 }
310
313 template <typename T>
315 {
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))) {
319 return false;
320 }
321 for (std::size_t j {0}; j < i; ++j) {
322 if (a(i, j) != conj_of(a(j, i))) {
323 return false;
324 }
325 }
326 }
327 return true;
328 }
329
331 [[nodiscard]] inline std::pair<vector<double>, matrix<double>> hermitian_system(const matrix<double>& a)
332 {
333 symmetric_eigen e {a};
334 vector<double> values {e.values()};
335 return {std::move(values), std::move(e).vectors()};
336 }
337
339 [[nodiscard]] inline std::pair<vector<double>, matrix<std::complex<double>>> hermitian_system(const matrix<std::complex<double>>& a)
340 {
341 hermitian_eigen e {a};
342 vector<double> values {e.values()};
343 return {std::move(values), std::move(e).vectors()};
344 }
345
350 template <typename R, typename T>
352 const std::vector<R>& f,
353 bool hermitian)
354 {
355 const std::size_t n {v.rows()};
356 buffer<R> scaled(n * n);
357 buffer<R> adjoint(n * n);
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];
361 adjoint[(k * n) + i] = conj_of(R {v(i, k)});
362 }
363 }
364 matrix<R> x {matrix<R> {n, n, std::move(scaled)} *matrix<R> {n, n, std::move(adjoint)}};
365 if (!hermitian) {
366 return x;
367 }
368 buffer<R> out(n * n);
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;
372 }
373 }
374 return matrix<R> {n, n, std::move(out)};
375 }
376 } // namespace detail
377
380 inline constexpr std::size_t hermitian_expm_least {64};
381
393 template <typename T>
394 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
395 [[nodiscard]] matrix<T> expm(const matrix<T>& a)
396 {
397 const std::size_t n {a.rows()};
398 if (a.cols() != n) {
399 throw dimension_error("expm requires a square matrix");
400 }
401 detail::require_finite(a, "expm");
402 if (n == 0) {
403 return matrix<T> {0, 0, buffer<T> {}};
404 }
405 if (n >= hermitian_expm_least && detail::exactly_hermitian(a)) { // one eigendecomposition: below, the Padé path is faster
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])};
410 }
411 return detail::spectral<T>(vectors, powers, true);
412 }
413 buffer<T> a0(a.begin(), a.end());
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 {};
418 }
419 }
420 buffer<double> moduli {detail::entry_moduli(a0)};
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};
430 const auto finish = [&](buffer<T> x) { return matrix<T> {n, n, std::move(x)}; };
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));
434 }
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));
437 }
438 buffer<T> a8 {detail::square_product(a4, a4, n)};
439 powers[3] = &a8;
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));
444 }
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));
447 }
448 // η₅ = min(η₃, max(d₈, d₁₀)) is η₃ where η₃ ≤ θ₁₃ (s = 0 whatever d₁₀) or d₈ ≥ η₃: A¹⁰ formed only otherwise
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);
453 // Each buffer freed once read for the last time: its block kept for the next of its size, in this call
454 moduli = buffer<double> {};
455 a8 = buffer<T> {};
456 const int power {static_cast<int>(s)};
457 const buffer<T> bands {triangular ? a0 : buffer<T> {}}; // a triangle's exact bands read A after
458 buffer<T> scaled {std::move(a0)};
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)};
464 }
465 buffer<T> x {detail::pade_approximant(scaled, powers, n, 13)};
466 if (triangular) {
467 detail::exact_triangular_bands(x, bands, n, std::ldexp(1.0, -power));
468 }
469 buffer<T> spare;
470 for (int j {power - 1}; j >= 0; --j) {
471 detail::square_in_place(x, spare, n);
472 if (triangular) {
473 detail::exact_triangular_bands(x, bands, n, std::ldexp(1.0, -j));
474 }
475 }
476 return finish(std::move(x));
477 }
478
479 namespace detail {
480
485 {
486 std::size_t m;
487 double theta;
488 };
489
491 inline constexpr std::array<taylor_bound, 35> taylor_bounds {{{1, 2.29e-16},
492 {2, 2.58e-8},
493 {3, 1.39e-5},
494 {4, 3.40e-4},
495 {5, 2.40e-3},
496 {6, 9.07e-3},
497 {7, 2.38e-2},
498 {8, 5.00e-2},
499 {9, 8.96e-2},
500 {10, 1.44e-1},
501 {11, 2.14e-1},
502 {12, 3.00e-1},
503 {13, 4.00e-1},
504 {14, 5.14e-1},
505 {15, 6.41e-1},
506 {16, 7.81e-1},
507 {17, 9.31e-1},
508 {18, 1.09},
509 {19, 1.26},
510 {20, 1.44},
511 {21, 1.62},
512 {22, 1.82},
513 {23, 2.01},
514 {24, 2.22},
515 {25, 2.43},
516 {26, 2.64},
517 {27, 2.86},
518 {28, 3.08},
519 {29, 3.31},
520 {30, 3.54},
521 {35, 4.7},
522 {40, 6.0},
523 {45, 7.2},
524 {50, 8.5},
525 {55, 9.9}}};
526
529 {
530 std::size_t terms;
531 std::size_t steps;
532 };
533
541 [[nodiscard]] inline taylor_plan plan_taylor(double norm,
542 std::size_t columns,
543 const std::function<double(std::size_t)>& power_norm)
544 {
545 constexpr std::size_t most_terms {55};
546 constexpr std::size_t most_power {8}; // the largest p with p (p − 1) ≤ m_max + 1
547 constexpr double ell {2.0};
548 taylor_plan best {0, 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) {
552 best = {m, s};
553 }
554 };
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) {
558 for (const taylor_bound& bound : taylor_bounds) {
559 consider(bound.m, norm / bound.theta);
560 }
561 return best;
562 }
563 std::vector<double> d(most_power + 2, 0.0); // d[p], estimated once each
564 const auto alpha = [&](std::size_t p) {
565 for (const std::size_t q : {p, p + 1}) {
566 if (d[q] == 0.0) {
567 d[q] = power_norm(q);
568 }
569 }
570 return std::max(d[p], d[p + 1]);
571 };
572 for (std::size_t p {2}; p <= most_power; ++p) {
573 for (const taylor_bound& bound : taylor_bounds) {
574 if (bound.m + 1 >= p * (p - 1)) {
575 consider(bound.m, alpha(p) / bound.theta);
576 }
577 }
578 }
579 best.steps = std::max<std::size_t>(best.steps, 1);
580 return best;
581 }
582
584 template <typename T>
585 [[nodiscard]] double row_sum_norm(const buffer<T>& x,
586 std::size_t n,
587 std::size_t k)
588 {
589 double largest {0.0};
590 for (std::size_t i {0}; i < n; ++i) {
591 double sum {0.0};
592 for (std::size_t j {0}; j < k; ++j) {
593 sum += std::abs(x[(i * k) + j]);
594 }
595 largest = std::max(largest, sum);
596 }
597 return largest;
598 }
599 } // namespace detail
600
616 template <typename T>
617 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
618 [[nodiscard]] matrix<T> expm_multiply(const matrix<T>& a,
619 const matrix<T>& b,
620 double t = 1.0)
621 {
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");
625 }
626 detail::require_finite(a, "expm_multiply");
627 detail::require_finite(b, "expm_multiply");
628 if (!std::isfinite(t)) {
629 throw non_finite_error("expm_multiply: the time is infinite or NaN");
630 }
631 const std::size_t k {b.cols()};
632 buffer<T> shifted(a.begin(), a.end());
633 T trace {};
634 for (std::size_t i {0}; i < n; ++i) {
635 trace += shifted[(i * n) + i];
636 }
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;
640 }
641 const double norm {n == 0 ? 0.0 : std::abs(t) * detail::one_norm(shifted, n)}; // ‖tA‖₁
642 detail::taylor_plan plan {0, 1};
643 if (norm != 0.0 && k != 0) {
644 buffer<T> adjoint(n * n); // Aᴴ, for the estimates' products with Aᴴ
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]);
648 }
649 }
650 const double scale {std::abs(t)};
651 plan = detail::plan_taylor(norm, k, [&](std::size_t p) { // ‖(tA)ᵖ‖₁^{1/p}, estimated
652 buffer<T> product(n);
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);
657 }
658 })};
659 return scale * std::pow(estimate, 1.0 / static_cast<double>(p));
660 });
661 }
662 constexpr double tol {0x1.0p-53};
663 buffer<T> f(b.begin(), b.end());
664 buffer<T> term(b.begin(), b.end());
665 buffer<T> next(n * k);
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) {
670 if (k == 1) { // the matrix–vector kernel: a one-column product's tiles take twice its time
671 detail::matrix_times_vector(shifted.data(), n, n, n, term.data(), next.data());
672 }
673 else {
674 gemm(n, k, n, shifted.data(), n, term.data(), k, next.data(), k, detail::c_start::zero);
675 }
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];
679 f[e] += term[e];
680 }
681 const double c2 {detail::row_sum_norm(term, n, k)};
682 if (c1 + c2 <= tol * detail::row_sum_norm(f, n, k)) {
683 break;
684 }
685 c1 = c2;
686 }
687 for (T& value : f) {
688 value *= eta;
689 }
690 term = f;
691 }
692 return matrix<T> {n, k, std::move(f)};
693 }
694
695 namespace detail {
696
698 template <typename T>
699 [[nodiscard]] matrix<T> adjoint_of(const matrix<T>& m)
700 {
701 buffer<T> out(m.rows() * m.cols());
702 for (std::size_t i {0}; i < m.rows(); ++i) {
703 for (std::size_t j {0}; j < m.cols(); ++j) {
704 out[(j * m.rows()) + i] = conj_of(m(i, j));
705 }
706 }
707 return matrix<T> {m.cols(), m.rows(), std::move(out)};
708 }
709
712 [[nodiscard]] inline std::size_t schur_block(const buffer<double>& t,
713 std::size_t n,
714 std::size_t k)
715 {
716 return k + 1 < n && t[((k + 1) * n) + k] != 0.0 ? 2 : 1;
717 }
718
720 [[nodiscard]] inline std::size_t schur_block(const buffer<std::complex<double>>& /*t*/,
721 std::size_t /*n*/,
722 std::size_t /*k*/)
723 {
724 return 1;
725 }
726
733 template <typename T>
734 void small_sylvester_block(const T* r,
735 std::size_t ldr,
736 const T* s,
737 std::size_t lds,
738 std::size_t rows,
739 std::size_t cols,
740 T* c,
741 std::size_t ldc,
742 double smin)
743 {
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}; // the unknown in each column after the column swaps
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];
754 }
755 for (std::size_t q {0}; q < cols; ++q) {
756 k[e][(i * cols) + q] += s[(q * lds) + j];
757 }
758 }
759 }
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]);
768 pivot_row = i;
769 pivot_col = j;
770 }
771 }
772 }
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]);
777 }
778 std::swap(order[step], order[pivot_col]);
779 if (std::abs(k[step][step]) < smin) {
780 k[step][step] = T {smin};
781 }
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];
786 }
787 rhs[i] -= factor * rhs[step];
788 }
789 }
790 std::array<T, 4> y {};
791 for (std::size_t back {size}; back > 0; --back) {
792 const std::size_t i {back - 1};
793 T value {rhs[i]};
794 for (std::size_t j {i + 1}; j < size; ++j) {
795 value -= k[i][j] * y[j];
796 }
797 y[i] = value / k[i][i];
798 }
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];
802 }
803 }
804
812 template <typename T>
814 std::size_t m,
815 const buffer<T>& s,
816 std::size_t n,
817 buffer<T>& f)
818 {
819 double largest {0.0};
820 for (const T& entry : r) {
821 largest = std::max(largest, std::abs(entry));
822 }
823 for (const T& entry : s) {
824 largest = std::max(largest, std::abs(entry));
825 }
826 const double smin {std::max(std::numeric_limits<double>::epsilon() * largest, std::numeric_limits<double>::min())};
827 buffer<T> minus_s;
828 buffer<T> columns; // Y's columns of the block, each contiguous
829 for (std::size_t l {0}; l < n;) {
830 const std::size_t nl {schur_block(s, n, l)};
831 if (l > 0) { // F(:, l…) −= Y(:, 0…l) S(0…l, l…)
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];
836 }
837 }
838 gemm(m, nl, l, f.data(), n, minus_s.data(), nl, f.data() + l, n);
839 }
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) { // F(k, l) −= R(k, end…m) Y(end…m, l)
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);
847 }
848 }
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];
853 }
854 }
855 end = k0;
856 }
857 l += nl;
858 }
859 }
860 } // namespace detail
861
874 template <typename T>
875 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
876 [[nodiscard]] matrix<T> solve_sylvester(const matrix<T>& a,
877 const matrix<T>& b,
878 const matrix<T>& q)
879 {
880 const std::size_t m {a.rows()};
881 const std::size_t n {b.rows()};
882 if (a.cols() != m || b.cols() != n || q.rows() != m || q.cols() != n) {
883 throw dimension_error("solve_sylvester requires a square a (m × m), a square b (n × n) and q (m × n)");
884 }
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) {
889 return matrix<T> {m, n, buffer<T>(m * n, T {})};
890 }
891 const schur_decomposition<T> left {a};
892 const schur_decomposition<T> right {b};
893 const matrix<T>& u {left.z()};
894 const matrix<T>& v {right.z()};
895 matrix<T> f {detail::adjoint_of(u) * q * v};
896 buffer<T> y {std::move(f).elements()};
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);
899 }
900
913 template <typename T>
914 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
916 const matrix<T>& q)
917 {
918 const std::size_t n {a.rows()};
919 if (a.cols() != n || q.rows() != n || q.cols() != n) {
920 throw dimension_error("solve_continuous_lyapunov requires a square a and q of its shape");
921 }
922 detail::require_finite(a, "solve_continuous_lyapunov");
923 detail::require_finite(q, "solve_continuous_lyapunov");
924 if (n == 0) {
925 return matrix<T> {0, 0, buffer<T> {}};
926 }
927 const schur_decomposition<T> form {a};
928 const matrix<T>& u {form.z()};
929 const matrix<T>& r {form.t()};
930 const matrix<T> f {detail::adjoint_of(u) * q * u};
931 buffer<T> y(n * n); // (Uᴴ Q U) J, then Y J
932 buffer<T> reversed(n * n); // J Rᴴ J
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));
937 }
938 }
939 detail::triangular_sylvester(buffer<T>(r.begin(), r.end()), n, reversed, n, y);
940 buffer<T> x(n * n);
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];
944 }
945 }
946 return u * matrix<T> {n, n, std::move(x)} *detail::adjoint_of(u);
947 }
948
949 namespace detail {
950
953 [[nodiscard]] inline double frechet_bound(std::size_t m)
954 {
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};
957 return table[m];
958 }
959
961 template <typename T>
963 const buffer<T>& term,
964 double coefficient)
965 {
966 for (std::size_t e {0}; e < into.size(); ++e) {
967 into[e] += T {coefficient} *term[e];
968 }
969 }
970
972 template <typename T>
973 [[nodiscard]] buffer<T> both_products(const buffer<T>& p,
974 const buffer<T>& q,
975 std::size_t n)
976 {
977 buffer<T> sum {square_product(p, q, n)};
978 const buffer<T> other {square_product(q, p, n)};
979 for (std::size_t e {0}; e < sum.size(); ++e) {
980 sum[e] += other[e];
981 }
982 return sum;
983 }
984
992 template <typename T>
993 [[nodiscard]] std::pair<buffer<T>, buffer<T>> frechet_pade(const buffer<T>& a,
994 const buffer<T>& e,
995 std::size_t n,
996 std::size_t m)
997 {
998 const double* const b {pade_coefficients(m)};
999 buffer<T> identity(n * n, T {});
1000 for (std::size_t i {0}; i < n; ++i) {
1001 identity[(i * n) + i] = T {1.0};
1002 }
1003 const buffer<T> a2 {square_product(a, a, n)};
1004 const buffer<T> m2 {both_products(a, e, n)};
1005 const buffer<T> a4 {square_product(a2, a2, n)};
1006 const buffer<T> m4 {both_products(a2, m2, n)};
1007 const buffer<T> a6 {square_product(a2, a4, n)};
1008 buffer<T> m6 {square_product(a4, m2, n)};
1009 add_scaled(m6, square_product(m4, a2, n), 1.0);
1010 buffer<T> w(n * n, T {}); // U = A W
1011 buffer<T> v(n * n, T {});
1012 buffer<T> lw(n * n, T {}); // Lu = A Lw + E W
1013 buffer<T> lv(n * n, T {});
1014 if (m == 13) {
1015 buffer<T> w1(n * n, T {});
1016 buffer<T> z1(n * n, T {});
1017 buffer<T> lw1(n * n, T {});
1018 buffer<T> lz1(n * n, T {});
1019 add_scaled(w1, a6, b[13]);
1020 add_scaled(w1, a4, b[11]);
1021 add_scaled(w1, a2, b[9]);
1022 add_scaled(z1, a6, b[12]);
1023 add_scaled(z1, a4, b[10]);
1024 add_scaled(z1, a2, b[8]);
1025 add_scaled(lw1, m6, b[13]);
1026 add_scaled(lw1, m4, b[11]);
1027 add_scaled(lw1, m2, b[9]);
1028 add_scaled(lz1, m6, b[12]);
1029 add_scaled(lz1, m4, b[10]);
1030 add_scaled(lz1, m2, b[8]);
1031 w = square_product(a6, w1, n);
1032 v = square_product(a6, z1, n);
1033 lw = square_product(a6, lw1, n);
1034 add_scaled(lw, square_product(m6, w1, n), 1.0);
1035 add_scaled(lv, square_product(a6, lz1, n), 1.0);
1036 add_scaled(lv, square_product(m6, z1, n), 1.0);
1037 const auto lower_terms = [&](const buffer<T>& power, const buffer<T>& derivative, std::size_t k) { // W₂, Z₂, Lw₂, Lz₂
1038 add_scaled(w, power, b[k + 1]);
1039 add_scaled(v, power, b[k]);
1040 add_scaled(lw, derivative, b[k + 1]);
1041 add_scaled(lv, derivative, b[k]);
1042 };
1043 lower_terms(a6, m6, 6);
1044 lower_terms(a4, m4, 4);
1045 lower_terms(a2, m2, 2);
1046 }
1047 else {
1048 const buffer<T> a8 {square_product(a4, a4, n)};
1049 const buffer<T> m8 {both_products(a4, m4, n)};
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) { // b_{k+1} A^k into W, b_k A^k into V, from the highest
1053 add_scaled(w, *powers[(k / 2) - 1], b[k + 1]);
1054 add_scaled(v, *powers[(k / 2) - 1], b[k]);
1055 add_scaled(lw, *derivatives[(k / 2) - 1], b[k + 1]);
1056 add_scaled(lv, *derivatives[(k / 2) - 1], b[k]);
1057 }
1058 }
1059 add_scaled(w, identity, b[1]);
1060 add_scaled(v, identity, b[0]);
1061 const buffer<T> u {square_product(a, w, n)};
1062 buffer<T> lu {square_product(a, lw, n)};
1063 add_scaled(lu, square_product(e, w, n), 1.0);
1064 buffer<T> numerator(n * n);
1065 buffer<T> denominator(n * n);
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];
1069 }
1070 const lu_decomposition<T> factor {matrix<T> {n, n, std::move(denominator)}};
1071 buffer<T> r {factor.solve(matrix<T> {n, n, std::move(numerator)}).elements()};
1072 buffer<T> difference(n * n);
1073 for (std::size_t k {0}; k < n * n; ++k) {
1074 difference[k] = lu[k] - lv[k];
1075 }
1076 buffer<T> derivative_terms {square_product(difference, r, n)};
1077 for (std::size_t k {0}; k < n * n; ++k) {
1078 derivative_terms[k] = lu[k] + lv[k] + derivative_terms[k];
1079 }
1080 buffer<T> l {factor.solve(matrix<T> {n, n, std::move(derivative_terms)}).elements()};
1081 return {std::move(r), std::move(l)};
1082 }
1083 } // namespace detail
1084
1088 {
1091 };
1092
1104 template <typename T>
1105 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
1106 [[nodiscard]] std::pair<matrix<T>, matrix<T>> expm_frechet(const matrix<T>& a,
1107 const matrix<T>& e,
1108 frechet_method method = frechet_method::scaling_pade_squaring)
1109 {
1110 const std::size_t n {a.rows()};
1111 if (a.cols() != n || e.rows() != n || e.cols() != n) {
1112 throw dimension_error("expm_frechet requires square matrices a and e of one order");
1113 }
1114 detail::require_finite(a, "expm_frechet");
1115 detail::require_finite(e, "expm_frechet");
1116 if (n == 0) {
1117 return {matrix<T> {0, 0, buffer<T> {}}, matrix<T> {0, 0, buffer<T> {}}};
1118 }
1119 if (method == frechet_method::block_enlarge) {
1120 buffer<T> block(4 * n * n, T {});
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);
1126 }
1127 }
1128 const matrix<T> x {expm(matrix<T> {2 * n, 2 * n, std::move(block)})};
1129 buffer<T> top(n * n);
1130 buffer<T> right(n * n);
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);
1135 }
1136 }
1137 return {matrix<T> {n, n, std::move(top)}, matrix<T> {n, n, std::move(right)}};
1138 }
1139 buffer<T> a0(a.begin(), a.end());
1140 buffer<T> e0(e.begin(), e.end());
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)};
1145 return {matrix<T> {n, n, std::move(r)}, matrix<T> {n, n, std::move(l)}};
1146 }
1147 }
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)};
1152 }
1153 auto [r, l] {detail::frechet_pade(a0, e0, n, 13)};
1154 buffer<T> spare;
1155 for (int k {0}; k < s; ++k) {
1156 l = detail::both_products(r, l, n);
1157 detail::square_in_place(r, spare, n);
1158 }
1159 return {matrix<T> {n, n, std::move(r)}, matrix<T> {n, n, std::move(l)}};
1160 }
1161
1170 template <typename T>
1171 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
1172 [[nodiscard]] double expm_cond(const matrix<T>& a)
1173 {
1174 const std::size_t n {a.rows()};
1175 if (a.cols() != n) {
1176 throw dimension_error("expm_cond requires a square matrix");
1177 }
1178 detail::require_finite(a, "expm_cond");
1179 if (n == 0) { // no direction to perturb along
1180 return 0.0;
1181 }
1182 const std::size_t columns {n * n};
1183 buffer<T> k(columns * columns);
1184 for (std::size_t i {0}; i < n; ++i) {
1185 for (std::size_t j {0}; j < n; ++j) {
1186 buffer<T> unit(columns, T {});
1187 unit[(i * n) + j] = T {1.0};
1188 const matrix<T> l {expm_frechet(a, matrix<T> {n, n, std::move(unit)}).second};
1189 for (std::size_t q {0}; q < n; ++q) { // vec, column-major: entry (p, q) at q n + p
1190 for (std::size_t p {0}; p < n; ++p) {
1191 k[(((q * n) + p) * columns) + (i * n) + j] = l(p, q);
1192 }
1193 }
1194 }
1195 }
1196 const auto frobenius = [](const matrix<T>& m) {
1197 double sum {0.0};
1198 for (const T& x : m) {
1199 sum += std::norm(x);
1200 }
1201 return std::sqrt(sum);
1202 };
1203 const double kronecker {singular_values(matrix<T> {columns, columns, std::move(k)})[0]};
1204 return kronecker * frobenius(a) / frobenius(expm(a));
1205 }
1206
1207 namespace detail {
1208
1217 template <typename T>
1219 buffer<T>& r,
1220 std::size_t n,
1221 const std::vector<std::size_t>& starts)
1222 {
1223 const std::size_t blocks {starts.size()};
1224 buffer<T> columns(2 * n); // the block column's entries above its diagonal block, by column: contiguous
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) { // the blocks above, the nearest first
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];
1240 }
1241 c[(i * nj) + j] = value;
1242 }
1243 }
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;
1247 }
1248 else {
1249 small_sylvester_block(r.data() + (i0 * n) + i0, n, r.data() + (j0 * n) + j0, n, ni, nj, c.data(), nj, 0.0);
1250 }
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];
1255 }
1256 }
1257 }
1258 }
1259 }
1260
1266 [[nodiscard]] inline std::optional<matrix<double>> real_square_root(const matrix<double>& form,
1267 const matrix<double>* z)
1268 {
1269 const std::size_t n {form.rows()};
1270 const buffer<double> t(form.begin(), form.end());
1271 buffer<double> r(n * n, 0.0);
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);
1275 if (schur_block(t, n, k) == 1) {
1276 if (t[(k * n) + k] < 0.0) {
1277 return std::nullopt;
1278 }
1279 r[(k * n) + k] = std::sqrt(t[(k * n) + k]);
1280 continue;
1281 }
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);
1289 }
1290 square_root_columns(t, r, n, starts);
1291 const matrix<double> root {n, n, std::move(r)};
1292 return z == nullptr ? root : *z * root * transpose(*z);
1293 }
1294
1296 [[nodiscard]] inline double scalar_sqrt(double x)
1297 {
1298 return std::sqrt(x);
1299 }
1300
1302 [[nodiscard]] inline std::complex<double> scalar_sqrt(const std::complex<double>& z)
1303 {
1304 return complex_sqrt(z);
1305 }
1306
1309 template <typename T>
1311 std::size_t n)
1312 {
1313 buffer<T> r(n * n, T {});
1314 std::vector<std::size_t> starts(n);
1315 for (std::size_t k {0}; k < n; ++k) {
1316 starts[k] = k;
1317 r[(k * n) + k] = scalar_sqrt(t[(k * n) + k]);
1318 }
1319 square_root_columns(t, r, n, starts);
1320 return r;
1321 }
1322
1324 inline constexpr std::size_t square_root_block {64};
1325
1334 template <typename T>
1336 std::size_t n)
1337 {
1338 bool singular {false};
1339 for (std::size_t k {0}; k < n; ++k) {
1340 singular = singular || t[(k * n) + k] == T {};
1341 }
1342 if (n <= square_root_block || singular) {
1343 return pointwise_square_root(t, n);
1344 }
1345 const std::size_t blocks {(n + square_root_block - 1) / square_root_block};
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); // R_bb, contiguous
1348 buffer<T> r(n * n, T {});
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};
1352 buffer<T> block(nb * nb);
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));
1355 }
1356 roots[b] = pointwise_square_root(block, 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);
1359 }
1360 }
1361 buffer<T> f;
1362 buffer<T> product;
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};
1369 f.resize(ni * nj);
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];
1375 }
1376 }
1377 triangular_sylvester(roots[bi - 1], ni, roots[bj], nj, f);
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);
1380 }
1381 }
1382 }
1383 return r;
1384 }
1385
1387 [[nodiscard]] inline matrix<std::complex<double>> complex_square_root(const matrix<std::complex<double>>& form,
1388 const matrix<std::complex<double>>* z)
1389 {
1390 const std::size_t n {form.rows()};
1391 const buffer<std::complex<double>> t(form.begin(), form.end());
1393 return z == nullptr ? root : *z * root * adjoint_of(*z);
1394 }
1395
1401 [[nodiscard]] inline std::pair<matrix<std::complex<double>>, matrix<std::complex<double>>> complex_schur_form(const matrix<double>& t,
1402 const matrix<double>& z)
1403 {
1404 using C = std::complex<double>;
1405 const std::size_t n {t.rows()};
1406 buffer<C> tc(n * n);
1407 buffer<C> zc(n * n);
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)]};
1411 }
1412 for (std::size_t k {n}; k > 1; --k) { // the rows m = k − 1 from the last to the second
1413 const std::size_t m {k - 1};
1414 const C below {tc[(m * n) + m - 1]};
1415 if (below == C {}) {
1416 continue;
1417 }
1418 // the block scaled by a power of two near its largest entry: b·c can neither overflow (an entry past √DBL_MAX)
1419 // nor vanish, and the rotation, a ratio, is unchanged (a power of two rounds nothing)
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]),
1421 std::abs(below)})};
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};
1427 // the first eigenvalue of the block less its last diagonal entry, as rsf2csf's mu[0]
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))};
1431 const C c {mu / r};
1432 const C sn {c_s / r};
1433 for (std::size_t j {m - 1}; j < n; ++j) { // G = [c̄ s; −s c] on rows m − 1 and m
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);
1438 }
1439 for (std::size_t i {0}; i <= m; ++i) { // · Gᴴ on columns m − 1 and m
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);
1444 }
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);
1450 }
1451 tc[(m * n) + m - 1] = C {};
1452 }
1453 return {matrix<C> {n, n, std::move(tc)}, matrix<C> {n, n, std::move(zc)}};
1454 }
1455
1458 template <typename T>
1459 [[nodiscard]] bool upper_triangular(const matrix<T>& a)
1460 {
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 {}) {
1464 return false;
1465 }
1466 }
1467 }
1468 return true;
1469 }
1470 } // namespace detail
1471
1472 namespace detail {
1473
1475 template <typename T>
1477 {
1478 const auto [values, vectors] {hermitian_system(a)};
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]});
1482 }
1483 return spectral<std::complex<double>>(vectors, roots, std::all_of(values.begin(), values.end(), [](double v) { return v >= 0.0; }));
1484 }
1485 } // namespace detail
1486
1488 class no_real_root_error : public detail::tagged<std::domain_error>
1489 {
1490 public:
1491
1493 explicit no_real_root_error(const std::string& message)
1494 : tagged(message)
1495 {}
1496 };
1497
1507 [[nodiscard]] inline matrix<std::complex<double>> sqrtm(const matrix<std::complex<double>>& a)
1508 {
1509 if (a.rows() != a.cols()) {
1510 throw dimension_error("sqrtm requires a square matrix");
1511 }
1512 detail::require_finite(a, "sqrtm");
1513 if (detail::exactly_hermitian(a)) {
1514 return detail::hermitian_root(a);
1515 }
1516 if (detail::upper_triangular(a)) {
1517 return detail::complex_square_root(a, nullptr);
1518 }
1520 return detail::complex_square_root(s.t(), &s.z());
1521 }
1522
1532 {
1533 if (a.rows() != a.cols()) {
1534 throw dimension_error("sqrtm requires a square matrix");
1535 }
1536 detail::require_finite(a, "sqrtm");
1537 if (detail::exactly_hermitian(a)) {
1538 return detail::hermitian_root(a);
1539 }
1540 if (detail::upper_triangular(a)) {
1541 const matrix<std::complex<double>> form {detail::complex_schur_form(a, a).first};
1542 return detail::complex_square_root(form, nullptr);
1543 }
1544 const schur_decomposition<double> s {a};
1545 const auto [t, z] {detail::complex_schur_form(s.t(), s.z())};
1546 return detail::complex_square_root(t, &z);
1547 }
1548
1558 [[nodiscard]] inline matrix<double> sqrtm(const matrix<double>& a)
1559 {
1560 if (a.rows() != a.cols()) {
1561 throw dimension_error("sqrtm requires a square matrix");
1562 }
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");
1569 }
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]);
1573 }
1574 return detail::spectral<double>(vectors, roots, true);
1575 }
1576 if (detail::upper_triangular(a)) {
1577 root = detail::real_square_root(a, nullptr);
1578 }
1579 else {
1580 const schur_decomposition<double> s {a};
1581 root = detail::real_square_root(s.t(), &s.z());
1582 }
1583 if (!root) {
1584 throw no_real_root_error("sqrtm: a real eigenvalue below 0, whose principal square root is complex");
1585 }
1586 return std::move(*root);
1587 }
1588
1589 namespace detail {
1590
1593 [[nodiscard]] inline std::complex<double> rounding_direction(std::size_t place)
1594 {
1595 // the turn a Weyl sequence's fraction (the golden ratio's), well spread for consecutive places
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));
1598 }
1599
1602 inline constexpr std::size_t upper_block_product_least {64};
1603
1604 inline void solve_upper_blocks(const matrix<std::complex<double>>& t,
1605 const std::vector<std::size_t>& starts,
1606 buffer<std::complex<double>>& x,
1607 const std::complex<double>* sources)
1608 {
1609 using C = std::complex<double>;
1610 const std::size_t n {t.rows()};
1611 const std::size_t count {starts.size() - 1};
1612 buffer<C> form(n * n); // T by rows, for the products
1613 buffer<C> columns(n * n); // T by columns, and X: the small blocks' sums contiguous along both operands
1614 buffer<C> x_columns(n * n);
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];
1620 }
1621 }
1622 buffer<C> rhs;
1623 buffer<C> product;
1624 buffer<C> left;
1625 buffer<C> right;
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}; // X_ij still 0 among its terms
1634 rhs.resize(pi * pj);
1635 product.resize(pi * pj);
1636 if (pi * pj >= upper_block_product_least) {
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);
1639 }
1640 else {
1641 for (std::size_t i {0}; i < pi; ++i) {
1642 for (std::size_t j {0}; j < pj; ++j) {
1643 C forward {};
1644 C backward {};
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];
1652 }
1653 rhs[(i * pj) + j] = forward;
1654 product[(i * pj) + j] = backward;
1655 }
1656 }
1657 }
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;
1662 }
1663 }
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));
1668 }
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];
1672 }
1673 }
1674 triangular_sylvester(left, pi, right, pj, rhs);
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];
1679 }
1680 }
1681 }
1682 }
1683 }
1684
1698 [[nodiscard]] inline double recurrence_error(const matrix<std::complex<double>>& t,
1699 const std::vector<std::size_t>& starts,
1700 const buffer<std::complex<double>>& fx,
1701 buffer<std::complex<double>> error)
1702 {
1703 using C = std::complex<double>;
1704 const std::size_t n {t.rows()};
1705 buffer<double> t_moduli(n * n);
1706 buffer<double> f_moduli(n * n);
1707 double size {0.0};
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]));
1712 }
1713 buffer<double> moduli(n * n); // |F| |T| + |T| |F|: the products' moduli each entry above sums (both upper triangular)
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);
1716 buffer<C> sources(n * n, C {});
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);
1721 }
1722 }
1723 }
1724 solve_upper_blocks(t, starts, error, sources.data());
1725 double largest {0.0};
1726 for (const C& entry : error) {
1727 largest = std::max(largest, std::abs(entry));
1728 }
1729 return largest / std::max(size, std::numeric_limits<double>::min());
1730 }
1731
1734 [[nodiscard]] inline double parlett_estimate(const matrix<std::complex<double>>& t,
1735 double smallest)
1736 {
1737 const double tolerance {std::numeric_limits<double>::epsilon()};
1738 double upper {0.0}; // ‖strict upper triangle of T‖₁
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));
1743 }
1744 upper = std::max(upper, column);
1745 }
1746 return std::min(1.0, std::max(tolerance, (tolerance / (smallest == 0.0 ? tolerance : smallest)) * upper));
1747 }
1748 } // namespace detail
1749
1755 {
1757 double error {0.0};
1758 std::vector<double> contours;
1759 };
1760
1761 namespace detail {
1762
1764 [[nodiscard]] inline std::pair<matrix<std::complex<double>>, matrix<std::complex<double>>> function_schur_form(const matrix<double>& a)
1765 {
1766 const schur_decomposition<double> s {a};
1767 return complex_schur_form(s.t(), s.z());
1768 }
1769
1771 [[nodiscard]] inline std::pair<matrix<std::complex<double>>, matrix<std::complex<double>>> function_schur_form(const matrix<std::complex<double>>& a)
1772 {
1774 return {s.t(), s.z()};
1775 }
1776 } // namespace detail
1777
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);
1791
1792 namespace detail {
1795 [[nodiscard]] inline std::pair<funm_result, double> parlett_function(const matrix<std::complex<double>>& t,
1796 const matrix<std::complex<double>>& z,
1797 const std::vector<std::complex<double>>& values)
1798 {
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");
1803 }
1804 const double tolerance {std::numeric_limits<double>::epsilon()};
1805 if (n == 0) {
1806 return {funm_result {matrix<C> {0, 0, buffer<C> {}}, tolerance, {}}, tolerance};
1807 }
1808 buffer<C> f(n * n, C {});
1809 for (std::size_t i {0}; i < n; ++i) {
1810 f[(i * n) + i] = values[i];
1811 }
1812 buffer<C> tc(n * n); // T and F by columns: the recurrence's sums contiguous along both operands
1813 buffer<C> fc(n * n, C {});
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);
1817 }
1818 fc[(i * n) + i] = values[i];
1819 }
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])};
1825 C left {};
1826 C right {};
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];
1834 }
1835 sum += left - right;
1836 const C gap {t(j, j) - t(i, i)};
1837 if (gap != C {}) {
1838 sum /= gap;
1839 }
1840 f[(i * n) + j] = sum;
1841 fc[(j * n) + i] = sum;
1842 smallest = std::min(smallest, std::abs(gap));
1843 }
1844 }
1845 buffer<C> rounding(n * n, C {}); // f at each eigenvalue, rounded
1846 for (std::size_t i {0}; i < n; ++i) {
1847 rounding[(i * n) + i] = tolerance * values[i] * detail::rounding_direction(i);
1848 }
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))};
1852 const matrix<C> result {z * matrix<C> {n, n, std::move(f)} *detail::adjoint_of(z)};
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) { // x − x is 0 for a finite part and NaN for an infinite or NaN one, without overflow
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();
1859 }
1860 return {funm_result {result, error, {}}, own};
1861 }
1862 } // namespace detail
1863
1864 [[nodiscard]] inline funm_result funm_from_schur(const matrix<std::complex<double>>& t,
1865 const matrix<std::complex<double>>& z,
1866 const std::vector<std::complex<double>>& values)
1867 {
1868 return detail::parlett_function(t, z, values).first;
1869 }
1870
1871 namespace detail {
1872
1875 [[nodiscard]] inline std::vector<std::size_t> eigenvalue_clusters(const std::vector<std::complex<double>>& values,
1876 double delta)
1877 {
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) {
1881 id[i] = i;
1882 }
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]) { // j's cluster joins i's
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;
1890 }
1891 }
1892 }
1893 }
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++;
1899 }
1900 id[i] = label[id[i]];
1901 }
1902 return id;
1903 }
1904
1907 inline constexpr double cluster_share {0.1};
1908
1913 inline constexpr double cluster_share_fine {0.01};
1914
1916 inline constexpr double funm_fallback_error {1e3 * std::numeric_limits<double>::epsilon()};
1917
1922 [[nodiscard]] inline double cluster_bound(const std::vector<std::complex<double>>& values,
1923 double share)
1924 {
1925 double scale {1.0};
1926 for (const std::complex<double>& v : values) {
1927 scale = std::max(scale, std::abs(v));
1928 }
1929 return share * scale;
1930 }
1931
1939 [[nodiscard]] inline bool clusters_separate(const std::vector<std::complex<double>>& values,
1940 double share)
1941 {
1942 const std::vector<std::size_t> cluster {eigenvalue_clusters(values, cluster_bound(values, share))};
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]];
1949 }
1950 for (std::size_t c {0}; c < count; ++c) {
1951 centre[c] /= static_cast<double>(members[c]);
1952 }
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);
1960 }
1961 else {
1962 outside[c] = std::min(outside[c], distance);
1963 }
1964 }
1965 }
1966 for (std::size_t c {0}; c < count; ++c) {
1967 if (!(outside[c] > spread[c])) {
1968 return false;
1969 }
1970 }
1971 return true;
1972 }
1973
1975 [[nodiscard]] inline std::vector<std::complex<double>> diagonal_of(const matrix<std::complex<double>>& t)
1976 {
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);
1980 }
1981 return values;
1982 }
1983
1987 {
1988 std::vector<std::size_t> starts;
1989 std::vector<std::complex<double>> centres;
1990 std::vector<double> radii;
1991 };
1992
1994 inline constexpr std::size_t contour_points {64};
1995
1999 inline constexpr std::size_t contour_points_most {4096};
2000
2002 inline constexpr double contour_tolerance {32.0 * std::numeric_limits<double>::epsilon()};
2003
2010 [[nodiscard]] inline cluster_circles circles_of(const matrix<std::complex<double>>& t,
2011 double share)
2012 {
2013 using C = std::complex<double>;
2014 const std::size_t n {t.rows()};
2015 const std::vector<C> values {diagonal_of(t)};
2016 const double delta {cluster_bound(values, share)};
2017 const std::vector<std::size_t> cluster {eigenvalue_clusters(values, delta)};
2018 cluster_circles circles;
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);
2022 }
2023 }
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) {
2032 continue;
2033 }
2034 C centre {};
2035 for (std::size_t i {first}; i < last; ++i) {
2036 centre += values[i];
2037 }
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)));
2049 }
2050 }
2051 circles.centres[b] = centre;
2052 circles.radii[b] = spread + std::min(std::max({spread, delta, coupling}), (outside - spread) / 2.0);
2053 }
2054 return circles;
2055 }
2056
2059 [[nodiscard]] inline std::vector<std::size_t> starting_points(const cluster_circles& circles)
2060 {
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);
2062 }
2063
2066 [[nodiscard]] inline std::vector<std::complex<double>> circle_points(const cluster_circles& circles,
2067 const std::vector<std::size_t>& counts)
2068 {
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)));
2076 }
2077 }
2078 }
2079 return points;
2080 }
2081
2087 [[nodiscard]] inline bool gather_clusters(matrix<std::complex<double>>& t,
2088 matrix<std::complex<double>>& z,
2089 double share)
2090 {
2091 using C = std::complex<double>;
2092 const std::size_t n {t.rows()};
2093 std::vector<C> values {diagonal_of(t)};
2094 const double delta {cluster_bound(values, share)};
2095 const std::vector<std::size_t> first {eigenvalue_clusters(values, delta)};
2096 if (*std::max_element(first.begin(), first.end()) + 1 == n) { // every cluster a single eigenvalue (n ≥ 1: an empty matrix is Hermitian)
2097 return false;
2098 }
2099 buffer<C> form(t.begin(), t.end());
2100 buffer<C> zt {transpose(z).elements()};
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];
2105 }
2106 const std::vector<std::size_t> cluster {eigenvalue_clusters(values, delta)};
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];
2110 }
2111 placed = move_leading(form, zt, n, chosen);
2112 }
2113 t = matrix<C> {n, n, std::move(form)};
2114 z = transpose(matrix<C> {n, n, std::move(zt)});
2115 return true;
2116 }
2117
2120 inline constexpr std::size_t funm_batch_elements {std::size_t {1} << 20};
2121
2128 inline void add_circle_terms(const matrix<std::complex<double>>& t,
2129 std::size_t first,
2130 std::size_t p,
2131 std::complex<double> centre,
2132 double radius,
2133 std::size_t count,
2134 std::size_t from,
2135 std::size_t step,
2136 const std::complex<double>* images,
2137 buffer<std::complex<double>>& sum,
2138 buffer<double>& moduli)
2139 {
2140 using C = std::complex<double>;
2141 // The points' inverses in batches on the threads (each point's own buffers), then their terms added in the
2142 // points' order: the same bits on any number of threads. Only the upper triangle: an upper triangular matrix's
2143 // inverse is upper triangular, and the sum's lower part stays the zero it starts as.
2144 const std::size_t terms {((count - from) + step - 1) / step}; // from < count: a grid of 64 points or more
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))};
2146 buffer<C> inverses(batch * p * p);
2147 buffer<C> shifted(batch * p * p);
2148 for (std::size_t done {0}; done < terms; done += batch) {
2149 const std::size_t now {std::min(batch, terms - done)};
2150 parallel_for(now, p * p * p, [&](std::size_t b) {
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);
2159 }
2160 x[(i * p) + i] = C {1.0};
2161 }
2162 solve_triangular_in_place(a, p, false, triangular_op::none, false, x, p);
2163 });
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());
2174 }
2175 }
2176 }
2177 }
2178 }
2179
2182 [[nodiscard]] inline std::vector<std::complex<double>> grid_points(std::complex<double> centre,
2183 double radius,
2184 std::size_t count,
2185 std::size_t from,
2186 std::size_t step)
2187 {
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)));
2191 }
2192 return points;
2193 }
2194
2204 [[nodiscard]] inline double circle_integral(buffer<std::complex<double>>& whole,
2205 buffer<std::complex<double>>& half,
2206 const buffer<double>& moduli,
2207 std::size_t p,
2208 std::size_t count,
2209 const std::complex<double>* diagonal)
2210 {
2211 double size {0.0};
2212 double gap {0.0};
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]);
2220 }
2221 for (std::size_t i {0}; i < p; ++i) {
2222 gap = std::max(gap, std::abs(whole[(i * p) + i] - diagonal[i]));
2223 }
2224 gap = std::max(gap, std::numeric_limits<double>::epsilon() * rounding / static_cast<double>(count));
2225 return size > 0.0 ? gap / size : gap;
2226 }
2227
2234 [[nodiscard]] inline buffer<std::complex<double>> circle_error(const buffer<std::complex<double>>& whole,
2235 const buffer<std::complex<double>>& half,
2236 const buffer<double>& moduli,
2237 std::size_t count)
2238 {
2239 buffer<std::complex<double>> error(whole.size());
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));
2242 }
2243 return error;
2244 }
2245
2261 [[nodiscard]] inline std::tuple<buffer<std::complex<double>>, double, double> assembled_function(const matrix<std::complex<double>>& t,
2262 const cluster_circles& circles,
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)
2266 {
2267 using C = std::complex<double>;
2268 const std::size_t n {t.rows()};
2269 const std::size_t count {circles.radii.size()};
2270 buffer<C> fx(n * n, C {});
2271 buffer<C> error(n * n, C {}); // the diagonal blocks' errors, as recurrence_error starts from them
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};
2275 if (p == 1) {
2276 fx[(first * n) + first] = at_eigenvalues[first];
2277 error[(first * n) + first] = std::numeric_limits<double>::epsilon() * at_eigenvalues[first] * rounding_direction(first);
2278 continue;
2279 }
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);
2283 }
2284 }
2285 double separation {std::numeric_limits<double>::infinity()}; // the smallest gap between two clusters' eigenvalues
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)));
2290 }
2291 }
2292 }
2293 solve_upper_blocks(t, circles.starts, fx, nullptr);
2294 const double estimate {recurrence_error(t, circles.starts, fx, std::move(error))};
2295 return {std::move(fx), std::min(1.0, std::max(parlett_estimate(t, separation), estimate)), estimate};
2296 }
2297
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,
2308 double share,
2309 const std::vector<std::size_t>& counts)
2310 {
2311 using C = std::complex<double>;
2312 const std::size_t n {t.rows()};
2313 const cluster_circles circles {circles_of(t, share)};
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");
2318 }
2319 std::vector<buffer<C>> blocks(circles.radii.size());
2320 std::vector<buffer<C>> errors(circles.radii.size()); // each block's, as assembled_function carries them
2321 std::vector<double> contours;
2322 std::size_t next {n}; // the next circle's first image
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};
2326 if (p == 1) {
2327 continue;
2328 }
2329 const std::size_t count {counts[contours.size()]};
2330 buffer<C> half(p * p, C {}); // the even points', then all of them
2331 buffer<C> odd(p * p, C {});
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]);
2336 }
2337 buffer<double> moduli(p * p, 0.0);
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);
2340 buffer<C> whole(p * p);
2341 for (std::size_t e {0}; e < p * p; ++e) {
2342 whole[e] = half[e] + odd[e];
2343 }
2344 contours.push_back(circle_integral(whole, half, moduli, p, count, images.data() + first));
2345 errors[b] = circle_error(whole, half, moduli, count);
2346 blocks[b] = std::move(whole);
2347 next += count;
2348 }
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)}; // a circle at least: images past the eigenvalues
2353 return {std::move(fx), std::min(1.0, std::max(estimate, contour_error)), std::move(contours)};
2354 }
2355
2358 [[nodiscard]] inline funm_result funm_answer(matrix<std::complex<double>>&& x,
2359 double error,
2360 std::vector<double>&& contours,
2361 const std::vector<std::complex<double>>& at_eigenvalues)
2362 {
2363 for (const std::complex<double>& entry : x) {
2364 error = is_finite_entry(entry) ? error : std::numeric_limits<double>::infinity();
2365 }
2366 for (const std::complex<double>& image : at_eigenvalues) {
2367 error = is_finite_entry(image) ? error : std::numeric_limits<double>::infinity();
2368 }
2369 return {std::move(x), error, std::move(contours)};
2370 }
2371 } // namespace detail
2372
2380 {
2383 std::vector<std::complex<double>> points;
2384 bool hermitian {false};
2385 double share {detail::cluster_share};
2386 std::vector<std::size_t> counts;
2387 };
2388
2396 template <typename T>
2397 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2398 [[nodiscard]] funm_plan plan_funm(const matrix<T>& a)
2399 {
2400 using C = std::complex<double>;
2401 if (a.rows() != a.cols()) {
2402 throw dimension_error("funm requires a square matrix");
2403 }
2404 detail::require_finite(a, "funm");
2405 const std::size_t n {a.rows()};
2406 funm_plan plan;
2407 if (detail::exactly_hermitian(a)) {
2408 const auto [values, vectors] {detail::hermitian_system(a)};
2409 buffer<C> diagonal(n * n, C {});
2410 for (std::size_t i {0}; i < n; ++i) {
2411 diagonal[(i * n) + i] = C {values[i]};
2412 }
2413 plan.t = matrix<C> {n, n, std::move(diagonal)};
2414 plan.z = matrix<C> {n, n, buffer<C>(vectors.begin(), vectors.end())};
2415 plan.points = detail::diagonal_of(plan.t);
2416 plan.hermitian = true;
2417 return plan;
2418 }
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)) { // chained clusters no circle separates: the finer share
2422 plan.share = detail::cluster_share_fine;
2423 }
2424 if (detail::gather_clusters(plan.t, plan.z, plan.share)) {
2425 plan.points = detail::diagonal_of(plan.t);
2426 const detail::cluster_circles circles {detail::circles_of(plan.t, plan.share)};
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());
2430 }
2431 return plan;
2432 }
2433
2441 [[nodiscard]] inline funm_result finish_funm(const funm_plan& plan,
2442 const std::vector<std::complex<double>>& images)
2443 {
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) { // the eigenvalues' values at least
2447 throw dimension_error("funm requires a square Schur form T, Z of its order and one value per eigenvalue");
2448 }
2449 const std::vector<C> at_eigenvalues(images.begin(), images.begin() + static_cast<std::ptrdiff_t>(n));
2450 if (!plan.hermitian && images.size() == n) {
2451 return funm_from_schur(plan.t, plan.z, at_eigenvalues);
2452 }
2453 matrix<C> x;
2454 double error {std::numeric_limits<double>::epsilon()};
2455 std::vector<double> contours;
2456 if (plan.hermitian) {
2457 x = detail::spectral<C>(plan.z, at_eigenvalues, false);
2458 }
2459 else {
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);
2462 error = estimate;
2463 contours = std::move(integrals);
2464 }
2465 return detail::funm_answer(std::move(x), error, std::move(contours), at_eigenvalues);
2466 }
2467
2472 [[nodiscard]] inline std::vector<std::complex<double>> funm_points(const funm_plan& plan)
2473 {
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());
2477 return points;
2478 }
2479
2485 [[nodiscard]] inline funm_plan regathered(funm_plan plan,
2486 double share)
2487 {
2488 plan.share = share;
2489 plan.counts = {};
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));
2493 plan.points = funm_points(plan);
2494 }
2495 return plan;
2496 }
2497
2508 template <typename T>
2509 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2510 [[nodiscard]] funm_result funm(const matrix<T>& a,
2511 const std::function<std::vector<std::complex<double>>(const std::vector<std::complex<double>>&)>& f)
2512 {
2513 using C = std::complex<double>;
2514 // each circle whose integral falls short of contour_tolerance takes twice the points while it gains at least half:
2515 // the grid of 2P points is that of P and the P between, so only those are new (f there, and their resolvents)
2516 // each attempt with its own estimate beside (the recurrence's and the circles', without SciPy's floor), by which
2517 // funm weighs them
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);
2523 }
2524 if (plan.hermitian || plan.counts.empty() || images.size() != plan.points.size()) {
2525 funm_result answer {finish_funm(plan, images)};
2526 const double own {answer.error};
2527 return {std::move(answer), own};
2528 }
2529 const detail::cluster_circles circles {detail::circles_of(plan.t, plan.share)};
2530 std::vector<std::size_t> at; // each circle's block
2531 std::vector<buffer<C>> sums; // its rule's sum over all its points so far
2532 std::vector<buffer<C>> halves; // over the even ones
2533 std::vector<buffer<double>> moduli; // its terms' moduli, summed
2534 for (std::size_t b {0}; b < circles.radii.size(); ++b) {
2535 if (circles.radii[b] > 0.0) {
2536 at.push_back(b);
2537 }
2538 }
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]);
2547 }
2548 next += plan.counts[c];
2549 buffer<C> half(p * p, C {});
2550 buffer<C> odd(p * p, C {});
2551 buffer<double> sizes(p * p, 0.0);
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) {
2556 odd[e] += half[e];
2557 }
2558 sums.push_back(std::move(odd));
2559 halves.push_back(std::move(half));
2560 }
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 = [&] { // each block from its sums, and its estimate
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]};
2570 buffer<C> whole {sums[c]};
2571 buffer<C> half {halves[c]};
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);
2575 }
2576 };
2577 integrals();
2578 for (;;) {
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);
2586 }
2587 else {
2588 settled[c] = true;
2589 }
2590 }
2591 if (refined.empty()) {
2592 break;
2593 }
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");
2597 }
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]};
2603 buffer<C> added(p * p, C {});
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];
2609 }
2610 counts[c] *= 2;
2611 }
2612 integrals();
2613 for (const std::size_t c : refined) {
2614 settled[c] = !(errors[c] < 0.5 * before[c]);
2615 }
2616 }
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};
2624 };
2625 const funm_plan plan {plan_funm(a)}; // its share the finer where the clusters chain (detail::clusters_separate)
2626 auto best {evaluated(plan)};
2627 // clusters, and an estimate past it, at the coarser share
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);
2632 }
2633 }
2634 // clusters still, and an estimate past it: Parlett's recurrence with every eigenvalue apart, as SciPy's. A bound
2635 // relative to the largest modulus joins eigenvalues far apart where the spectrum spans decades (0 and −30 beside
2636 // −500, whose circle of radius 60 lost all to cancellation under exp; 1 and 300 beside 10⁵), which the recurrence
2637 // divides by their gap alone.
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);
2642 }
2643 // and Davies and Higham's own bound, 0.1 whatever the largest modulus: a tight pair gathers under a small
2644 // circle, apart from an eigenvalue 30 away that both relative bounds joined to it (0 and −10⁻¹² beside −30 and
2645 // −5000: Parlett's recurrence divided by 10⁻¹², 2·10⁻⁶; this, 10⁻¹⁵)
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));
2649 }
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);
2654 }
2655 }
2656 }
2657 return std::move(best.first);
2658 }
2659
2666 {
2668 bool exactly_singular {false};
2669 bool nearly_singular {false};
2670 };
2671
2672 namespace detail {
2673
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};
2677
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};
2681
2682
2684 [[nodiscard]] inline double unwinding(const std::complex<double>& z)
2685 {
2686 return std::ceil((z.imag() - std::numbers::pi) / (2.0 * std::numbers::pi));
2687 }
2688
2694 [[nodiscard]] inline std::complex<double> briggs(std::complex<double> a,
2695 std::size_t k)
2696 {
2697 using C = std::complex<double>;
2698 if (k == 0) {
2699 return a - C {1.0};
2700 }
2701 if (k == 1) {
2702 return complex_sqrt(a) - C {1.0};
2703 }
2704 std::size_t remaining {k};
2705 if (std::arg(a) >= std::numbers::pi / 2.0) {
2706 a = complex_sqrt(a);
2707 --remaining;
2708 }
2709 const C z0 {a - C {1.0}};
2710 a = complex_sqrt(a);
2711 C product {C {1.0} + a};
2712 for (std::size_t j {1}; j < remaining; ++j) {
2713 a = complex_sqrt(a);
2714 product *= C {1.0} + a;
2715 }
2716 return z0 / product;
2717 }
2718
2721 [[nodiscard]] inline std::complex<double> fractional_power_superdiagonal(const std::complex<double>& l1,
2722 const std::complex<double>& l2,
2723 const std::complex<double>& t12,
2724 double p)
2725 {
2726 using C = std::complex<double>;
2727 if (l1 == l2) {
2728 return t12 * p * complex_exp((p - 1.0) * complex_log(l1));
2729 }
2730 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2731 return t12 * (complex_exp(p * complex_log(l2)) - complex_exp(p * complex_log(l1))) / (l2 - l1);
2732 }
2733 const C z {(l2 - l1) / (l2 + l1)};
2734 const C log1 {complex_log(l1)};
2735 const C log2 {complex_log(l2)};
2736 const C scaled {t12 * complex_exp((p / 2.0) * (log2 + log1))};
2737 const double u {unwinding(log2 - log1)};
2738 const C b {p * (complex_atanh(z) + (std::numbers::pi * C {0.0, 1.0} *u))};
2739 return scaled * (C {2.0} *complex_sinh(b) / (l2 - l1));
2740 }
2741
2744 [[nodiscard]] inline std::complex<double> log_superdiagonal(const std::complex<double>& l1,
2745 const std::complex<double>& l2,
2746 const std::complex<double>& t12)
2747 {
2748 using C = std::complex<double>;
2749 if (l1 == l2) {
2750 return t12 / l1;
2751 }
2752 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2753 return t12 * (complex_log(l2) - complex_log(l1)) / (l2 - l1);
2754 }
2755 const C z {(l2 - l1) / (l2 + l1)};
2756 const double u {unwinding(complex_log(l2) - complex_log(l1))};
2757 return t12 * C {2.0} *(complex_atanh(z) + (std::numbers::pi * C {0.0, 1.0} *u)) / (l2 - l1);
2758 }
2759
2762 [[nodiscard]] inline double briggs(double a,
2763 std::size_t k)
2764 {
2765 if (k == 0) {
2766 return a - 1.0;
2767 }
2768 const double z0 {a - 1.0};
2769 a = std::sqrt(a);
2770 double product {1.0 + a};
2771 for (std::size_t j {1}; j < k; ++j) {
2772 a = std::sqrt(a);
2773 product *= 1.0 + a;
2774 }
2775 return z0 / product;
2776 }
2777
2779 [[nodiscard]] inline double fractional_power_superdiagonal(double l1,
2780 double l2,
2781 double t12,
2782 double p)
2783 {
2784 if (l1 == l2) {
2785 return t12 * p * std::exp((p - 1.0) * std::log(l1));
2786 }
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);
2789 }
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));
2792 }
2793
2795 [[nodiscard]] inline double log_superdiagonal(double l1,
2796 double l2,
2797 double t12)
2798 {
2799 if (l1 == l2) {
2800 return t12 / l1;
2801 }
2802 if (std::abs(l2 - l1) > std::abs(l1 + l2) / 2.0) {
2803 return t12 * (std::log(l2) - std::log(l1)) / (l2 - l1);
2804 }
2805 return t12 * 2.0 * std::atanh((l2 - l1) / (l2 + l1)) / (l2 - l1);
2806 }
2807
2809 [[nodiscard]] inline double scalar_log(double x)
2810 {
2811 return std::log(x);
2812 }
2813
2815 [[nodiscard]] inline std::complex<double> scalar_log(const std::complex<double>& z)
2816 {
2817 return complex_log(z);
2818 }
2819
2824 template <typename T>
2826 {
2827 public:
2828
2830 std::size_t n) : shifted_ {t}, n_ {n}
2831 {
2832 for (std::size_t i {0}; i < n; ++i) {
2833 shifted_[(i * n) + i] -= T {1.0};
2834 }
2835 power_ = shifted_;
2836 }
2837
2838 [[nodiscard]] double operator()(std::size_t p)
2839 {
2840 while (norms_.size() + 1 < p) {
2841 square_product_into(power_, shifted_, n_, spare_);
2842 std::swap(power_, spare_);
2843 norms_.push_back(one_norm(power_, n_));
2844 }
2845 return std::pow(norms_[p - 2], 1.0 / static_cast<double>(p));
2846 }
2847
2848 private:
2849
2852 buffer<T> spare_; // the next power's storage, the one before's once swapped
2853 std::size_t n_;
2854 std::vector<double> norms_;
2855 };
2856
2859 [[nodiscard]] inline bool principal_branch(const buffer<double>& /*t*/,
2860 std::size_t /*n*/)
2861 {
2862 return true;
2863 }
2864
2866 [[nodiscard]] inline bool principal_branch(const buffer<std::complex<double>>& t,
2867 std::size_t n)
2868 {
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)) {
2872 return false;
2873 }
2874 }
2875 return true;
2876 }
2877
2885 template <typename T>
2886 [[nodiscard]] std::tuple<buffer<T>, std::size_t, std::size_t> inverse_squaring(const buffer<T>& t0,
2887 std::size_t n,
2888 const std::array<double, 8>& theta = log_pade_bounds,
2889 const char* name = "logm")
2890 {
2891 const auto bound = [&theta](std::size_t m) { return theta[m]; };
2892 std::size_t s0 {0};
2894 for (std::size_t i {0}; i < n; ++i) {
2895 diagonal[i] = t0[(i * n) + i];
2896 }
2897 const auto far = [&diagonal, &bound]() {
2898 double largest {0.0};
2899 for (const T& d : diagonal) {
2900 largest = std::max(largest, std::abs(d - T {1.0}));
2901 }
2902 return largest > bound(7);
2903 };
2904 while (far()) {
2905 for (T& d : diagonal) {
2906 d = scalar_sqrt(d);
2907 }
2908 ++s0;
2909 }
2910 buffer<T> t {t0};
2911 for (std::size_t i {0}; i < s0; ++i) {
2912 t = triangular_square_root(t, n);
2913 }
2914 std::size_t s {s0};
2915 shifted_power_norms<T> norms {t, n};
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})};
2918 while (m == 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)) { // NaN compares false with every bound: the roots would go on for ever
2923 throw convergence_error(std::string {name} + ": the square roots of the triangular form are not finite");
2924 }
2925 if (a3 <= bound(7)) {
2926 std::size_t j1 {3};
2927 while (a3 > bound(j1)) {
2928 ++j1;
2929 }
2930 if (j1 <= 6) {
2931 m = j1;
2932 break;
2933 }
2934 // a square root about halves a3, so one in (θ₆, θ₇] falls to θ₆ or below: the paper's cap of two such roots
2935 // (SciPy's k < 2) is never reached
2936 if (a3 / 2.0 <= bound(5)) {
2937 t = triangular_square_root(t, n);
2938 norms = shifted_power_norms<T> {t, n};
2939 ++s;
2940 continue;
2941 }
2942 }
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});
2946 if (m == 0) {
2947 t = triangular_square_root(t, n);
2948 norms = shifted_power_norms<T> {t, n};
2949 ++s;
2950 }
2951 }
2952 for (std::size_t i {0}; i < n; ++i) {
2953 t[(i * n) + i] -= T {1.0};
2954 }
2955 if (principal_branch(t0, n)) {
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);
2959 if (j + 1 < n) {
2960 t[(j * n) + j + 1] = fractional_power_superdiagonal(t0[(j * n) + j], t0[((j + 1) * n) + j + 1], t0[(j * n) + j + 1], p);
2961 }
2962 }
2963 }
2964 return {std::move(t), s, m};
2965 }
2966
2973 template <typename T>
2974 [[nodiscard]] buffer<T> triangular_log(const buffer<T>& t0,
2975 std::size_t n)
2976 {
2977 static constexpr std::array<std::array<double, 7>, 7> nodes {{
2978 {0.5},
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 {{
2986 {1.0},
2987 {0.5, 0.5},
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}}};
2994 auto [r, s, m] {inverse_squaring(t0, n)};
2995 buffer<T> u(n * n, T {});
2996 buffer<T> shifted(n * n); // each node's I + β R and α R, written whole
2997 buffer<T> term(n * n);
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];
3004 }
3005 for (std::size_t i {0}; i < n; ++i) {
3006 shifted[(i * n) + i] += T {1.0};
3007 }
3008 solve_triangular_in_place(shifted.data(), n, false, triangular_op::none, false, term.data(), n);
3009 for (std::size_t e {0}; e < n * n; ++e) {
3010 u[e] += term[e];
3011 }
3012 }
3013 const double power {std::ldexp(1.0, static_cast<int>(s))};
3014 for (T& x : u) {
3015 x *= power;
3016 }
3017 if (principal_branch(t0, n)) {
3018 for (std::size_t i {0}; i < n; ++i) {
3019 u[(i * n) + i] = scalar_log(t0[(i * n) + i]);
3020 if (i + 1 < n) {
3021 u[(i * n) + i + 1] = log_superdiagonal(t0[(i * n) + i], t0[((i + 1) * n) + i + 1], t0[(i * n) + i + 1]);
3022 }
3023 }
3024 }
3025 return u;
3026 }
3027
3031 template <typename T>
3032 [[nodiscard]] std::pair<bool, bool> force_nonsingular(buffer<T>& t,
3033 std::size_t n)
3034 {
3035 constexpr double tiny {1e-20};
3036 bool exact {false};
3037 bool near {false};
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;
3042 }
3043 if (exact) {
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];
3046 }
3047 }
3048 return {exact, near && !exact};
3049 }
3050 } // namespace detail
3051
3052 namespace detail {
3053
3055 [[nodiscard]] inline const matrix<std::complex<double>>& as_complex(const matrix<std::complex<double>>& a)
3056 {
3057 return a;
3058 }
3059
3062 {
3064 }
3065
3067 [[nodiscard]] inline std::complex<double> principal_power(const std::complex<double>& z,
3068 double p)
3069 {
3070 return complex_exp(p * complex_log(z));
3071 }
3072
3075 [[nodiscard]] inline double power_pade_constant(std::size_t i,
3076 double t)
3077 {
3078 if (i == 1) {
3079 return -t;
3080 }
3081 if (i % 2 == 0) {
3082 const double j {static_cast<double>(i) / 2.0}; // i even: exact
3083 return (t - j) / (2.0 * ((2.0 * j) - 1.0));
3084 }
3085 const double j {(static_cast<double>(i) - 1.0) / 2.0}; // i odd: exact
3086 return (-j - t) / (2.0 * ((2.0 * j) + 1.0));
3087 }
3088
3094 [[nodiscard]] inline buffer<std::complex<double>> power_pade(const buffer<std::complex<double>>& x,
3095 std::size_t n,
3096 double t,
3097 std::size_t m)
3098 {
3099 using C = std::complex<double>;
3100 buffer<C> y(n * n);
3101 for (std::size_t e {0}; e < n * n; ++e) {
3102 y[e] = x[e] * power_pade_constant(2 * m, t);
3103 }
3104 buffer<C> rhs(n * n); // each step's cⱼ X, written whole, then Y's
3105 for (std::size_t j {(2 * m) - 1}; j >= 1; --j) {
3106 for (std::size_t e {0}; e < n * n; ++e) {
3107 rhs[e] = x[e] * power_pade_constant(j, t);
3108 }
3109 for (std::size_t i {0}; i < n; ++i) {
3110 y[(i * n) + i] += C {1.0};
3111 }
3112 solve_triangular_in_place(y.data(), n, false, triangular_op::none, false, rhs.data(), n);
3113 std::swap(y, rhs);
3114 }
3115 for (std::size_t i {0}; i < n; ++i) {
3116 y[(i * n) + i] += C {1.0};
3117 }
3118 return y;
3119 }
3120
3129 [[nodiscard]] inline buffer<std::complex<double>> triangular_power(const buffer<std::complex<double>>& t0,
3130 std::size_t n,
3131 double t)
3132 {
3133 using C = std::complex<double>;
3134 bool diagonal {true};
3135 for (std::size_t i {0}; i < n; ++i) {
3136 for (std::size_t j {i + 1}; j < n; ++j) {
3137 diagonal = diagonal && t0[(i * n) + j] == C {};
3138 }
3139 }
3140 if (diagonal) {
3141 buffer<C> u(n * n, C {});
3142 for (std::size_t i {0}; i < n; ++i) {
3143 u[(i * n) + i] = principal_power(t0[(i * n) + i], t);
3144 }
3145 return u;
3146 }
3147 auto [r, s, m] {inverse_squaring(t0, n, power_pade_bounds, "fractional_matrix_power")};
3148 for (C& x : r) {
3149 x = -x;
3150 }
3151 buffer<C> u {power_pade(r, n, t, m)};
3152 buffer<C> spare;
3153 const bool exact {principal_branch(t0, n)};
3154 for (std::size_t i {s + 1}; i-- > 0;) {
3155 if (i < s) {
3156 square_in_place(u, spare, n);
3157 }
3158 if (exact) {
3159 const double p {std::ldexp(t, -static_cast<int>(i))};
3160 for (std::size_t j {0}; j < n; ++j) {
3161 u[(j * n) + j] = principal_power(t0[(j * n) + j], p);
3162 if (j + 1 < n) {
3163 u[(j * n) + j + 1] = fractional_power_superdiagonal(t0[(j * n) + j], t0[((j + 1) * n) + j + 1], t0[(j * n) + j + 1], p);
3164 }
3165 }
3166 }
3167 }
3168 return u;
3169 }
3170
3177 [[nodiscard]] inline buffer<std::complex<double>> nearly_diagonal_power(const buffer<std::complex<double>>& t,
3178 std::size_t n,
3179 double p)
3180 {
3181 buffer<std::complex<double>> u(n * n, std::complex<double> {});
3182 for (std::size_t i {0}; i < n; ++i) {
3183 u[(i * n) + i] = principal_power(t[(i * n) + i], p);
3184 for (std::size_t j {i + 1}; j < n; ++j) {
3185 u[(i * n) + j] = fractional_power_superdiagonal(t[(i * n) + i], t[(j * n) + j], t[(i * n) + j], p);
3186 }
3187 }
3188 return u;
3189 }
3190
3192 [[nodiscard]] inline buffer<double> nearly_diagonal_power(const matrix<double>& similar,
3193 double p)
3194 {
3195 const std::size_t n {similar.rows()};
3196 buffer<double> u(n * n, 0.0);
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) {
3200 u[(i * n) + j] = fractional_power_superdiagonal(similar(i, i), similar(j, j), similar(i, j), p);
3201 }
3202 }
3203 return u;
3204 }
3205
3208 template <typename T>
3214
3216 template <typename T>
3218 {
3219 matrix<T> v {hermitian_system(a).second};
3220 matrix<T> similar {adjoint_of(v) * a * v};
3221 return {std::move(v), std::move(similar)};
3222 }
3223
3231 [[nodiscard]] inline buffer<std::complex<double>> similar_power(const matrix<std::complex<double>>& similar,
3232 double t)
3233 {
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 {};
3241 }
3242 }
3243 return nearly_diagonal_power(upper, n, t);
3244 }
3245
3253 double t)
3254 {
3255 using C = std::complex<double>;
3256 const matrix<double>& v {s.vectors};
3257 const std::size_t n {v.rows()};
3258 const matrix<double> vt {adjoint_of(v)};
3259 bool positive {true};
3260 for (std::size_t i {0}; i < n; ++i) {
3261 positive = positive && s.similar(i, i) > 0.0;
3262 }
3263 if (positive) { // every power real: in real arithmetic throughout (order 200 1.7 → 0.3 ms for T^t)
3264 return as_complex(v * matrix<double> {n, n, nearly_diagonal_power(s.similar, t)} *vt);
3265 }
3266 const buffer<C> u {similar_power(as_complex(s.similar), t)};
3267 buffer<double> real(n * n);
3268 buffer<double> imaginary(n * n);
3269 for (std::size_t k {0}; k < n * n; ++k) {
3270 real[k] = u[k].real();
3271 imaginary[k] = u[k].imag();
3272 }
3273 const matrix<double> real_part {v * matrix<double> {n, n, std::move(real)} *vt};
3274 // some eigenvalue negative: its principal power, and with it T^t, complex
3275 const matrix<double> imaginary_part {v * matrix<double> {n, n, std::move(imaginary)} *vt};
3276 buffer<C> power(n * n);
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)};
3279 }
3280 return matrix<C> {n, n, std::move(power)};
3281 }
3282
3285 [[nodiscard]] inline matrix<std::complex<double>> hermitian_remainder_power(const hermitian_similarity<std::complex<double>>& s,
3286 double t)
3287 {
3288 const std::size_t n {s.vectors.rows()};
3289 return s.vectors * matrix<std::complex<double>> {n, n, similar_power(s.similar, t)} *adjoint_of(s.vectors);
3290 }
3291
3296 template <typename T>
3297 [[nodiscard]] std::optional<matrix<std::complex<double>>> remainder_power(const matrix<T>& a,
3298 double t,
3299 const std::optional<hermitian_similarity<T>>& similarity)
3300 {
3301 using C = std::complex<double>;
3302 const std::size_t n {a.rows()};
3303 const bool triangular {upper_triangular(a)};
3304 const bool hermitian {exactly_hermitian(a)};
3305 if (similarity) {
3306 return hermitian_remainder_power(*similarity, t);
3307 }
3308 matrix<C> form;
3309 matrix<C> z;
3310 if (triangular) {
3311 form = as_complex(a);
3312 }
3313 else {
3314 std::tie(form, z) = function_schur_form(a);
3315 }
3316 buffer<C> triangle(form.begin(), form.end());
3317 for (std::size_t i {0}; i < n; ++i) {
3318 if (triangle[(i * n) + i] == C {}) {
3319 return std::nullopt;
3320 }
3321 if (hermitian) { // its eigenvalues real: a negative one's rounding below the axis took the other branch
3322 triangle[(i * n) + i] = C {triangle[(i * n) + i].real(), 0.0};
3323 }
3324 }
3325 matrix<C> u {n, n, triangular_power(triangle, n, t)};
3326 if (triangular) {
3327 return u;
3328 }
3329 return z * u * adjoint_of(z);
3330 }
3331
3334 template <typename T>
3335 [[nodiscard]] matrix<T> integer_power(const matrix<T>& a,
3336 double e)
3337 {
3338 const std::size_t n {a.rows()};
3339 matrix<T> square {e < 0.0 ? inverse(a) : a};
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) {
3343 result = result ? *result * square : square;
3344 }
3345 k = std::floor(k / 2.0);
3346 if (k > 0.0) {
3347 square = square * square;
3348 }
3349 }
3350 if (result) {
3351 return *result;
3352 }
3353 buffer<T> unit(n * n, T {});
3354 for (std::size_t i {0}; i < n; ++i) {
3355 unit[(i * n) + i] = T {1.0};
3356 }
3357 return matrix<T> {n, n, std::move(unit)};
3358 }
3359 } // namespace detail
3360
3377 template <typename T>
3378 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3380 double p)
3381 {
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");
3386 }
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");
3390 }
3391 if (n == 0) {
3392 return matrix<C> {0, 0, buffer<C> {}};
3393 }
3394 if (p == std::floor(p)) {
3395 return detail::as_complex(detail::integer_power(a, p));
3396 }
3397 // V Λᵖ Vᴴ from one eigendecomposition, a negative eigenvalue's power complex; for p > 0 only: an eigenvalue's
3398 // absolute error ε ‖A‖ grows by the condition under a negative power (60 times the Schur–Padé path's error seen)
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);
3404 }
3405 return detail::spectral<C>(vectors, powers, std::all_of(values.begin(), values.end(), [](double v) { return v >= 0.0; }));
3406 }
3407 // A Hermitian matrix not triangular: its singular values the magnitudes of Vᴴ A V's diagonal (its eigenvalues to
3408 // the similarity's rounding, of which the remainder takes the power: none of them 0 there), the similarity then the
3409 // remainder's (\ref detail::hermitian_remainder_power); one decomposition in place of two
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);
3420 }
3421 }
3422 else {
3423 const vector<double> sigma {singular_values(a)};
3424 largest = sigma[0];
3425 smallest = sigma[n - 1];
3426 }
3427 if (smallest != 0.0) {
3428 const double k2 {largest / smallest}; // the condition chooses between ⌊p⌋ and ⌈p⌉, as SciPy's
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;
3435 }
3436 }
3437 if (p < 0.0) {
3438 throw singular_matrix_error("fractional_matrix_power: a negative power of a singular matrix");
3439 }
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); });
3444 return powers;
3445 };
3446 return detail::as_complex(detail::integer_power(a, std::floor(p))) * funm(a, power).f;
3447 }
3448
3449 namespace detail {
3450
3453 template <typename T>
3455 std::size_t n,
3456 const matrix<T>* z)
3457 {
3458 const auto [exact, near] {force_nonsingular(t, n)};
3459 const matrix<T> u {n, n, triangular_log(t, n)};
3460 return {as_complex(z == nullptr ? u : *z * u * adjoint_of(*z)), exact, near};
3461 }
3462
3464 [[nodiscard]] inline bool nonnegative_diagonal(const matrix<double>& t)
3465 {
3466 for (std::size_t i {0}; i < t.rows(); ++i) {
3467 if (t(i, i) < 0.0) {
3468 return false;
3469 }
3470 }
3471 return true;
3472 }
3473
3476 [[nodiscard]] inline logm_result general_logm(const matrix<std::complex<double>>& a)
3477 {
3478 using C = std::complex<double>;
3479 if (upper_triangular(a)) {
3480 return schur_logm<C>(buffer<C>(a.begin(), a.end()), a.rows(), nullptr);
3481 }
3482 const schur_decomposition<C> s {a};
3483 return schur_logm(buffer<C>(s.t().begin(), s.t().end()), a.rows(), &s.z());
3484 }
3485
3489 [[nodiscard]] inline logm_result general_logm(const matrix<double>& a)
3490 {
3491 using C = std::complex<double>;
3492 if (upper_triangular(a)) {
3493 if (nonnegative_diagonal(a)) {
3494 return schur_logm<double>(buffer<double>(a.begin(), a.end()), a.rows(), nullptr);
3495 }
3496 return schur_logm<C>(buffer<C>(a.begin(), a.end()), a.rows(), nullptr);
3497 }
3498 const schur_decomposition<double> s {a};
3499 if (upper_triangular(s.t()) && nonnegative_diagonal(s.t())) {
3500 return schur_logm(buffer<double>(s.t().begin(), s.t().end()), a.rows(), &s.z());
3501 }
3502 const auto [form, z] {complex_schur_form(s.t(), s.z())};
3503 return schur_logm(buffer<C>(form.begin(), form.end()), a.rows(), &z);
3504 }
3505 } // namespace detail
3506
3521 template <typename T>
3522 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3523 [[nodiscard]] logm_result logm(const matrix<T>& a)
3524 {
3525 using C = std::complex<double>;
3526 const std::size_t n {a.rows()};
3527 if (a.cols() != n) {
3528 throw dimension_error("logm requires a square matrix");
3529 }
3530 detail::require_finite(a, "logm");
3531 if (n == 0) {
3532 return {matrix<C> {0, 0, buffer<C> {}}, false, false};
3533 }
3534 if (detail::exactly_hermitian(a)) { // V log(Λ) Vᴴ, unless an eigenvalue is below 10⁻²⁰ (SciPy's singular cases)
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]});
3541 }
3542 if (regular) {
3543 return {detail::spectral<C>(vectors, logs, values[0] > 0.0), false, false};
3544 }
3545 }
3546 return detail::general_logm(a);
3547 }
3548} // namespace numerical
3549
3550#endif // NUMERICAL_MATRIX_FUNCTIONS_HPP
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Definition vector.hpp:87
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)
A standard exception Std that numerical::error tags too, its one what answering for both bases.
Definition vector.hpp:61
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
Definition vector.hpp:40
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.
Definition matrix.hpp:36
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
Definition matrix.hpp:139
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
Definition matrix.hpp:133
std::size_t rows() const noexcept
The number of rows.
Definition matrix.hpp:108
buffer< T > elements() &&
The elements, row-major, handed over by a matrix about to expire, which is left 0 × 0: a large result...
Definition matrix.hpp:146
std::size_t cols() const noexcept
The number of columns.
Definition matrix.hpp:114
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): ...
Definition eigen.hpp:3501
const matrix< T > & t() const &noexcept
T, upper quasi-triangular (real) or triangular (complex).
Definition eigen.hpp:3626
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.
Definition vector.hpp:171
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.
Definition fft.hpp:1290
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).
Definition parallel.hpp:790
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,...
Definition eigen.hpp:3462
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,...
Definition gemm.hpp:715
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.
Definition amx.hpp:44
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...
Definition buffer.hpp:443
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),...
Definition matrix.hpp:251
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....
Definition svd.hpp:2274
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...
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.