8#ifndef NUMERICAL_BANDED_HPP
9#define NUMERICAL_BANDED_HPP
59 std::vector<std::size_t>& pivots)
61 const std::size_t
kv {
ku +
kl};
64 for (std::size_t j {1}; j <= n; ++j) {
66 for (std::size_t i {1}; i <=
kl; ++i) {
70 const std::size_t
km {std::min(
kl, n - j)};
73 for (std::size_t r {2}; r <=
km + 1; ++r) {
79 pivots[j - 1] =
jp + j - 1;
83 ju = std::max(
ju, std::min(j +
ku +
jp - 1, n));
85 for (std::size_t c {0}; c <=
ju - j; ++c) {
86 std::swap(
ab(
kv +
jp - c, j + c),
ab(
kv + 1 - c, j + c));
89 const T pivot {
ab(
kv + 1, j)};
90 for (std::size_t r {
kv + 2}; r <=
kv + 1 +
km; ++r) {
93 for (std::size_t c {1}; c <=
ju - j; ++c) {
94 const T factor {
ab(
kv + 1 - c, j + c)};
95 for (std::size_t r {1}; r <=
km; ++r) {
96 ab(
kv + 1 - c + r, j + c) -=
ab(
kv + 1 + r, j) * factor;
107 template <
typename T>
112 const std::vector<std::size_t>& pivots,
116 const std::size_t
kd {
ku +
kl + 1};
117 for (std::size_t j {1}; j < n; ++j) {
118 const std::size_t
lm {std::min(
kl, n - j)};
119 const std::size_t l {pivots[j - 1]};
121 std::swap_ranges(b.begin() +
static_cast<std::ptrdiff_t
>((l - 1) * k), b.begin() +
static_cast<std::ptrdiff_t
>(l * k),
122 b.begin() +
static_cast<std::ptrdiff_t
>((j - 1) * k));
124 for (std::size_t r {1}; r <=
lm; ++r) {
128 for (std::size_t j {n}; j >= 1; --j) {
130 for (std::size_t c {0}; c < k; ++c) {
133 const std::size_t first {j >
kl +
ku ? j -
kl -
ku : 1};
134 for (std::size_t i {first}; i < j; ++i) {
145 template <
typename T>
150 const std::vector<std::size_t>& pivots,
153 const std::size_t
kd {
ku +
kl + 1};
154 for (std::size_t j {1}; j <= n; ++j) {
155 const std::size_t first {j >
kl +
ku ? j -
kl -
ku : 1};
156 for (std::size_t i {first}; i < j; ++i) {
161 for (std::size_t j {n}; j-- > 1;) {
162 const std::size_t
lm {std::min(
kl, n - j)};
163 for (std::size_t r {1}; r <=
lm; ++r) {
166 const std::size_t l {pivots[j - 1]};
168 std::swap(x[l - 1], x[j - 1]);
179 template <
typename T>
183 const std::string&
name)
185 for (std::size_t j {1}; j <= n; ++j) {
186 const double ajj {std::real(
ab(
kd + 1, j))};
190 const double root {std::sqrt(
ajj)};
192 const std::size_t
kn {std::min(
kd, n - j)};
193 for (std::size_t c {1}; c <=
kn; ++c) {
196 for (std::size_t c {1}; c <=
kn; ++c) {
198 for (std::size_t r {1}; r <= c; ++r) {
209 template <
typename T>
216 for (std::size_t j {1}; j <= n; ++j) {
217 const std::size_t first {j >
kd ? j -
kd : 1};
218 for (std::size_t i {first}; i < j; ++i) {
222 for (std::size_t c {0}; c < k; ++c) {
226 for (std::size_t j {n}; j >= 1; --j) {
228 for (std::size_t c {0}; c < k; ++c) {
231 const std::size_t first {j >
kd ? j -
kd : 1};
232 for (std::size_t i {first}; i < j; ++i) {
246 template <
typename T>
254 for (std::size_t i {0}; i + 1 < n; ++i) {
255 T*
const here {b.data() + (i * k)};
256 T*
const next {b.data() + ((i + 1) * k)};
262 d[i + 1] = d[i + 1] - (
fact *
du[i]);
263 for (std::size_t c {0}; c < k; ++c) {
264 next[c] = next[c] - (
fact *
here[c]);
278 for (std::size_t c {0}; c < k; ++c) {
281 next[c] =
top - (
fact * next[c]);
285 if (d[n - 1] ==
T {}) {
288 for (std::size_t c {0}; c < k; ++c) {
289 b[((n - 1) * k) + c] = b[((n - 1) * k) + c] / d[n - 1];
292 for (std::size_t c {0}; c < k; ++c) {
293 b[((n - 2) * k) + c] = (b[((n - 2) * k) + c] - (
du[n - 2] * b[((n - 1) * k) + c])) / d[n - 2];
296 for (std::size_t i {n - std::min<std::size_t>(n, 2)}; i-- > 0;) {
297 for (std::size_t c {0}; c < k; ++c) {
298 b[(i * k) + c] = (b[(i * k) + c] - (
du[i] * b[((i + 1) * k) + c]) - (
dl[i] * b[((i + 2) * k) + c])) / d[i];
310 return next - (e *
ei);
315 std::complex<double>& e,
318 const double real {e.real()};
319 const double imag {e.imag()};
320 const double f {real / d};
321 const double g {
imag / d};
322 e = std::complex<double> {f, g};
323 return next - (f * real) - (g *
imag);
333 for (std::size_t c {0}; c < k; ++c) {
334 b[((n - 1) * k) + c] = b[((n - 1) * k) + c] / d[n - 1];
336 for (std::size_t i {n - 1}; i-- > 0;) {
337 for (std::size_t c {0}; c < k; ++c) {
338 b[(i * k) + c] = (b[(i * k) + c] / d[i]) - (b[((i + 1) * k) + c] * e[i]);
345 const buffer<std::complex<double>>& e,
346 buffer<std::complex<double>>& b,
350 for (std::size_t i {0}; i < n; ++i) {
351 for (std::size_t c {0}; c < k; ++c) {
352 b[(i * k) + c] = b[(i * k) + c] / d[i];
355 for (std::size_t i {n - 1}; i-- > 0;) {
356 for (std::size_t c {0}; c < k; ++c) {
357 b[(i * k) + c] = b[(i * k) + c] - (b[((i + 1) * k) + c] * std::conj(e[i]));
369 template <
typename T>
376 for (std::size_t i {0}; i < n; ++i) {
378 throw not_positive_definite_error(
"solveh_banded: the matrix is not positive definite (leading minor " + std::to_string(i + 1) +
")");
384 for (std::size_t i {1}; i < n; ++i) {
385 for (std::size_t c {0}; c < k; ++c) {
386 b[(i * k) + c] = b[(i * k) + c] - (b[((i - 1) * k) + c] * e[i - 1]);
394 std::type_identity<double> )
401 std::type_identity<std::complex<double>> )
407 template <
typename T>
411 const std::string&
name)
413 if (
ab.rows() != rows) {
416 if (b.
rows() !=
ab.cols()) {
417 throw dimension_error(
name +
": the right-hand sides must have as many rows as the band has columns");
435 template <
typename T>
436 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
443 const std::size_t n {
ab.cols()};
444 if (lower == 1 &&
upper == 1 && n > 0) {
448 for (std::size_t j {0}; j < n; ++j) {
451 du[j] =
ab(0, j + 1);
459 const std::size_t ldab {(2 * lower) +
upper + 1};
461 for (std::size_t r {0}; r < lower +
upper + 1; ++r) {
462 for (std::size_t j {0}; j < n; ++j) {
463 work(lower + r + 1, j + 1) =
ab(r, j);
466 std::vector<std::size_t> pivots;
474 template <
typename T>
491 template <
typename T>
492 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
499 const std::size_t n {
ab.cols()};
500 const std::size_t ldab {(2 * lower) +
upper + 1};
502 double one_norm {0.0};
503 for (std::size_t j {0}; j < n; ++j) {
505 for (std::size_t r {
upper > j ?
upper - j : 0}; r < std::min(lower +
upper + 1,
upper + n - j); ++r) {
508 one_norm = std::max(one_norm,
column);
510 for (std::size_t r {0}; r < lower +
upper + 1; ++r) {
511 for (std::size_t j {0}; j < n; ++j) {
512 work(lower + r + 1, j + 1) =
ab(r, j);
515 std::vector<std::size_t> pivots;
534 template <
typename T>
538 const std::size_t
kd {
ab.rows() - 1};
539 const std::size_t n {
ab.cols()};
541 for (std::size_t j {0}; j < n; ++j) {
542 for (std::size_t i {j >
kd ? j -
kd : 0}; i <= j; ++i) {
561 template <
typename T>
562 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
567 if (
ab.rows() == 0) {
568 throw dimension_error(
"solveh_banded: the band must have at least one row");
570 const std::size_t
kd {
ab.rows() - 1};
572 const std::size_t n {
ab.cols()};
573 if (
kd == 1 && n > 0) {
576 for (std::size_t j {0}; j < n; ++j) {
601 template <
typename T>
602 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
606 if (
ab.rows() == 0) {
607 throw dimension_error(
"cholesky_banded: the band must have at least one row");
610 const std::size_t
kd {
ab.rows() - 1};
611 const std::size_t n {
ab.cols()};
615 for (std::size_t j {0}; j < n; ++j) {
616 for (std::size_t i {j >
kd ? j -
kd : 0}; i <= j; ++i) {
621 out[((
kd + i - j) * n) + j] = work(
kd + 1 + i - j, j + 1);
634 template <
typename T>
635 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
640 if (
cb.rows() == 0) {
641 throw dimension_error(
"cho_solve_banded: the band must have at least one row");
663 template <
typename T>
664 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
669 const std::size_t n {c.
size()};
670 if (r.
size() != n || b.
rows() != n) {
671 throw dimension_error(
"solve_toeplitz: c and r must be of b's row count");
674 for (std::size_t i {0}; i < n; ++i) {
676 throw non_finite_error(
"solve_toeplitz: an entry of c or r is infinite or NaN");
679 const std::size_t k {b.
cols()};
684 const auto singular = [] {
return singular_matrix_error(
"solve_toeplitz: singular principal minor"); };
690 for (std::size_t
col {0};
col < k; ++
col) {
701 for (std::size_t m {1}; m < n; ++m) {
704 const bool grows {m + 1 < n};
711 for (std::size_t j {0}; j < m; ++j) {
713 const T other {r[m - j]};
723 for (std::size_t
col {0};
col < k; ++
col) {
726 for (std::size_t j {0}; j < m; ++j) {
728 const T other {r[m - j]};
729 for (std::size_t
col {0};
col < k; ++
col) {
741 for (std::size_t
col {0};
col < k; ++
col) {
744 for (std::size_t j {0}; j < m; ++j) {
745 for (std::size_t
col {0};
col < k; ++
col) {
746 x[(j * k) +
col] -= x[(m * k) +
col] * g[m - 1 - j];
759 for (std::size_t j {0},
last {m - 1}; j <=
last; ++j, --
last) {
788 template <
typename T>
789 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
793 std::optional<double>
tol = std::nullopt)
795 using C = std::complex<double>;
796 const std::size_t n {c.
size()};
797 const std::size_t k {b.
cols()};
799 throw dimension_error(
"solve_circulant: b must have as many rows as c has entries");
802 for (std::size_t i {0}; i < n; ++i) {
804 throw non_finite_error(
"solve_circulant: an entry of c is infinite or NaN");
807 if (n == 0 || k == 0) {
811 double largest {0.0};
813 largest = std::max(largest, std::abs(value));
815 const double threshold {
tol.value_or(largest *
static_cast<double>(n) * std::numeric_limits<double>::epsilon())};
825 for (std::size_t i {0}; i < n; ++i) {
827 for (std::size_t
col {0};
col < k; ++
col) {
833 for (std::size_t e {0}; e < n * k; ++e) {
843 template <
typename T>
847 const std::size_t m {c.
size()};
848 const std::size_t n {r.
size()};
850 for (std::size_t i {0}; i < m; ++i) {
851 for (std::size_t j {0}; j < n; ++j) {
852 out[(i * n) + j] = i >= j ? c[i - j] : r[j - i];
859 template <
typename T>
862 const std::size_t n {c.
size()};
864 for (std::size_t i {0}; i < n; ++i) {
865 for (std::size_t j {0}; j < n; ++j) {
866 out[(i * n) + j] = c[(i + n - j) % n];
876 template <
typename T>
880 const std::size_t m {c.
size()};
881 const std::size_t n {r.
size()};
883 for (std::size_t i {0}; i < m; ++i) {
884 for (std::size_t j {0}; j < n; ++j) {
885 out[(i * n) + j] = i + j < m ? c[i + j] : r[i + j + 1 - m];
892 template <
typename T>
895 std::size_t rows {0};
896 std::size_t cols {0};
898 rows += block.
rows();
899 cols += block.cols();
905 for (std::size_t i {0}; i < block.rows(); ++i) {
906 for (std::size_t j {0}; j < block.cols(); ++j) {
907 out[((
r0 + i) * cols) +
c0 + j] = block(i, j);
913 return matrix<T> {rows, cols, std::move(out)};
Thrown when an operation's operands have incompatible shapes.
A dense, row-major matrix of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
std::size_t rows() const noexcept
The number of rows.
std::size_t cols() const noexcept
The number of columns.
Thrown when a decomposition's input holds an infinite or NaN entry: no factorisation of it means anyt...
Thrown when a Cholesky factorisation finds the matrix not positive-definite.
Thrown when a matrix has no unique solution (it is singular).
A dense N-dimensional tensor of T with value semantics, read row-major. Its elements are immutable on...
A dense vector of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
std::size_t size() const noexcept
The number of elements.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element.
The LU, Cholesky and QR factorisations and the symmetric and Hermitian eigen-decompositions.
The discrete Fourier transform of a tensor along an axis, as numpy.fft.fft and numpy....
void 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 definit...
void 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...
void require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
void 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 subd...
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
void subtract_product(double *y, const double &f, const double *x, std::size_t count)
y[i] −= f · x[i] for double on the widest x86-64 units the matrix product's kernel may use (gemm_path...
band_storage< T > 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),...
magnitude_t< T > pivot_magnitude(const T &x)
The magnitude partial pivoting compares: |x| of a real x.
void 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.
bool is_finite_entry(const T &x)
Whether x is finite.
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
double positive_pivot_step(double d, double &e, double next)
pttrf's step for a real tridiagonal: e ← e / d,
void 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,...
void 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.
void 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,...
double 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).
void 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,...
void 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 (...
The NumericAL public API.
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
T sum(const tensor< T > &t)
The sum of every element, by pairwise halving (0 for an empty tensor), on the threads where they are ...
matrix< T > 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.
matrix< T > 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]),...
matrix< T > 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....
matrix< T > 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].
matrix< T > 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....
vector< std::complex< double > > eigenvalues(const matrix< T > &a)
The eigenvalues alone of the square a, as numpy.linalg.eigvals.
matrix< T > 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 (LAPA...
least_squares_solution< T > least_squares(const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff={})
lstsq, with the residuals, the rank and the singular values numpy.linalg.lstsq returns beside the sol...
tensor< T > ifft(const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward)
The inverse discrete Fourier transform of a along axis, as numpy.fft.ifft: x_j = (1/n) Σ_k X_k e^{2πi...
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
matrix< T > 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,...
matrix< T > 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....
@ 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.
conditioned_solution< T > 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 ...
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...
tensor< T > fft(const tensor< T > &a, std::optional< std::size_t > n=std::nullopt, std::ptrdiff_t axis=-1, fft_norm norm=fft_norm::backward)
The discrete Fourier transform of a along axis, as numpy.fft.fft: X_k = Σ_j x_j e^{−2πi jk/n}.
matrix< T > 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,...
matrix< T > 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...
A solution and the reciprocal condition number of its system (solve_banded_conditioned).
double reciprocal_condition
1 / (‖A‖₁ ‖A⁻¹‖₁), ‖A⁻¹‖₁ estimated.
matrix< T > x
The solution.
A band's entries in LAPACK's column-major band storage: AB(i, j) (from 1) at (i − 1) + (j − 1) ldab.
buffer< T > entries
The columns, ldab apart.
T & operator()(std::size_t i, std::size_t j)
AB(i, j), from 1.
std::size_t ldab
The rows of the storage.