|
NumericAL
A header-only C++20 lexer built on REAL
|
Functions of a square matrix and the matrix equations solved through Schur forms: the exponential, by scaling and squaring of a Padé approximant; the principal square root, by the Schur method; the Sylvester equation A X + X B = Q, as Bartels and Stewart.
More...
#include <algorithm>#include <array>#include <cmath>#include <complex>#include <concepts>#include <cstddef>#include <functional>#include <limits>#include <numeric>#include <numbers>#include <optional>#include <stdexcept>#include <string>#include <tuple>#include <utility>#include <vector>#include "complex_math.hpp"#include "eigen.hpp"Go to the source code of this file.
Classes | |
| struct | numerical::detail::taylor_bound |
Al-Mohy and Higham's θ_m (2011, table 3.1, double precision): the 1-norm of t A up to which m terms of the Taylor series of e^{tA} B, taken s times, stay within the unit roundoff, for the m the selection tries (SciPy's, from 1 to 30, then by fives to 55). More... | |
| struct | numerical::detail::taylor_plan |
The terms m and the steps s of expm_multiply. More... | |
| class | numerical::no_real_root_error |
| Thrown when a real matrix has no real principal square root (a real eigenvalue below 0): its root is complex. More... | |
| struct | numerical::funm_result |
A function of a square matrix from its complex Schur form, as scipy.linalg.funm forms it: f(A) and the estimate of its relative error. More... | |
| struct | numerical::detail::cluster_circles |
The circles of Cauchy's integral about the clusters of the reordered Schur form t (each a run of its diagonal): the runs' starts (and n), and each run's centre and radius (0 for a single eigenvalue). More... | |
| struct | numerical::funm_plan |
Where funm wants f, and the forms it completes: a Hermitian A's eigendecomposition (t Λ, z V); else its complex Schur form (a real matrix's real form made complex, as rsf2csf), reordered so the eigenvalues within 10⁻² of the largest modulus (or of 1) gather in runs. points: the eigenvalues in the form's order, then detail::contour_points on the circle about each run of two or more. More... | |
| struct | numerical::logm_result |
The principal logarithm of a square matrix with what SciPy warns of: log A (complex), and whether A's triangular form was exactly singular (its zero diagonal entries taken as 10⁻²⁰, as SciPy's) or nearly (a diagonal entry below 10⁻²⁰ in modulus). More... | |
| class | numerical::detail::shifted_power_norms< T > |
‖(T − I)ᵖ‖₁^(1/p) of the upper triangular n × n t, p from 2, exactly (SciPy estimates them, onenormest): each power the one before times T − I, formed once whatever order the norms are asked in. More... | |
| struct | numerical::detail::hermitian_similarity< T > |
A Hermitian matrix A's eigenvectors V (hermitian_system) and Vᴴ A V: its Schur form Λ to the similarity's rounding, which hermitian_remainder_power keeps above the diagonal. More... | |
Namespaces | |
| namespace | numerical |
| The NumericAL public API. | |
| namespace | numerical::detail |
Enumerations | |
| enum class | numerical::frechet_method { numerical::scaling_pade_squaring , numerical::block_enlarge } |
How expm_frechet computes: Al-Mohy and Higham's algorithm (SciPy's "SPS"), or the exponential of the block matrix [[A, E], [0, A]] ("blockEnlarge"). More... | |
Functions | |
| buffer< double > | numerical::detail::entry_moduli (const buffer< double > &a) |
| The moduli of a real matrix's entries. | |
| buffer< double > | numerical::detail::entry_moduli (const buffer< std::complex< double > > &a) |
The moduli of a complex matrix's entries: √(x² + y²), which vectorises, where the largest part lies in [2⁻⁵⁰⁰, 2⁵⁰⁰] (no square overflows; one that underflows is of an entry below 2⁻⁵⁰⁰ times the largest's, nothing to a norm); hypot otherwise, as std::abs takes it. | |
| double | numerical::detail::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 column sum. | |
| template<typename T > | |
| double | numerical::detail::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. | |
| double | numerical::detail::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 p products of a vector and |A|, a matrix of moduli's norm its largest entry. | |
| template<typename T > | |
| void | numerical::detail::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, as many made as needed): C = A·B, each part of it zeroed by the thread that computes it (c_start::zero), where a zeroed buffer was filled on the calling thread first. c is neither operand. | |
| template<typename T > | |
| buffer< T > | numerical::detail::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). | |
| template<typename T > | |
| void | numerical::detail::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): no fresh n × n mapped and faulted in per squaring. | |
| const double * | numerical::detail::pade_coefficients (std::size_t m) |
The coefficients b₀ … b_m of the [m/m] Padé approximant of the exponential, as Higham's (2005). | |
| std::size_t | numerical::detail::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 error bound, from the leading term of its series |c₂ₘ₊₁| ‖ |A|²ᵐ⁺¹ ‖₁ / ‖A‖₁, falls below the unit roundoff; A times scale (a power of two), its norms exact, from its moduli (|A|, formed once for every degree tried: a complex entry's modulus is a hypot). | |
| template<typename T > | |
| buffer< T > | numerical::detail::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², A⁴, A⁶, and A⁸ for m = 9), as Higham's (2005): U the odd terms, V the even, A¹³'s terms by A⁶ (A⁶ (b₁₃ A⁶ + b₁₁ A⁴ + b₉ A²) + …). | |
| template<typename T > | |
| T | numerical::detail::sinch (const T &x) |
sinh(x) / x, 1 at 0, by its series where x is small. | |
| template<typename T > | |
| void | numerical::detail::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 triangular t, as Al-Mohy and Higham's code fragment 2.1: e^{λᵢ}, and t_{i,i+1} e^{(λᵢ + λᵢ₊₁)/2} sinch((λᵢ − λᵢ₊₁)/2); past divided_exponentials_past, t_{i,i+1} (e^{λᵢ} − e^{λᵢ₊₁}) / (λᵢ − λᵢ₊₁), where that difference overflows each exponential divided by the gap's modulus within it (e^{λ − log|g|}), so that the band overflows only where it is past the largest double. | |
| template<typename T > | |
| bool | numerical::detail::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 V f(Λ) Vᴴ from one eigendecomposition (Armadillo's expmat_sym, logmat_sympd, sqrtmat_sympd). | |
| std::pair< vector< double >, matrix< double > > | numerical::detail::hermitian_system (const matrix< double > &a) |
The eigenvalues (ascending) and orthonormal eigenvectors of the real symmetric a. | |
| std::pair< vector< double >, matrix< std::complex< double > > > | numerical::detail::hermitian_system (const matrix< std::complex< double > > &a) |
The eigenvalues (ascending) and orthonormal eigenvectors of the complex Hermitian a. | |
| template<typename R , typename T > | |
| matrix< R > | numerical::detail::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: one product. Made Hermitian to the bit where hermitian (every f real). | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::expm (const matrix< T > &a) |
The exponential e^A of a square matrix, as scipy.linalg.expm: scaling and squaring of a Padé approximant, as Al-Mohy and Higham's algorithm (2009): the degree 3, 5, 7, 9 or 13 and the squarings s chosen from ‖A^{2k}‖₁^{1/2k} (exact, A², A⁴ and A⁶ formed, A⁸ and A¹⁰ where needed) and the approximant's backward error bound (ℓ), then r(2⁻ˢ A) squared s times; an upper triangular A's diagonal and first superdiagonal written exactly at each squaring. A Hermitian A (to the bit) of order hermitian_expm_least or more: V e^Λ Vᴴ from its eigendecomposition. | |
| taylor_plan | numerical::detail::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, ℓ 2): the m and s of least cost m s for t A of 1-norm norm and columns columns of B. Where condition 3.13 holds (‖tA‖₁ small for the columns), s = ⌈‖tA‖₁ / θ_m⌉; else s = ⌈α_p / θ_m⌉ over the p from 2 to 8 and the m from p (p − 1) − 1, α_p = max(d_p, d_{p+1}), d_p power_norm(p) (an estimate of ‖(tA)ᵖ‖₁^{1/p}), at least one step. | |
| template<typename T > | |
| double | numerical::detail::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‖∞). | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::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 3.2 (2011). A less μ I, μ its trace over n; then s steps, each m terms at most of the Taylor series of e^{tA/s} on the step's start, each term one product of A by the n × k block (the matrix product kernel), the series stopped where its last two terms fall under the unit roundoff of the sum; each step times e^{tμ/s}. m and s the least products for the unit roundoff (detail::plan_taylor), the norms of A's powers estimated through products with vectors (detail::one_norm_estimate). Some m s products of n² k where e^{tA} takes n³ several times: the few columns' case. | |
| template<typename T > | |
| matrix< T > | numerical::detail::adjoint_of (const matrix< T > &m) |
Mᴴ: the transpose, conjugated. | |
| std::size_t | numerical::detail::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: 2 where the entry below its diagonal is nonzero (a real Schur form's pair). | |
| std::size_t | numerical::detail::schur_block (const buffer< std::complex< double > > &, std::size_t, std::size_t) |
| The same for a complex Schur form, triangular: 1. | |
| template<typename T > | |
| void | numerical::detail::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 blocks r (row stride ldr) and s (row stride lds): the Kronecker system of order rows · cols by Gaussian elimination with complete pivoting, a pivot under smin taken as smin, as LAPACK's dlasy2 perturbs one (the eigenvalues of R and −S close). | |
| template<typename T > | |
| void | numerical::detail::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 triangular (complex) r (m × m) and s (n × n), as LAPACK's trsyl (no transposes, +): by blocks of columns of S from the first, each first relieved of the columns solved before it through the matrix product, then by blocks of rows of R from the last, each a system of at most four unknowns (small_sylvester_block), R and −S close in an eigenvalue perturbing its pivot as trsyl does. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::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 Bartels and Stewart's method, the Schur forms A = U R Uᴴ and B = V S Vᴴ (schur_decomposition), R Y + Y S = Uᴴ Q V solved by blocks (LAPACK's trsyl), then X = U Y Vᴴ. Real throughout for real operands (R and S quasi-triangular), complex where any is. Where A and −B share an eigenvalue the equation has no unique solution: a pivot below the rounding of the forms is perturbed, as LAPACK's, and the answer grows accordingly. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::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.solve_continuous_lyapunov: one Schur form A = U R Uᴴ, whose adjoint Aᴴ = U Rᴴ Uᴴ it also gives (solve_sylvester with b = Aᴴ formed a second one, twice the time), then R Y + Y Rᴴ = Uᴴ Q U and X = U Y Uᴴ. Rᴴ is lower triangular: with J the order reversed, J Rᴴ J is upper (quasi-)triangular, so R (Y J) + (Y J)(J Rᴴ J) = (Uᴴ Q U) J is solved by blocks as LAPACK's trsyl. Real throughout for real operands, complex where either is. | |
| double | numerical::detail::frechet_bound (std::size_t m) |
‖A‖₁ bounds of the [m/m] Padé approximants of the Fréchet derivative of the exponential, for m from 1 to 20, as Al-Mohy and Higham's table 6.1 (2009) and SciPy's ell_table_61. | |
| template<typename T > | |
| void | numerical::detail::add_scaled (buffer< T > &into, const buffer< T > &term, double coefficient) |
into += coefficient · term over the n × n buffers. | |
| template<typename T > | |
| buffer< T > | numerical::detail::both_products (const buffer< T > &p, const buffer< T > &q, std::size_t n) |
P Q + Q P of n × n buffers. | |
| template<typename T > | |
| std::pair< buffer< T >, buffer< T > > | numerical::detail::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 algorithm 6.4 (2009) and SciPy's expm_frechet_algo_64: U, V and their derivatives Lu, Lv along e (M₂ = A E + E A, M₄ = A² M₂ + M₂ A², M₆ = A⁴ M₂ + M₄ A², M₈ = A⁴ M₄ + M₄ A⁴), each sum from its highest term, then R = (V − U)⁻¹ (U + V) and L = (V − U)⁻¹ (Lu + Lv + (Lu − Lv) R) by one LU factorisation; for m = 13, a and e already scaled, A⁶'s nesting as pade_approximant's. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| std::pair< matrix< T >, matrix< T > > | numerical::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.expm_frechet: by default Al-Mohy and Higham's algorithm 6.4 (2009) as SciPy's: the [m/m] Padé approximant (m 3, 5, 7 or 9) where ‖A‖₁ is within its bound, else m = 13 on 2⁻ˢ A and 2⁻ˢ E, s = ⌈log₂(‖A‖₁ / 4.74)⌉, then s squarings L ← R L + L R, R ← R²; or the exponential of [[A, E], [0, A]], whose blocks are e^A and L(A, E). | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| double | numerical::expm_cond (const matrix< T > &a) |
The relative condition number of the exponential at a in the Frobenius norm, as scipy.linalg.expm_cond: ‖K‖₂ ‖A‖_F / ‖e^A‖_F, K the n² × n² Kronecker form of the Fréchet derivative (its column i n + j the column-major vec of L(A, eᵢ eⱼᵀ)), ‖K‖₂ its largest singular value. An empty matrix's is 0. | |
| template<typename T > | |
| void | numerical::detail::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, its diagonal blocks already in r, column of blocks by column, each block row from the last: R_ii X + X R_jj = T_ij − Σ R_ik R_kj (Higham, 1987), between two scalars x = c / (r_ii + r_jj), a zero over a zero taken as 0 and a nonzero over a zero as infinite (no root there, as SciPy answers), else the small Sylvester system of the blocks (small_sylvester_block; principal roots of eigenvalues off the negative axis never sum to 0 there). | |
| std::optional< matrix< double > > | numerical::detail::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), or none where a has a real eigenvalue below 0 (its principal root complex): a 1 × 1 block's root √t, a 2 × 2 block [θ b; c θ] of eigenvalues θ ± iμ the root α I + (T − θ I) / 2α for α + iβ = √(θ + iμ). | |
| double | numerical::detail::scalar_sqrt (double x) |
√x of a real x at least 0. | |
| std::complex< double > | numerical::detail::scalar_sqrt (const std::complex< double > &z) |
csqrt's √z, exact on the axes as NumPy's and SciPy's. | |
| template<typename T > | |
| buffer< T > | numerical::detail::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 T is real), entry by entry: √t_ii on the diagonal, the rest by square_root_columns. | |
| template<typename T > | |
| buffer< T > | numerical::detail::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 T is real): pointwise_square_root up to square_root_block or where a diagonal entry is 0 (a zero over a zero taken as 0 there); else by blocks (Deadman, Higham and Ralha, 2013, as SciPy's _sqrtm_triu): each diagonal block's root entry by entry, then each block column from the diagonal up, R_ii X + X R_jj = T_ij − R_i,(i+1…j−1) R_(i+1…j−1),j, the product by gemm and the Sylvester equation by triangular_sylvester (R_ii + R_jj has no eigenvalue at 0: principal roots of nonzero eigenvalues). | |
| matrix< std::complex< double > > | numerical::detail::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::pair< matrix< std::complex< double > >, matrix< std::complex< double > > > | numerical::detail::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) triangularised by a unitary rotation of its two rows and columns, the columns of z turning with it; a real eigenvalue's diagonal entry kept exactly real. | |
| template<typename T > | |
| bool | numerical::detail::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, so an infinite entry of the root reaches no other). | |
| template<typename T > | |
| matrix< std::complex< double > > | numerical::detail::hermitian_root (const matrix< T > &a) |
The principal square root of the Hermitian a, V √Λ Vᴴ: Hermitian where no eigenvalue is below 0. | |
| matrix< std::complex< double > > | numerical::sqrtm (const matrix< std::complex< double > > &a) |
The principal square root X of a complex square matrix (X² = A, its eigenvalues of nonnegative real part), as scipy.linalg.sqrtm: by the Schur method, A = Z T Zᴴ, the triangular R² = T column by column (Björck and Hammarling), X = Z R Zᴴ. Where A has no square root (a zero eigenvalue in a Jordan block) the entries that would need one are infinite, as SciPy's. | |
| matrix< std::complex< double > > | numerical::complex_sqrtm (const matrix< double > &a) |
The complex principal square root of a real square matrix, as scipy.linalg.sqrtm answers one with a real eigenvalue below 0: from its real Schur form made complex (SciPy's rsf2csf), its real eigenvalues exactly real, so each root of one below 0 is +i √|λ|. | |
| matrix< double > | numerical::sqrtm (const matrix< double > &a) |
The real principal square root of a real square matrix, as scipy.linalg.sqrtm answers one: in real arithmetic on its real Schur form (Higham, 1987), a complex pair's block by its own real root. | |
| std::complex< double > | numerical::detail::rounding_direction (std::size_t place) |
A direction of unit modulus for the rounding of entry place of an estimate's model, fixed and varying from one entry to the next. | |
| void | numerical::detail::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 | numerical::detail::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 diagonal, relative to its largest entry: the recurrence run again on the error alone, from its diagonal blocks' errors (error, n × n, its diagonal blocks set: circle_error for a cluster, f's rounding for one eigenvalue), each entry above them with its rounding as a source, ε (Σ |F_ik| |T_kj| + |T_ik| |F_kj|) over the products that form it (the moduli as |re| + |im|), in a direction of its own (rounding_direction). Where clusters are far from normal, the separation of their blocks falls far below their eigenvalues' gaps and the recurrence grows the diagonal blocks' errors and its own roundings by its inverse: eight clusters of 32 at order 256 (spread 0.01, T's strict upper triangle 0.3 N(0, 1)), integrals right to 10⁻¹¹ each and f(T) wrong by 10⁻⁴ above them (by 10⁻⁶ from the roundings alone, a recurrence in 30 digits from the same blocks shows), where SciPy's estimate, ε ‖strict upper T‖₁ over the smallest gap, said 7·10⁻¹³; this one says 2·10⁻⁴. | |
| double | numerical::detail::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‖₁ / δ)), δ smallest (ε where 0). | |
| std::pair< matrix< std::complex< double > >, matrix< std::complex< double > > > | numerical::detail::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). | |
| std::pair< matrix< std::complex< double > >, matrix< std::complex< double > > > | numerical::detail::function_schur_form (const matrix< std::complex< double > > &a) |
| A complex matrix's Schur form. | |
| funm_result | numerical::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.linalg.funm completes it: Parlett's recurrence (Golub and Van Loan's algorithm 11.1.1) on F, a superdiagonal at a time, F(i, j) = (T(i, j) (F(j, j) − F(i, i)) + Σ T(i, k) F(k, j) − Σ F(i, k) T(k, j)) / (T(j, j) − T(i, i)) (not divided where two diagonal entries are equal, as SciPy's, the error estimate then 1), then Z F Zᴴ. The estimate: the recurrence run again on its roundings (detail::recurrence_error), or SciPy's where larger, δ the smallest |T(j, j) − T(i, i)| met (or |T(0, 0)|, ε where 0); SciPy's alone said 6·10⁻¹⁴ of an error of 2·10⁻¹¹ (order 16, eigenvalues 0.27 apart, T's strict upper triangle 5 N(0, 1)). | |
| std::pair< funm_result, double > | numerical::detail::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, which reads 1 wherever T(0, 0) is 0): what funm weighs its attempts by. | |
| std::vector< std::size_t > | numerical::detail::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 member's place. | |
| double | numerical::detail::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, Davies and Higham's bound, relative here). Parlett's recurrence divides by the gaps between clusters: under it, gaps of 0.003 to 0.03 and an evenly spread spectrum lost 10⁶ to 10¹³ ε; a cluster's Cauchy integral takes as many points as its estimate asks (contour_points_most), a random matrix's whole spectrum among them. | |
| bool | numerical::detail::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 eigenvalue nearer its centre than every other one (no circle about it could keep the others out else), read from the values alone, before gather_clusters reorders a Schur form for them: a random matrix's spectrum chains into clusters no circle separates, whose reordering funm then gave up for the finer share (order 256: 12.7 of 41 ms). values not empty. | |
| std::vector< std::complex< double > > | numerical::detail::diagonal_of (const matrix< std::complex< double > > &t) |
The diagonal of the square t. | |
| cluster_circles | numerical::detail::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 cluster of two or more, its radius the cluster's spread plus a margin as wide as the spread, the cluster bound, or the block's coupling (its largest entry above the diagonal: the resolvent's terms ‖N‖ᵏ / rᵏ⁺¹ then stay near 1/r and cancel without loss), half the way to the nearest other eigenvalue at most. | |
| std::vector< std::size_t > | numerical::detail::starting_points (const cluster_circles &circles) |
The points to start each circle of circles about a cluster of two or more with: contour_points, funm doubling those its integral's estimate asks more of. | |
| std::vector< std::complex< double > > | numerical::detail::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, after one another. | |
| bool | numerical::detail::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, within cluster_bound) is a run of the diagonal, each in turn moved to the first place past those placed. | |
| void | numerical::detail::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 circle (centre, radius), f(z_k) (z_k − c) (z_k I − T_b)⁻¹, T_b the p × p block of t from first and f(z_k) the next of images in turn: the trapezoidal rule's terms of Cauchy's integral (1/2πi) ∮ f(z) (zI − T_b)⁻¹ dz (Hale, Higham and Trefethen, 2008), times the count. | |
| std::vector< std::complex< double > > | numerical::detail::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, radius), in turn. | |
| double | numerical::detail::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, half (each divided by its count here), and its own estimate, relative to the integral's largest entry: the two rules' largest difference, the diagonal's against diagonal (f at the cluster's eigenvalues: a singularity of f in the disk breaks it), and the sum's rounding, ε times its terms' moduli (moduli, summed over the count points). A cluster far from normal has resolvents on its circle whose terms cancel to an integral orders below them (eight clusters of 32 at order 256: an integral wrong by 2·10⁻⁴ where the rules agreed to 4·10⁻¹¹); more points do not bring those digits back. | |
| buffer< std::complex< double > > | numerical::detail::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 rules' difference (whole − half, a function of the block as its integral's error is), and its sum's rounding, ε times its terms' moduli (moduli, summed over the count points), each entry in a direction of its own. whole and half as circle_integral leaves them (p × p). | |
| std::tuple< buffer< std::complex< double > >, double, double > | numerical::detail::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 recurrence of Davies and Higham's Schur–Parlett algorithm, a block superdiagonal at a time: T_ii X_ij − X_ij T_jj = X_ii T_ij − T_ij X_jj + Σ (X_ik T_kj − T_ik X_kj) + S_ij, a triangular Sylvester equation each, the clusters as runs of t's diagonal (starts, each run's first place, then n), and S sources (n × n), or none where null. | |
| std::tuple< buffer< std::complex< double > >, double, std::vector< double > > | numerical::detail::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, f at the eigenvalues then at each cluster's circle (circles_of), counts points each: each cluster's block by its integral (add_circle_terms, its even points' rule beside for the estimate, circle_integral), the rest by assembled_function. | |
| funm_result | numerical::detail::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 (no f(A) then, whatever the circles gave), and the circles' estimates contours. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| funm_plan | numerical::plan_funm (const matrix< T > &a) |
The funm_plan of a: f is then wanted at its points, and finish_funm completes f(A). | |
| funm_result | numerical::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ᴴ, its estimate ε; where eigenvalues gather, Davies and Higham's Schur–Parlett algorithm with each cluster by Cauchy's integral (detail::clustered_function); else Parlett's recurrence, as SciPy's (funm_from_schur). The estimate ∞ where f at an eigenvalue, or the result, is not finite. | |
| std::vector< std::complex< double > > | numerical::funm_points (const funm_plan &plan) |
The points where finish_funm wants f for plan (not Hermitian) with its circles' counts: its eigenvalues, then each circle's. | |
| funm_plan | numerical::regathered (funm_plan plan, double share) |
plan (not Hermitian) with its eigenvalues gathered anew within share of the largest modulus (or of 1): its Schur form reordered by the finer clusters (the same form, their runs moved), its points the eigenvalues, then detail::contour_points on each circle where clusters remain. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| funm_result | numerical::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 (the eigenvalues, then the circles' where eigenvalues gather) returning one value each, then finish_funm. f must be analytic on each circle's disk. Accurate where the eigenvalues are well apart or gather tightly; between, Parlett's recurrence (the estimate says how). | |
| double | numerical::detail::unwinding (const std::complex< double > &z) |
ceil((Im z − π) / 2π), the unwinding number of z (SciPy's _unwindk). | |
| std::complex< double > | numerical::detail::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-Mohy and Higham's algorithm 2, 2012): (a − 1) / Π (1 + a^(1/2^j)), a first square root taken where arg a ≥ π/2. | |
| std::complex< double > | numerical::detail::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]], as SciPy's _fractional_power_superdiag_entry (Higham and Lin's equation 5.5, 2011). | |
| std::complex< double > | numerical::detail::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]], as SciPy's _logm_superdiag_entry. | |
| double | numerical::detail::briggs (double a, std::size_t k) |
briggs of a real a above 0: (a − 1) / Π (1 + a^(1/2^j)), for k = 1 too (where √a − 1 would cancel). | |
| double | numerical::detail::fractional_power_superdiagonal (double l1, double l2, double t12, double p) |
fractional_power_superdiagonal of real l1 and l2 above 0 (the unwinding number 0). | |
| double | numerical::detail::log_superdiagonal (double l1, double l2, double t12) |
log_superdiagonal of real l1 and l2 above 0 (the unwinding number 0). | |
| double | numerical::detail::scalar_log (double x) |
log x of a real x above 0. | |
| std::complex< double > | numerical::detail::scalar_log (const std::complex< double > &z) |
complex_log of z. | |
| bool | numerical::detail::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 below 0, and its zeros taken as 10⁻²⁰ (force_nonsingular). | |
| bool | numerical::detail::principal_branch (const buffer< std::complex< double > > &t, std::size_t n) |
Whether log has its principal branch at every diagonal entry of t (none real and at most 0). | |
| template<typename T > | |
| std::tuple< buffer< T >, std::size_t, std::size_t > | numerical::detail::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, as SciPy's _inverse_squaring_helper: s square roots of T until T − I is small enough for the [m/m] Padé approximant whose bounds are theta (log(I + X)'s, or (I − X)ᵗ's; m from 1 to 7), the norms ‖(T − I)ᵖ‖₁^(1/p) exact; R = T − I with its diagonal and superdiagonal recomputed without cancellation where the principal branch exists. | |
| template<typename T > | |
| buffer< T > | numerical::detail::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, s and m by inverse_squaring, U = 2ˢ Σ αₖ (I + βₖ R)⁻¹ R (the [m/m] Padé approximant as the partial fractions of m-point Gauss–Legendre quadrature on [0, 1], SciPy's nodes and weights), then the diagonal log λᵢ and the superdiagonal recomputed exactly where the principal branch exists. | |
| template<typename T > | |
| std::pair< bool, bool > | numerical::detail::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 diagonal entry replaced by 10⁻²⁰. | |
| const matrix< std::complex< double > > & | numerical::detail::as_complex (const matrix< std::complex< double > > &a) |
a itself: already complex. | |
| matrix< std::complex< double > > | numerical::detail::as_complex (const matrix< double > &a) |
a's entries as complex numbers. | |
| std::complex< double > | numerical::detail::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). | |
| double | numerical::detail::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_constant (Higham and Lin, 2011, equation 4.1). | |
| buffer< std::complex< double > > | numerical::detail::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: its continued fraction from the bottom, Y = c₂ₘ X, then Y = (I + Y)⁻¹ cⱼ X for j = 2m − 1, …, 1, and I + Y. | |
| buffer< std::complex< double > > | numerical::detail::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_power_triu (Higham and Lin's Schur–Padé algorithm, 2013): a diagonal T entry by entry; else R = T^(1/2ˢ) − I and m by inverse_squaring with the bounds of (I − X)ᵗ, the [m/m] Padé approximant at −R, then s squarings. Where the principal branch exists, the diagonal λᵢ^(t/2ⁱ) and the superdiagonal (fractional_power_superdiagonal) are written exactly after each squaring, as Higham and Lin's algorithm 5.1 does (SciPy writes them before the first squaring only). | |
| buffer< std::complex< double > > | numerical::detail::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, Z a Hermitian A's eigenvectors): its diagonal's principal powers, above them each entry times the divided difference of x^t between its diagonal entries (fractional_power_superdiagonal), Daleckii and Krein's first order, exact to the square of the rounding. | |
| buffer< double > | numerical::detail::nearly_diagonal_power (const matrix< double > &similar, double p) |
nearly_diagonal_power of the upper triangle of a real similar whose diagonal is positive: real. | |
| template<typename T > | |
| hermitian_similarity< T > | numerical::detail::similarity_of (const matrix< T > &a) |
hermitian_similarity of the Hermitian a. | |
| buffer< std::complex< double > > | numerical::detail::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 rounding above the diagonal kept as a Schur form keeps it (Λ alone erred two to five times more), its diagonal taken real (a negative eigenvalue's power the principal value's), T^t to first order in that rounding (nearly_diagonal_power, in place of the Padé steps: order 200 35 → 9 ms, the same errors). | |
| matrix< std::complex< double > > | numerical::detail::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 V (similar_power), the products real: T^t real where T's diagonal is positive (nearly_diagonal_power's in real arithmetic), else its real and imaginary parts apart. | |
| matrix< std::complex< double > > | numerical::detail::hermitian_remainder_power (const hermitian_similarity< std::complex< double > > &s, double t) |
A^t (−1 < t < 1) of a complex Hermitian A not triangular from s: Z T^t Zᴴ, T the upper triangle of Zᴴ A Z (similar_power). | |
| template<typename T > | |
| std::optional< matrix< std::complex< double > > > | numerical::detail::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 directly, else Z T^t Zᴴ; none where the triangular form has a zero on its diagonal. An exactly Hermitian A not triangular by its eigenvectors (hermitian_remainder_power); a diagonal one's diagonal taken real, so that a negative eigenvalue's power is the principal value's. | |
| template<typename T > | |
| matrix< T > | numerical::detail::integer_power (const matrix< T > &a, double e) |
a to the integer power e (a finite whole number) by repeated squaring, as numpy.linalg.matrix_power: the identity for 0, the inverse's powers for e < 0. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< std::complex< double > > | numerical::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, an exactly Hermitian (real symmetric) A by one eigendecomposition, V Λᵖ Vᴴ (Hermitian where no eigenvalue is below 0); else A^a A^b with a the floor or the ceiling of p, chosen by A's condition as SciPy chooses it, and A^b (|b| < 1) by Higham and Lin's Schur–Padé algorithm (2013) on the Schur form. Where the triangular form has a zero on its diagonal (A singular), a positive p falls back to funm of x^(p − ⌊p⌋), as SciPy's; a negative one has no answer and is refused (SciPy returns a matrix of NaN). Complex: a real matrix's power may be complex. | |
| template<typename T > | |
| logm_result | numerical::detail::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 entries taken as 10⁻²⁰ (force_nonsingular). | |
| bool | numerical::detail::nonnegative_diagonal (const matrix< double > &t) |
Whether no diagonal entry of t is below 0. | |
| logm_result | numerical::detail::general_logm (const matrix< std::complex< double > > &a) |
| logm of a complex matrix past its Hermitian path: an upper triangular one directly, else its Schur form's. | |
| logm_result | numerical::detail::general_logm (const matrix< double > &a) |
logm of a real matrix past its Hermitian path: in real arithmetic where its real Schur form (or the matrix, upper triangular) is triangular with no diagonal entry below 0, as SciPy's (_logm, _logm_triu), else in the complex form (rsf2csf). | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| logm_result | numerical::logm (const matrix< T > &a) |
The principal logarithm of a square matrix, as scipy.linalg.logm: an upper triangular A directly, else its Schur form A = Z T Zᴴ and Z log(T) Zᴴ: in real arithmetic where A is real and its real Schur form triangular with no eigenvalue below 0, else in the complex form (the real one made complex), as SciPy's. log T by Al-Mohy and Higham's inverse scaling and squaring (2012) as SciPy's _logm_triu, the norms that choose the square roots and the degree exact where SciPy estimates them. A zero eigenvalue is taken as 10⁻²⁰ (no logarithm exists there), as SciPy's, and reported; complex, SciPy's real part where A is real and it is negligible. | |
Variables | |
| constexpr double | numerical::detail::divided_exponentials_past {64.0} |
The half gap past which exact_triangular_bands divides the difference of the exponentials by the gap: one exponential then outweighs the other by e¹²⁸, and the difference loses nothing, where the product e^{half sum} sinch(half gap) overflows sinh while the exponential underflows (a gap past about 1420). | |
| constexpr std::size_t | numerical::hermitian_expm_least {64} |
| The order from which expm of a Hermitian matrix takes its eigendecomposition (below, the Padé path is faster: an order-32 symmetric_eigen costs more than the few products of a small Padé degree). | |
| constexpr std::array< taylor_bound, 35 > | numerical::detail::taylor_bounds |
The table of taylor_bound, m ascending. | |
| constexpr std::size_t | numerical::detail::square_root_block {64} |
The order of the diagonal blocks of triangular_square_root (SciPy's _sqrtm_triu's). | |
| constexpr std::size_t | numerical::detail::upper_block_product_least {64} |
The blocks' size (rows × columns) from which solve_upper_blocks forms a block's terms by gemm: below it, a call costs more than its sums (a random matrix's clusters, most of one eigenvalue). | |
| constexpr double | numerical::detail::cluster_share {0.1} |
| The share of the largest modulus (or of 1) within which eigenvalues gather (cluster_bound): Davies and Higham's 0.1, relative here. | |
| constexpr double | numerical::detail::cluster_share_fine {0.01} |
| The finer share funm falls back to where clusters at cluster_share leave its estimate past funm_fallback_error, or where, chained into irregular shapes (a random matrix's spectrum), a cluster's circle about its centre reaches another's eigenvalues, and no count of points helps (order 192: error 1.4). | |
| constexpr double | numerical::detail::funm_fallback_error {1e3 * std::numeric_limits<double>::epsilon()} |
| The estimate past which funm tries the finer clusters (SciPy reports a result past it inaccurate). | |
| constexpr std::size_t | numerical::detail::contour_points {64} |
| The trapezoidal rule's points on each circle of Cauchy's integral. | |
| constexpr std::size_t | numerical::detail::contour_points_most {4096} |
| The most points on one cluster's circle: funm doubles them from contour_points while the integrals' estimate passes contour_tolerance and halves at least (the trapezoidal rule converges geometrically on a circle: a cluster of 128 eigenvalues of a random matrix took 512 to 25 ε). | |
| constexpr double | numerical::detail::contour_tolerance {32.0 * std::numeric_limits<double>::epsilon()} |
| The integrals' estimate below which funm takes no more points. | |
| constexpr std::size_t | numerical::detail::funm_batch_elements {std::size_t {1} << 20} |
The elements of one batch of add_circle_terms's points (their p × p inverses, and as many of their shifted blocks): 2²⁰, 16 MiB each, and at least one point. | |
| constexpr std::array< double, 8 > | numerical::detail::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} |
The bounds θ_m of the [m/m] Padé approximant of log(I + X) (Al-Mohy and Higham's table 2.1, 2012), m from 1 to 7. | |
| constexpr std::array< double, 8 > | numerical::detail::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} |
The bounds θ_m of the [m/m] Padé approximant of (I − X)ᵗ (Higham and Lin's table 3.1, 2013, as SciPy's _remainder_matrix_power_triu), m from 1 to 7. | |
Functions of a square matrix and the matrix equations solved through Schur forms: the exponential, by scaling and squaring of a Padé approximant; the principal square root, by the Schur method; the Sylvester equation A X + X B = Q, as Bartels and Stewart.
Definition in file matrix_functions.hpp.