NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
banded.hpp
Go to the documentation of this file.
1
8#ifndef NUMERICAL_BANDED_HPP
9#define NUMERICAL_BANDED_HPP
10
11#include <algorithm>
12#include <cmath>
13#include <complex>
14#include <concepts>
15#include <cstddef>
16#include <limits>
17#include <optional>
18#include <string>
19#include <type_traits>
20#include <utility>
21#include <vector>
22
23#include "factorizations.hpp"
24#include "fft.hpp"
25
26namespace numerical {
27
28 namespace detail {
29
31 template <typename T>
33 {
35 std::size_t ldab;
36
38 [[nodiscard]] T& operator()(std::size_t i,
39 std::size_t j)
40 {
41 return entries[(i - 1) + ((j - 1) * ldab)];
42 }
43 };
44
54 template <typename T>
56 std::size_t n,
57 std::size_t kl,
58 std::size_t ku,
59 std::vector<std::size_t>& pivots)
60 {
61 const std::size_t kv {ku + kl};
62 pivots.assign(n, 0);
63 std::size_t ju {1};
64 for (std::size_t j {1}; j <= n; ++j) {
65 if (j + kv <= n) {
66 for (std::size_t i {1}; i <= kl; ++i) {
67 ab(i, j + kv) = T {};
68 }
69 }
70 const std::size_t km {std::min(kl, n - j)};
71 std::size_t jp {1};
72 double largest {pivot_magnitude(ab(kv + 1, j))};
73 for (std::size_t r {2}; r <= km + 1; ++r) {
74 if (pivot_magnitude(ab(kv + r, j)) > largest) {
75 largest = pivot_magnitude(ab(kv + r, j));
76 jp = r;
77 }
78 }
79 pivots[j - 1] = jp + j - 1;
80 if (ab(kv + jp, j) == T {}) {
81 throw singular_matrix_error("singular matrix");
82 }
83 ju = std::max(ju, std::min(j + ku + jp - 1, n));
84 if (jp != 1) { // rows j and j + jp − 1 over columns j … ju, along the storage's rows
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));
87 }
88 }
89 const T pivot {ab(kv + 1, j)};
90 for (std::size_t r {kv + 2}; r <= kv + 1 + km; ++r) {
91 ab(r, j) /= pivot;
92 }
93 for (std::size_t c {1}; c <= ju - j; ++c) { // the rows below take the multiples of row j, column by column
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;
97 }
98 }
99 }
100 }
101
107 template <typename T>
109 std::size_t n,
110 std::size_t kl,
111 std::size_t ku,
112 const std::vector<std::size_t>& pivots,
113 buffer<T>& b,
114 std::size_t k)
115 {
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]};
120 if (l != j) {
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));
123 }
124 for (std::size_t r {1}; r <= lm; ++r) {
125 subtract_product(b.data() + ((j - 1 + r) * k), ab(kd + r, j), b.data() + ((j - 1) * k), k);
126 }
127 }
128 for (std::size_t j {n}; j >= 1; --j) {
129 const T diagonal {ab(kd, j)};
130 for (std::size_t c {0}; c < k; ++c) {
131 b[((j - 1) * k) + c] /= diagonal;
132 }
133 const std::size_t first {j > kl + ku ? j - kl - ku : 1};
134 for (std::size_t i {first}; i < j; ++i) {
135 subtract_product(b.data() + ((i - 1) * k), ab(kd + i - j, j), b.data() + ((j - 1) * k), k);
136 }
137 }
138 }
139
145 template <typename T>
147 std::size_t n,
148 std::size_t kl,
149 std::size_t ku,
150 const std::vector<std::size_t>& pivots,
151 T* x)
152 {
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) {
157 x[j - 1] -= conj_of(ab(kd + i - j, j)) * x[i - 1];
158 }
159 x[j - 1] /= conj_of(ab(kd, j));
160 }
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) {
164 x[j - 1] -= conj_of(ab(kd + r, j)) * x[j - 1 + r];
165 }
166 const std::size_t l {pivots[j - 1]};
167 if (l != j) {
168 std::swap(x[l - 1], x[j - 1]);
169 }
170 }
171 }
172
179 template <typename T>
181 std::size_t n,
182 std::size_t kd,
183 const std::string& name)
184 {
185 for (std::size_t j {1}; j <= n; ++j) {
186 const double ajj {std::real(ab(kd + 1, j))};
187 if (!(ajj > 0.0)) {
188 throw not_positive_definite_error(name + ": the matrix is not positive definite (leading minor " + std::to_string(j) + ")");
189 }
190 const double root {std::sqrt(ajj)};
191 ab(kd + 1, j) = T {root};
192 const std::size_t kn {std::min(kd, n - j)};
193 for (std::size_t c {1}; c <= kn; ++c) { // row j of U right of the diagonal: AB(kd + 1 − c, j + c)
194 ab(kd + 1 - c, j + c) /= T {root};
195 }
196 for (std::size_t c {1}; c <= kn; ++c) { // A(j + r, j + c) −= conj(U(j, j + r)) U(j, j + c), r ≤ c, the upper band
197 const T right {ab(kd + 1 - c, j + c)};
198 for (std::size_t r {1}; r <= c; ++r) {
199 ab(kd + 1 + r - c, j + c) -= conj_of(ab(kd + 1 - r, j + r)) * right;
200 }
201 }
202 }
203 }
204
209 template <typename T>
211 std::size_t n,
212 std::size_t kd,
213 buffer<T>& b,
214 std::size_t k)
215 {
216 for (std::size_t j {1}; j <= n; ++j) { // Uᴴ: column j of Uᴴ is row j of U, conjugated
217 const std::size_t first {j > kd ? j - kd : 1};
218 for (std::size_t i {first}; i < j; ++i) {
219 subtract_product(b.data() + ((j - 1) * k), conj_of(ab(kd + 1 + i - j, j)), b.data() + ((i - 1) * k), k);
220 }
221 const T diagonal {ab(kd + 1, j)};
222 for (std::size_t c {0}; c < k; ++c) {
223 b[((j - 1) * k) + c] /= diagonal;
224 }
225 }
226 for (std::size_t j {n}; j >= 1; --j) {
227 const T diagonal {ab(kd + 1, j)};
228 for (std::size_t c {0}; c < k; ++c) {
229 b[((j - 1) * k) + c] /= diagonal;
230 }
231 const std::size_t first {j > kd ? j - kd : 1};
232 for (std::size_t i {first}; i < j; ++i) {
233 subtract_product(b.data() + ((i - 1) * k), ab(kd + 1 + i - j, j), b.data() + ((j - 1) * k), k);
234 }
235 }
236 }
237
246 template <typename T>
248 buffer<T>& d,
249 buffer<T>& du,
250 buffer<T>& b,
251 std::size_t n,
252 std::size_t k)
253 {
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)};
257 if (pivot_magnitude(d[i]) >= pivot_magnitude(dl[i])) {
258 if (d[i] == T {}) {
259 throw singular_matrix_error("singular matrix");
260 }
261 const T fact {dl[i] / d[i]};
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]);
265 }
266 dl[i] = T {};
267 }
268 else {
269 const T fact {d[i] / dl[i]};
270 d[i] = dl[i];
271 const T diagonal {d[i + 1]};
272 d[i + 1] = du[i] - (fact * diagonal);
273 if (i + 2 < n) {
274 dl[i] = du[i + 1];
275 du[i + 1] = -fact * dl[i];
276 }
277 du[i] = diagonal;
278 for (std::size_t c {0}; c < k; ++c) {
279 const T top {here[c]};
280 here[c] = next[c];
281 next[c] = top - (fact * next[c]);
282 }
283 }
284 }
285 if (d[n - 1] == T {}) {
286 throw singular_matrix_error("singular matrix");
287 }
288 for (std::size_t c {0}; c < k; ++c) {
289 b[((n - 1) * k) + c] = b[((n - 1) * k) + c] / d[n - 1];
290 }
291 if (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];
294 }
295 }
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];
299 }
300 }
301 }
302
304 [[nodiscard]] inline double positive_pivot_step(double d,
305 double& e,
306 double next)
307 {
308 const double ei {e};
309 e = ei / d;
310 return next - (e * ei);
311 }
312
314 [[nodiscard]] inline double positive_pivot_step(double d,
315 std::complex<double>& e,
316 double next)
317 {
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);
324 }
325
328 const buffer<double>& e,
330 std::size_t n,
331 std::size_t k)
332 {
333 for (std::size_t c {0}; c < k; ++c) {
334 b[((n - 1) * k) + c] = b[((n - 1) * k) + c] / d[n - 1];
335 }
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]);
339 }
340 }
341 }
342
345 const buffer<std::complex<double>>& e,
346 buffer<std::complex<double>>& b,
347 std::size_t n,
348 std::size_t k)
349 {
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];
353 }
354 }
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]));
358 }
359 }
360 }
361
369 template <typename T>
371 buffer<T>& e,
372 buffer<T>& b,
373 std::size_t n,
374 std::size_t k)
375 {
376 for (std::size_t i {0}; i < n; ++i) {
377 if (!(d[i] > 0.0)) {
378 throw not_positive_definite_error("solveh_banded: the matrix is not positive definite (leading minor " + std::to_string(i + 1) + ")");
379 }
380 if (i + 1 < n) {
381 d[i + 1] = positive_pivot_step(d[i], e[i], d[i + 1]);
382 }
383 }
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]);
387 }
388 }
389 positive_back_substitution(d, e, b, n, k);
390 }
391
393 [[nodiscard]] inline double taken_as(const std::complex<double>& z,
394 std::type_identity<double> /*result*/)
395 {
396 return z.real();
397 }
398
400 [[nodiscard]] inline std::complex<double> taken_as(const std::complex<double>& z,
401 std::type_identity<std::complex<double>> /*result*/)
402 {
403 return z;
404 }
405
407 template <typename T>
409 std::size_t rows,
410 const matrix<T>& b,
411 const std::string& name)
412 {
413 if (ab.rows() != rows) {
414 throw dimension_error(name + ": the band must have " + std::to_string(rows) + " rows");
415 }
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");
418 }
419 require_finite(ab, name.c_str());
420 require_finite(b, name.c_str());
421 }
422 } // namespace detail
423
435 template <typename T>
436 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
437 [[nodiscard]] matrix<T> solve_banded(std::size_t lower,
438 std::size_t upper,
439 const matrix<T>& ab,
440 const matrix<T>& b)
441 {
442 detail::require_band(ab, lower + upper + 1, b, "solve_banded");
443 const std::size_t n {ab.cols()};
444 if (lower == 1 && upper == 1 && n > 0) { // gtsv, as SciPy
445 buffer<T> dl(n - 1);
446 buffer<T> d(n);
447 buffer<T> du(n - 1);
448 for (std::size_t j {0}; j < n; ++j) {
449 d[j] = ab(1, j);
450 if (j + 1 < n) {
451 du[j] = ab(0, j + 1);
452 dl[j] = ab(2, j);
453 }
454 }
455 buffer<T> x(b.begin(), b.end());
456 detail::tridiagonal_solve(dl, d, du, x, n, b.cols());
457 return matrix<T> {b.rows(), b.cols(), std::move(x)};
458 }
459 const std::size_t ldab {(2 * lower) + upper + 1};
460 detail::band_storage<T> work {buffer<T>(ldab * n, T {}), ldab};
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);
464 }
465 }
466 std::vector<std::size_t> pivots;
467 detail::band_lu(work, n, lower, upper, pivots);
468 buffer<T> x(b.begin(), b.end());
469 detail::band_lu_solve(work, n, lower, upper, pivots, x, b.cols());
470 return matrix<T> {b.rows(), b.cols(), std::move(x)};
471 }
472
474 template <typename T>
480
491 template <typename T>
492 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
494 std::size_t upper,
495 const matrix<T>& ab,
496 const matrix<T>& b)
497 {
498 detail::require_band(ab, lower + upper + 1, b, "solve_banded");
499 const std::size_t n {ab.cols()};
500 const std::size_t ldab {(2 * lower) + upper + 1};
501 detail::band_storage<T> work {buffer<T>(ldab * n, T {}), ldab};
502 double one_norm {0.0};
503 for (std::size_t j {0}; j < n; ++j) { // column j holds rows j − upper … j + lower of A
504 double column {0.0};
505 for (std::size_t r {upper > j ? upper - j : 0}; r < std::min(lower + upper + 1, upper + n - j); ++r) {
506 column += std::abs(ab(r, j));
507 }
508 one_norm = std::max(one_norm, column);
509 }
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);
513 }
514 }
515 std::vector<std::size_t> pivots;
516 detail::band_lu(work, n, lower, upper, pivots);
517 buffer<T> x(b.begin(), b.end());
518 detail::band_lu_solve(work, n, lower, upper, pivots, x, b.cols());
519 const double reciprocal {detail::reciprocal_condition<T>(n, one_norm, [&](T* v, bool adjoint) {
520 if (adjoint) {
521 detail::band_lu_solve_adjoint(work, n, lower, upper, pivots, v);
522 return;
523 }
524 buffer<T> column(v, v + n);
525 detail::band_lu_solve(work, n, lower, upper, pivots, column, 1);
526 std::copy(column.begin(), column.end(), v);
527 })};
528 return {matrix<T> {b.rows(), b.cols(), std::move(x)}, reciprocal};
529 }
530
531 namespace detail {
534 template <typename T>
536 bool lower_form)
537 {
538 const std::size_t kd {ab.rows() - 1};
539 const std::size_t n {ab.cols()};
540 band_storage<T> work {buffer<T>((kd + 1) * n, T {}), kd + 1};
541 for (std::size_t j {0}; j < n; ++j) {
542 for (std::size_t i {j > kd ? j - kd : 0}; i <= j; ++i) {
543 work(kd + 1 + i - j, j + 1) = lower_form ? conj_of(ab(j - i, i)) : ab(kd + i - j, j);
544 }
545 }
546 return work;
547 }
548 } // namespace detail
549
561 template <typename T>
562 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
564 const matrix<T>& b,
565 bool lower_form = false)
566 {
567 if (ab.rows() == 0) {
568 throw dimension_error("solveh_banded: the band must have at least one row");
569 }
570 const std::size_t kd {ab.rows() - 1};
571 detail::require_band(ab, kd + 1, b, "solveh_banded");
572 const std::size_t n {ab.cols()};
573 if (kd == 1 && n > 0) { // ptsv, as SciPy: the diagonal's real part, the subdiagonal (the superdiagonal conjugated)
574 buffer<double> d(n);
575 buffer<T> e(n - 1);
576 for (std::size_t j {0}; j < n; ++j) {
577 d[j] = std::real(lower_form ? ab(0, j) : ab(1, j));
578 if (j + 1 < n) {
579 e[j] = lower_form ? ab(1, j) : detail::conj_of(ab(0, j + 1));
580 }
581 }
582 buffer<T> x(b.begin(), b.end());
584 return matrix<T> {b.rows(), b.cols(), std::move(x)};
585 }
587 detail::band_cholesky(work, n, kd, "solveh_banded");
588 buffer<T> x(b.begin(), b.end());
589 detail::band_cholesky_solve(work, n, kd, x, b.cols());
590 return matrix<T> {b.rows(), b.cols(), std::move(x)};
591 }
592
601 template <typename T>
602 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
604 bool lower_form = false)
605 {
606 if (ab.rows() == 0) {
607 throw dimension_error("cholesky_banded: the band must have at least one row");
608 }
609 detail::require_finite(ab, "cholesky_banded");
610 const std::size_t kd {ab.rows() - 1};
611 const std::size_t n {ab.cols()};
613 detail::band_cholesky(work, n, kd, "cholesky_banded");
614 buffer<T> out(ab.begin(), ab.end());
615 for (std::size_t j {0}; j < n; ++j) {
616 for (std::size_t i {j > kd ? j - kd : 0}; i <= j; ++i) { // U(i, j), or L(j, i) = conj(U(i, j))
617 if (lower_form) {
618 out[((j - i) * n) + i] = detail::conj_of(work(kd + 1 + i - j, j + 1));
619 }
620 else {
621 out[((kd + i - j) * n) + j] = work(kd + 1 + i - j, j + 1);
622 }
623 }
624 }
625 return matrix<T> {kd + 1, n, std::move(out)};
626 }
627
634 template <typename T>
635 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
637 const matrix<T>& b,
638 bool lower_form = false)
639 {
640 if (cb.rows() == 0) {
641 throw dimension_error("cho_solve_banded: the band must have at least one row");
642 }
643 detail::require_band(cb, cb.rows(), b, "cho_solve_banded");
645 buffer<T> x(b.begin(), b.end());
646 detail::band_cholesky_solve(work, cb.cols(), cb.rows() - 1, x, b.cols());
647 return matrix<T> {b.rows(), b.cols(), std::move(x)};
648 }
649
663 template <typename T>
664 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
666 const vector<T>& r,
667 const matrix<T>& b)
668 {
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");
672 }
673 detail::require_finite(b, "solve_toeplitz");
674 for (std::size_t i {0}; i < n; ++i) {
675 if (!detail::is_finite_entry(c[i]) || (i > 0 && !detail::is_finite_entry(r[i]))) {
676 throw non_finite_error("solve_toeplitz: an entry of c or r is infinite or NaN");
677 }
678 }
679 const std::size_t k {b.cols()};
680 if (n == 0) {
681 return matrix<T> {0, k, buffer<T> {}};
682 }
683 // T(i, j) = c[i − j] on and below the diagonal, r[j − i] above: the recursion's entries c[m − j] and r[m − j]
684 const auto singular = [] { return singular_matrix_error("solve_toeplitz: singular principal minor"); };
685 const T diagonal {c[0]};
686 if (diagonal == T {}) {
687 throw singular();
688 }
689 buffer<T> x(n * k, T {});
690 for (std::size_t col {0}; col < k; ++col) {
691 x[col] = b(0, col) / diagonal;
692 }
693 if (n == 1) {
694 return matrix<T> {1, k, std::move(x)};
695 }
696 buffer<T> g(n, T {});
697 buffer<T> h(n, T {});
698 g[0] = r[1] / diagonal;
699 h[0] = c[1] / diagonal;
701 for (std::size_t m {1}; m < n; ++m) { // the system of order m + 1 from that of order m
702 // every sum of the step in one pass, each in its own order, in locals (an element of a buffer is stored and loaded
703 // back at each term, its address possibly x's): the same bits; g's and h's three unused at the last step
704 const bool grows {m + 1 < n};
706 T g_numerator {grows ? -r[m + 1] : T {}};
707 T h_numerator {grows ? -c[m + 1] : T {}};
709 if (k == 1) {
710 T sum {-b(m, 0)};
711 for (std::size_t j {0}; j < m; ++j) {
712 const T entry {c[m - j]};
713 const T other {r[m - j]};
714 sum += entry * x[j];
715 denominator += entry * g[m - 1 - j];
716 g_numerator += other * g[j];
717 h_numerator += entry * h[j];
718 g_denominator += other * h[m - 1 - j];
719 }
720 numerator[0] = sum;
721 }
722 else {
723 for (std::size_t col {0}; col < k; ++col) {
724 numerator[col] = -b(m, col);
725 }
726 for (std::size_t j {0}; j < m; ++j) {
727 const T entry {c[m - j]};
728 const T other {r[m - j]};
729 for (std::size_t col {0}; col < k; ++col) {
730 numerator[col] += entry * x[(j * k) + col];
731 }
732 denominator += entry * g[m - 1 - j];
733 g_numerator += other * g[j];
734 h_numerator += entry * h[j];
735 g_denominator += other * h[m - 1 - j];
736 }
737 }
738 if (denominator == T {}) {
739 throw singular();
740 }
741 for (std::size_t col {0}; col < k; ++col) {
742 x[(m * k) + col] = numerator[col] / denominator;
743 }
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];
747 }
748 }
749 if (!grows) {
750 break;
751 }
752 if (g_denominator == T {}) {
753 throw singular();
754 }
755 g[m] = g_numerator / g_denominator;
756 h[m] = h_numerator / denominator;
757 const T forward {g[m]};
758 const T backward {h[m]};
759 for (std::size_t j {0}, last {m - 1}; j <= last; ++j, --last) { // the pairs (j, m − 1 − j) from the ends in
760 const T g_first {g[j]};
761 const T g_last {g[last]};
762 const T h_first {h[j]};
763 const T h_last {h[last]};
764 g[j] = g_first - (forward * h_last);
765 g[last] = g_last - (forward * h_first);
766 h[j] = h_first - (backward * g_last);
767 h[last] = h_last - (backward * g_first);
768 if (last == 0) {
769 break;
770 }
771 }
772 }
773 return matrix<T> {n, k, std::move(x)};
774 }
775
788 template <typename T>
789 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
791 const matrix<T>& b,
792 bool least_squares = false,
793 std::optional<double> tol = std::nullopt)
794 {
795 using C = std::complex<double>;
796 const std::size_t n {c.size()};
797 const std::size_t k {b.cols()};
798 if (b.rows() != n) {
799 throw dimension_error("solve_circulant: b must have as many rows as c has entries");
800 }
801 detail::require_finite(b, "solve_circulant");
802 for (std::size_t i {0}; i < n; ++i) {
803 if (!detail::is_finite_entry(c[i])) {
804 throw non_finite_error("solve_circulant: an entry of c is infinite or NaN");
805 }
806 }
807 if (n == 0 || k == 0) {
808 return matrix<T> {n, k, buffer<T>(n * k, T {})};
809 }
810 const tensor<C> eigenvalues {fft(tensor<T> {{n}, buffer<T>(c.begin(), c.end())})};
811 double largest {0.0};
812 for (const C& value : eigenvalues.data()) {
813 largest = std::max(largest, std::abs(value));
814 }
815 const double threshold {tol.value_or(largest * static_cast<double>(n) * std::numeric_limits<double>::epsilon())};
816 bool near {false};
817 for (const C& value : eigenvalues.data()) {
818 near = near || std::abs(value) <= threshold;
819 }
820 if (near && !least_squares) {
821 throw singular_matrix_error("solve_circulant: near singular circulant matrix");
822 }
823 const tensor<C> transformed {fft(tensor<T> {{n, k}, buffer<T>(b.begin(), b.end())}, std::nullopt, 0)};
824 buffer<C> quotients(n * k);
825 for (std::size_t i {0}; i < n; ++i) {
826 const C value {eigenvalues.data()[i]};
827 for (std::size_t col {0}; col < k; ++col) {
828 quotients[(i * k) + col] = std::abs(value) <= threshold ? C {} : transformed.data()[(i * k) + col] / value;
829 }
830 }
831 const tensor<C> x {ifft(tensor<C> {{n, k}, std::move(quotients)}, std::nullopt, 0)};
832 buffer<T> out(n * k);
833 for (std::size_t e {0}; e < n * k; ++e) {
834 out[e] = detail::taken_as(x.data()[e], std::type_identity<T> {});
835 }
836 return matrix<T> {n, k, std::move(out)};
837 }
838
843 template <typename T>
845 const vector<T>& r)
846 {
847 const std::size_t m {c.size()};
848 const std::size_t n {r.size()};
849 buffer<T> out(m * n);
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];
853 }
854 }
855 return matrix<T> {m, n, std::move(out)};
856 }
857
859 template <typename T>
861 {
862 const std::size_t n {c.size()};
863 buffer<T> out(n * n);
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];
867 }
868 }
869 return matrix<T> {n, n, std::move(out)};
870 }
871
876 template <typename T>
878 const vector<T>& r)
879 {
880 const std::size_t m {c.size()};
881 const std::size_t n {r.size()};
882 buffer<T> out(m * n);
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];
886 }
887 }
888 return matrix<T> {m, n, std::move(out)};
889 }
890
892 template <typename T>
893 [[nodiscard]] matrix<T> block_diag(const std::vector<matrix<T>>& blocks)
894 {
895 std::size_t rows {0};
896 std::size_t cols {0};
897 for (const matrix<T>& block : blocks) {
898 rows += block.rows();
899 cols += block.cols();
900 }
901 buffer<T> out(rows * cols, T {});
902 std::size_t r0 {0};
903 std::size_t c0 {0};
904 for (const matrix<T>& block : blocks) {
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);
908 }
909 }
910 r0 += block.rows();
911 c0 += block.cols();
912 }
913 return matrix<T> {rows, cols, std::move(out)};
914 }
915} // namespace numerical
916
917#endif // NUMERICAL_BANDED_HPP
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
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
std::size_t cols() const noexcept
The number of columns.
Definition matrix.hpp:114
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...
Definition tensor.hpp:88
A dense vector of T with value semantics.
Definition vector.hpp:171
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
Definition vector.hpp:212
std::size_t size() const noexcept
The number of elements.
Definition vector.hpp:194
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element.
Definition vector.hpp:206
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...
Definition banded.hpp:370
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...
Definition banded.hpp:55
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...
Definition banded.hpp:247
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...
Definition gemm.hpp:485
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),...
Definition banded.hpp:535
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.
Definition banded.hpp:327
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,
Definition banded.hpp:304
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,...
Definition banded.hpp:210
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.
Definition banded.hpp:408
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,...
Definition banded.hpp:146
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).
Definition banded.hpp:393
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,...
Definition banded.hpp:108
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 (...
Definition banded.hpp:180
The NumericAL public API.
Definition amx.hpp:44
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
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.
Definition banded.hpp:893
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]),...
Definition banded.hpp:790
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....
Definition banded.hpp:563
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].
Definition banded.hpp:860
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....
Definition banded.hpp:877
vector< std::complex< double > > eigenvalues(const matrix< T > &a)
The eigenvalues alone of the square a, as numpy.linalg.eigvals.
Definition eigen.hpp:3686
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...
Definition banded.hpp:603
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...
Definition svd.hpp:3031
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...
Definition fft.hpp:3011
@ 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,...
Definition banded.hpp:437
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....
Definition banded.hpp:844
@ 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 ...
Definition banded.hpp:493
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}.
Definition fft.hpp:2966
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,...
Definition banded.hpp:665
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...
Definition banded.hpp:636
A solution and the reciprocal condition number of its system (solve_banded_conditioned).
Definition banded.hpp:476
double reciprocal_condition
1 / (‖A‖₁ ‖A⁻¹‖₁), ‖A⁻¹‖₁ estimated.
Definition banded.hpp:478
matrix< T > x
The solution.
Definition banded.hpp:477
A band's entries in LAPACK's column-major band storage: AB(i, j) (from 1) at (i − 1) + (j − 1) ldab.
Definition banded.hpp:33
buffer< T > entries
The columns, ldab apart.
Definition banded.hpp:34
T & operator()(std::size_t i, std::size_t j)
AB(i, j), from 1.
Definition banded.hpp:38
std::size_t ldab
The rows of the storage.
Definition banded.hpp:35