|
NumericAL
A header-only C++20 lexer built on REAL
|
Structured systems: banded matrices, in LAPACK's diagonal-ordered storage, the general band by its LU factorisation with partial pivoting (gbsv, gtsv for three diagonals), the Hermitian positive-definite band by its Cholesky factor (pbsv, ptsv's L D Lᴴ for three); Toeplitz matrices by Levinson's recursion; circulant matrices by the Fourier transform. And the structured matrices themselves, as scipy.linalg forms them: Toeplitz, circulant, Hankel, block diagonal.
More...
#include <algorithm>#include <cmath>#include <complex>#include <concepts>#include <cstddef>#include <limits>#include <optional>#include <string>#include <type_traits>#include <utility>#include <vector>#include "factorizations.hpp"#include "fft.hpp"Go to the source code of this file.
Classes | |
| struct | numerical::detail::band_storage< T > |
A band's entries in LAPACK's column-major band storage: AB(i, j) (from 1) at (i − 1) + (j − 1) ldab. More... | |
| struct | numerical::conditioned_solution< T > |
| A solution and the reciprocal condition number of its system (solve_banded_conditioned). More... | |
Namespaces | |
| namespace | numerical |
| The NumericAL public API. | |
| namespace | numerical::detail |
Functions | |
| template<typename T > | |
| void | numerical::detail::band_lu (band_storage< T > &ab, std::size_t n, std::size_t kl, std::size_t ku, std::vector< std::size_t > &pivots) |
The LU factorisation with partial pivoting of the n × n band of kl subdiagonals and ku superdiagonals in ab (2 kl + ku + 1 rows, the band from row kl + 1, the rows above for the fill the interchanges bring), in place, as LAPACK's gbtf2: each column's pivot the entry of largest pivot_magnitude (|Re| + |Im| for complex numbers, as izamax; the first of them) within the band below the diagonal, its row swapped to the reach of the rows it touches, the multipliers below and the rank-1 update right of it. pivots (from 1) the rows swapped. | |
| template<typename T > | |
| void | numerical::detail::band_lu_solve (band_storage< T > &ab, std::size_t n, std::size_t kl, std::size_t ku, const std::vector< std::size_t > &pivots, buffer< T > &b, std::size_t k) |
The k right-hand sides of b (n × k, row-major) solved in place against band_lu's factors, as LAPACK's gbtrs (no transpose): the interchanges and L column by column, then U, a band of kl + ku superdiagonals, by back substitution. | |
| template<typename T > | |
| void | numerical::detail::band_lu_solve_adjoint (band_storage< T > &ab, std::size_t n, std::size_t kl, std::size_t ku, const std::vector< std::size_t > &pivots, T *x) |
One right-hand side x (n entries) solved in place against the adjoint of band_lu's factors, Aᴴ x = b, as LAPACK's gbtrs (conjugate transpose): Uᴴ, a band of kl + ku subdiagonals, by forward substitution, then Lᴴ and the interchanges column by column from the last. | |
| template<typename T > | |
| void | numerical::detail::band_cholesky (band_storage< T > &ab, std::size_t n, std::size_t kd, const std::string &name) |
The Cholesky factor U (A = Uᴴ U) of the Hermitian positive-definite band of kd superdiagonals in ab (kd + 1 rows, AB(kd + 1 + i − j, j) = A(i, j)), in place, as LAPACK's pbtf2 (upper): each diagonal entry's square root, the row right of it scaled, the trailing band less its outer product. | |
| template<typename T > | |
| void | numerical::detail::band_cholesky_solve (band_storage< T > &ab, std::size_t n, std::size_t kd, buffer< T > &b, std::size_t k) |
The k right-hand sides of b (n × k, row-major) solved in place against band_cholesky's U, as LAPACK's pbtrs: Uᴴ y = b forward, then U x = y back. | |
| template<typename T > | |
| void | numerical::detail::tridiagonal_solve (buffer< T > &dl, buffer< T > &d, buffer< T > &du, buffer< T > &b, std::size_t n, std::size_t k) |
The k right-hand sides of b (n × k, row-major) solved in place against the tridiagonal matrix of subdiagonal dl, diagonal d and superdiagonal du (n − 1, n, n − 1 entries, overwritten), as LAPACK's gtsv, which scipy.linalg.solve_banded calls for one sub- and one superdiagonal: Gaussian elimination with partial pivoting, row i + 1 exchanged with row i where its subdiagonal entry is the larger (dl then holding the second superdiagonal the exchange brings), then back substitution. | |
| double | numerical::detail::positive_pivot_step (double d, double &e, double next) |
pttrf's step for a real tridiagonal: e ← e / d, | |
| double | numerical::detail::positive_pivot_step (double d, std::complex< double > &e, double next) |
zpttrf's step for a complex one: e ← e / d by parts, | |
| void | numerical::detail::positive_back_substitution (const buffer< double > &d, const buffer< double > &e, buffer< double > &b, std::size_t n, std::size_t k) |
dptts2's last two passes, after L: D and Lᵀ in one, b ← b / d − b_next e from the end. | |
| void | numerical::detail::positive_back_substitution (const buffer< double > &d, const buffer< std::complex< double > > &e, buffer< std::complex< double > > &b, std::size_t n, std::size_t k) |
zptts2's (lower): D, then Lᴴ, b ← b − b_next conj(e) from the end. | |
| template<typename T > | |
| void | numerical::detail::positive_tridiagonal_solve (buffer< double > &d, buffer< T > &e, buffer< T > &b, std::size_t n, std::size_t k) |
The k right-hand sides of b (n × k, row-major) solved in place against the Hermitian positive definite tridiagonal matrix of real diagonal d and subdiagonal e (n and n − 1 entries, overwritten), as LAPACK's ptsv, which scipy.linalg.solveh_banded calls for one off-diagonal: A = L D Lᴴ (pttrf, e becoming L's subdiagonal), then L, D and Lᴴ in turn (ptts2). | |
| double | numerical::detail::taken_as (const std::complex< double > &z, std::type_identity< double >) |
| A complex value as a real result takes it: its real part (the imaginary part rounding's alone). | |
| std::complex< double > | numerical::detail::taken_as (const std::complex< double > &z, std::type_identity< std::complex< double > >) |
| A complex value as a complex result takes it: whole. | |
| template<typename T > | |
| void | numerical::detail::require_band (const matrix< T > &ab, std::size_t rows, const matrix< T > &b, const std::string &name) |
Refuses a band that is not rows × n and right-hand sides not of n rows. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::solve_banded (std::size_t lower, std::size_t upper, const matrix< T > &ab, const matrix< T > &b) |
The solution X of A X = B for the n × n band A of lower subdiagonals and upper superdiagonals, given as scipy.linalg.solve_banded takes it: ab of lower + upper + 1 rows and n columns, ab[upper + i − j][j] = A(i, j) (its corners, outside the matrix, not read). By the LU factorisation with partial pivoting in LAPACK's band storage (gbsv): O(n · lower · (lower + upper)) operations; one sub- and one superdiagonal by detail::tridiagonal_solve (gtsv), as SciPy. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| conditioned_solution< T > | numerical::solve_banded_conditioned (std::size_t lower, std::size_t upper, const matrix< T > &ab, const matrix< T > &b) |
solve_banded with the reciprocal condition number of the band, as scipy.linalg.solve takes them from LAPACK's gbsv and gbcon: the band's LU factorisation for any band (gtsv's partial pivoting for three diagonals), ‖A‖₁ its largest column sum of moduli, ‖A⁻¹‖₁ estimated from the factors (Hager's method, a few solves of O(n (lower + upper)) each), so within a small factor of the exact. | |
| template<typename T > | |
| band_storage< T > | numerical::detail::upper_band (const matrix< T > &ab, bool lower_form) |
The upper band of kd superdiagonals of the band ab in either of scipy.linalg's forms (solveh_banded), AB(kd + 1 + i − j, j) = A(i, j) for i ≤ j, as band_cholesky takes it. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::solveh_banded (const matrix< T > &ab, const matrix< T > &b, bool lower_form=false) |
The solution X of A X = B for the Hermitian positive-definite band A, given as scipy.linalg.solveh_banded takes it: ab of kd + 1 rows and n columns, its upper form ab[kd + i − j][j] = A(i, j) for i ≤ j or, lower_form, its lower ab[i − j][j] = A(i, j) for i ≥ j (the diagonal's imaginary part, and the corners, not read). By the band's Cholesky factor (LAPACK's pbsv); one off-diagonal by detail::positive_tridiagonal_solve (ptsv), as SciPy. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::cholesky_banded (const matrix< T > &ab, bool lower_form=false) |
The Cholesky factor of the Hermitian positive-definite band ab, as scipy.linalg.cholesky_banded (LAPACK's pbtrf): in ab's own form, U (A = Uᴴ U) in the upper one, L = Uᴴ (A = L Lᴴ) with lower_form, the corners outside the band as ab has them. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::cho_solve_banded (const matrix< T > &cb, const matrix< T > &b, bool lower_form=false) |
The solution X of A X = B from cholesky_banded's factor cb of A, as scipy.linalg.cho_solve_banded((cb, lower_form), b) (LAPACK's pbtrs). | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::solve_toeplitz (const vector< T > &c, const vector< T > &r, const matrix< T > &b) |
The solution X of T X = B for the n × n Toeplitz T of first column c and first row r (T(i, j) = c[i − j] for i ≥ j, r[j − i] above; r[0] not read), as scipy.linalg.solve_toeplitz: Levinson's recursion as Numerical Recipes' toeplz (which SciPy's follows), every right-hand side at once, O(n²) operations a column: the solutions of the leading principal systems grown by one row at a time, the forward and backward vectors g and h beside them. It needs every leading principal minor nonsingular (not only T), and like all Levinson recursions it is stable for a well-conditioned symmetric positive definite T and may lose accuracy otherwise. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| matrix< T > | numerical::solve_circulant (const vector< T > &c, const matrix< T > &b, bool least_squares=false, std::optional< double > tol=std::nullopt) |
The solution X of C X = B for the n × n circulant C of first column c (C(i, j) = c[(i − j) mod n]), as scipy.linalg.solve_circulant: the Fourier transform diagonalises it, X = F⁻¹ (F B / F c), O(n log n) a column. An eigenvalue F c of modulus at most tol (by default n ε max |F c|, as numpy.linalg.matrix_rank judges) makes C near singular: refused, or with least_squares its terms left out (the minimum-norm least-squares solution, SciPy's singular="lstsq"). Real c and b give a real X (the transform's real part, as SciPy's). | |
| template<typename T > | |
| matrix< T > | numerical::toeplitz (const vector< T > &c, const vector< T > &r) |
The m × n Toeplitz matrix of first column c (m entries) and first row r (n), as scipy.linalg.toeplitz: T(i, j) = c[i − j] for i ≥ j, r[j − i] above (r[0] not read). | |
| template<typename T > | |
| matrix< T > | numerical::circulant (const vector< T > &c) |
The n × n circulant matrix of first column c, as scipy.linalg.circulant: C(i, j) = c[(i − j) mod n]. | |
| template<typename T > | |
| matrix< T > | numerical::hankel (const vector< T > &c, const vector< T > &r) |
The m × n Hankel matrix of first column c (m entries) and last row r (n), as scipy.linalg.hankel: H(i, j) = c[i + j] while i + j < m, r[i + j − m + 1] past it (r[0] not read). | |
| template<typename T > | |
| matrix< T > | numerical::block_diag (const std::vector< matrix< T > > &blocks) |
The block diagonal matrix of blocks, in order, as scipy.linalg.block_diag: zeros off the blocks. | |
Structured systems: banded matrices, in LAPACK's diagonal-ordered storage, the general band by its LU factorisation with partial pivoting (gbsv, gtsv for three diagonals), the Hermitian positive-definite band by its Cholesky factor (pbsv, ptsv's L D Lᴴ for three); Toeplitz matrices by Levinson's recursion; circulant matrices by the Fourier transform. And the structured matrices themselves, as scipy.linalg forms them: Toeplitz, circulant, Hankel, block diagonal.
Definition in file banded.hpp.