NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
svd.hpp
Go to the documentation of this file.
1
7#ifndef NUMERICAL_SVD_HPP
8#define NUMERICAL_SVD_HPP
9
10#include <algorithm>
11#include <array>
12#include <atomic>
13#include <bit>
14#include <cfloat>
15#include <cmath>
16#include <complex> // so std::abs resolves for a complex scalar, regardless of include order
17#include <concepts>
18#include <cstddef>
19#include <cstdint>
20#include <cstring>
21#include <functional>
22#include <limits>
23#include <memory>
24#include <numbers>
25#include <numeric>
26#include <optional>
27#include <stdexcept>
28#include <string>
29#include <tuple>
30#include <type_traits>
31#include <utility>
32#include <vector>
33
34#include "concepts.hpp"
35#include "dqds.hpp"
36#include "factorizations.hpp"
37
38namespace numerical {
39
40 namespace detail {
41
44 inline constexpr double jacobi_tiny {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
45
47 inline constexpr double jacobi_large {1e150};
48
51 inline constexpr double cancelled {64.0};
52
63 template <typename T>
65 buffer<T>& v,
66 std::size_t n,
67 std::size_t max_sweeps)
68 {
69 // The sweeps rotate columns: work on the transposes, where each column is a contiguous row. A walk
70 // down the columns of the row-major arrays strides by n on every access and runs several times slower.
71 const auto transpose_square {[n](buffer<T>& m) {
72 for (std::size_t i {0}; i < n; ++i) {
73 for (std::size_t j {i + 1}; j < n; ++j) {
74 std::swap(m[(i * n) + j], m[(j * n) + i]);
75 }
76 }
77 }};
80 // Orthogonal to the rounding of the columns' storage: a float column holds no inner product to double's.
81 // The rotations are carried in double: the coarser of T's epsilon and double's, times √n as LAPACK's dgesvj
82 // takes it: an inner product of n terms is rounded by about that much, and a bound below it may never hold.
83 const double epsilon {std::sqrt(static_cast<double>(n))
84 * std::max(static_cast<double>(std::numeric_limits<value_range_t<T>>::epsilon()), std::numeric_limits<double>::epsilon())};
85 for (std::size_t sweep {1};; ++sweep) {
86 bool rotated {false};
87 for (std::size_t p {0}; p < n; ++p) {
88 for (std::size_t q {p + 1}; q < n; ++q) {
89 const T* wp {w.data() + (p * n)};
90 const T* wq {w.data() + (q * n)};
91 double alpha {0.0};
92 double beta {0.0};
93 T gamma {};
94 for (std::size_t i {0}; i < n; ++i) {
95 alpha += static_cast<double>(std::norm(wp[i]));
96 beta += static_cast<double>(std::norm(wq[i]));
97 gamma += conj_of(wp[i]) * wq[i];
98 }
99 double magnitude {static_cast<double>(std::abs(gamma))};
100 double zeta {};
101 if (std::min(alpha, beta) < jacobi_tiny) {
102 // A column whose squares underflow (rows of a far smaller scale than the largest): its sum of squares
103 // is 0 or has lost its digits, and the test below never holds. The pair is judged on the columns over
104 // their norms, which need no squares: the cosine, and ζ from the ratio of the norms.
105 const auto norm_p {static_cast<double>(scaled_norm(wp, n))};
106 const auto norm_q {static_cast<double>(scaled_norm(wq, n))};
107 if (norm_p == 0.0 || norm_q == 0.0) {
108 continue; // a zero column is orthogonal to any other
109 }
110 T cosine {};
111 for (std::size_t i {0}; i < n; ++i) {
113 }
114 const double size {static_cast<double>(std::abs(cosine))};
115 zeta = ((norm_q / norm_p) - (norm_p / norm_q)) / (2.0 * size);
116 // Orthogonal to the precision the columns hold: a subnormal one holds fewer bits (a column of norm
117 // 1e-314, 31), and its cosine stops near its own spacing, which no rotation lowers (ones(25, 28)).
118 const double held {2.0 * std::sqrt(static_cast<double>(n)) * static_cast<double>(std::numeric_limits<value_range_t<T>>::denorm_min())
119 / std::min(norm_p, norm_q)};
120 if (size <= std::max(epsilon, held)) {
121 continue; // orthogonal to rounding
122 }
123 gamma = cosine; // the phase is γ's
124 magnitude = size;
125 }
126 else {
127 if (magnitude <= epsilon * std::sqrt(alpha) * std::sqrt(beta)) {
128 continue; // already orthogonal to rounding (or a zero column)
129 }
130 zeta = (beta - alpha) / (2.0 * magnitude);
131 }
132 // Past jacobi_large, ζ² overflows and t would be 0 (no rotation, ever): there |ζ| + √(1 + ζ²) is 2|ζ| exactly,
133 // and t is 1 / (2|ζ|). A tangent that still underflows to 0 is a rotation below the smallest double.
134 const double t {(zeta >= 0.0 ? 1.0 : -1.0) * (std::abs(zeta) > jacobi_large ? 0.5 / std::abs(zeta) : 1.0 / (std::abs(zeta) + std::sqrt(1.0 + (zeta * zeta))))};
135 if (t == 0.0) {
136 continue; // a rotation below the smallest double: the pair is as orthogonal as it can be
137 }
138 // Turn column q by the phase of γ so that the pair's inner product is real, then rotate.
139 const T turn {conj_of(gamma) / detail::from_carried<T>(magnitude)};
140 const double c {1.0 / std::sqrt(1.0 + (t * t))};
141 const double s {c * t};
142 rotated = true;
143 double after_p {0.0}; // W's columns' sums of squares once rotated
144 double after_q {0.0};
145 for (buffer<T>* side : {&w, &v}) {
146 T* mp {side->data() + (p * n)};
147 T* mq {side->data() + (q * n)};
148 for (std::size_t i {0}; i < n; ++i) {
149 const T left {mp[i]};
150 const T right {turn * mq[i]};
153 if (side == &w) {
154 after_p += static_cast<double>(std::norm(mp[i]));
155 after_q += static_cast<double>(std::norm(mq[i]));
156 }
157 }
158 }
159 // A column the rotation left with nothing but rounding (its norm fallen past 64 √n ε of what it was): it
160 // lay along the other to rounding, and its rest is that rounding, along the other again, which the sweeps
161 // would subtract a few digits at a time without end (a matrix of rank 1 from order 160, ones((200, 200))).
162 // It is set to 0, a change of W within that rounding. A column with something of its own keeps it.
163 if (std::min(alpha, beta) >= jacobi_tiny) {
164 const double gone {(cancelled * epsilon) * (cancelled * epsilon)};
165 for (const auto& [column, before, after] : {std::tuple {p, alpha, after_p}, std::tuple {q, beta, after_q}}) {
166 if (after <= gone * before) {
167 std::fill_n(w.data() + (column * n), n, T {});
168 }
169 }
170 }
171 }
172 }
173 if (!rotated) {
176 return;
177 }
178 if (sweep == max_sweeps) {
179 throw convergence_error("SVD: one-sided Jacobi did not converge within its sweeps");
180 }
181 }
182 }
183
186 inline constexpr std::size_t svd_qr_steps_per_value {30};
187
191 inline constexpr std::size_t bidiagonal_crossover {128};
192
196 inline constexpr std::size_t bidiagonal_basis_crossover {64};
197
212 template <typename T>
213 void form_bidiagonal_bases(const std::vector<buffer<T>>& left,
214 std::vector<buffer<T>> right,
215 const std::vector<T>& left_tau,
216 const std::vector<T>& right_tau,
217 const buffer<T>& left_phase,
218 const buffer<T>& right_phase,
219 std::size_t n,
220 buffer<T>& ut,
221 buffer<T>& vt)
222 {
223 // U_b = L₀ᴴ L₁ᴴ … with L_kᴴ = H_k diag(conj phase at k), and V_b = R₀ R₁ … with R_k = H'_k diag(phase
224 // at k+1). A phase on row k commutes with every later reflector, which acts on rows past it, so
225 // U_b = (H₀ H₁ …) diag(conj phases) and V_b = (H'₀ H'₁ …) diag(phases): the reflectors are applied to the
226 // diagonal by blocks, through the matrix product kernel, as QR's Q is formed.
227 ut.assign(n * n, T {}); // Uᵀ and Vᵀ, formed transposed: diagonal to start, the reflectors applied to them
228 vt.assign(n * n, T {});
229 for (std::size_t k {0}; k < n; ++k) {
230 ut[(k * n) + k] = conj_of(left_phase[k]);
231 vt[(k * n) + k] = k == 0 ? T {1} : right_phase[k - 1];
232 }
233 std::vector<buffer<T>> shifted(n); // right[k] acts from row k+1: as reflector k+1 of a QR
234 std::vector<T> shifted_tau(n, T {});
235 for (std::size_t k {0}; k + 1 < n; ++k) {
236 shifted[k + 1] = std::move(right[k]);
237 shifted_tau[k + 1] = right_tau[k];
238 }
239 if (n < bidiagonal_basis_crossover) { // a reflector at a time, the last first, as LAPACK's dorg2r
240 for (std::size_t k {n}; k-- > 0;) {
241 reflect_columns(ut.data(), n, left[k], k, k, n, left_tau[k]);
242 reflect_columns(vt.data(), n, shifted[k], k, k, n, shifted_tau[k]);
243 }
244 return;
245 }
246 for (std::size_t k1 {n}; k1 > 0;) { // blocks of qr_block reflectors, the last first
247 const std::size_t k0 {(k1 - 1) / qr_block * qr_block};
250 k1 = k0;
251 }
252 }
253
258#ifdef NUMERICAL_X86_COMPILED
259 inline constexpr std::size_t bidiagonal_shared_least {256};
260#endif
261
263 inline constexpr std::size_t bidiagonal_block {32};
264
268#ifdef NUMERICAL_X86_COMPILED
269 inline constexpr std::size_t bidiagonal_product_weight {4};
270#else
271 inline constexpr std::size_t bidiagonal_product_weight {1};
272#endif
273
274 template <typename T>
276 std::size_t n,
279 buffer<T>& ut,
280 buffer<T>& vt,
281 bool form = true);
282
300 template <typename T>
301 requires std::is_floating_point_v<T> || split_complex<T>
303 std::size_t n,
306 buffer<T>& ut,
307 buffer<T>& vt,
308 bool form = true)
309 {
310 if (n < bidiagonal_crossover) {
311 bidiagonalize_unblocked(b, n, d, e, ut, vt, form);
312 return;
313 }
314 std::vector<buffer<T>> left(n); // the left reflector of step k, on rows k…, empty where none was needed
315 std::vector<buffer<T>> right(n); // the right reflector of step k, on columns k+1…, likewise
316 std::vector<T> left_tau(n, T {}); // each one's τ, as LAPACK's dlarfg forms them (larfg_in_place)
317 std::vector<T> right_tau(n, T {});
318 buffer<T> left_phase(n, T {1}); // row k times it puts |d_k| on the diagonal (1: a real T)
319 buffer<T> right_phase(n, T {1}); // column k + 1 times it puts |e_k| above
320 const auto nonzero {[](const T& value) { return value != T {}; }};
321 constexpr bool complex_entries {split_complex<T>};
322 // By reflector, each row over the whole order: row 2p of vx holds step k0 + p's left reflector v (at its rows),
323 // row 2p + 1 what its right one moves, x = 2 B u (at the rows); row 2p of yu what v moves, y = 2 Bᵀ v (at the
324 // columns), row 2p + 1 the right reflector u (at its columns). A step's terms of the panel's earlier ones are then
325 // one update through their rows (subtract_products, a family's rows 2n apart), in their order.
328 buffer<T> columns(bidiagonal_block * n); // the panel's columns of B, gathered row by row
329 buffer<T> factors(2 * bidiagonal_block); // a step's coefficients of those rows
330#ifdef NUMERICAL_X86_COMPILED
331 buffer<T> next_factors(2 * bidiagonal_block); // the next column's, applied ahead (a shared step)
332#endif
333 for (std::size_t k0 {0}; k0 < n; k0 += bidiagonal_block) {
334 const std::size_t k1 {std::min(k0 + bidiagonal_block, n)};
335 const std::size_t width {k1 - k0};
336 std::fill_n(vx.data(), 2 * width * n, T {});
337 std::fill_n(yu.data(), 2 * width * n, T {});
338 for (std::size_t r {k0}; r < n; ++r) { // column k from row k down, each row's part read once
339 for (std::size_t k {k0}; k < std::min(k1, r + 1); ++k) {
340 columns[((k - k0) * n) + r] = b[(r * n) + k];
341 }
342 }
343 const auto v_row {[&vx, n](std::size_t p, std::size_t from) { return vx.data() + (2 * p * n) + from; }};
344 const auto x_row {[&vx, n](std::size_t p, std::size_t from) { return vx.data() + (((2 * p) + 1) * n) + from; }};
345 const auto y_row {[&yu, n](std::size_t p, std::size_t from) { return yu.data() + (2 * p * n) + from; }};
346 const auto u_row {[&yu, n](std::size_t p, std::size_t from) { return yu.data() + (((2 * p) + 1) * n) + from; }};
347#ifdef NUMERICAL_X86_COMPILED
348 bool column_ahead {false}; // whether the step's column took the steps before the last ahead (a shared step)
349#endif
350 for (std::size_t k {k0}; k < k1; ++k) {
351 const std::size_t i {k - k0};
352#ifdef NUMERICAL_X86_COMPILED
353 const std::size_t from {column_ahead ? i - 1 : 0};
354 column_ahead = false;
355#else
356 constexpr std::size_t from {0};
357#endif
358 for (std::size_t p {from}; p < i; ++p) { // v's row by y's element, x's by u's
359 factors[2 * (p - from)] = *y_row(p, k);
360 factors[(2 * (p - from)) + 1] = *u_row(p, k);
361 }
362 T* const column {columns.data() + (i * n) + k}; // column k from the diagonal down, the panel's earlier steps applied
363 subtract_products(column, factors.data(), v_row(from, k), n, 2 * (i - from), n - k);
364 if constexpr (complex_entries) {
365 if (k > 0) { // the previous step's phase on this column, now that it is to be reflected
366 for (std::size_t r {0}; r < n - k; ++r) {
367 column[r] *= right_phase[k - 1];
368 }
369 }
370 }
371 buffer<T> x(column, column + (n - k));
372 if (std::any_of(x.begin() + 1, x.end(), nonzero)) { // something below the diagonal to reflect
373 const auto [beta, tau] {larfg_in_place(x)}; // Hᴴ = I − τ̄ w wᴴ from the left, as LAPACK's dlabrd
374 if constexpr (complex_entries) {
375 d[k] = static_cast<double>(std::abs(beta));
376 left_phase[k] = conj_of(phase_of(beta));
377 }
378 else {
379 d[k] = static_cast<double>(beta);
380 }
381 // y = τ (B − V Yᵀ − X Uᵀ)ᴴ v on the columns past k, held conjugated: Bᵀ v̄ by contiguous rows, then the
382 // panel's terms, times τ̄.
383 buffer<T> by_vx(2 * i, T {}); // Vᵀ v and Xᵀ v over the earlier steps, interleaved as their rows
384 buffer<T> conjugate(x.size()); // v̄: Bᴴ v as the terms of (Bᵀ v̄) (v itself for a real T)
385 std::transform(x.begin(), x.end(), conjugate.begin(), [](const T& value) { return conj_of(value); });
386 for (std::size_t p {0}; p < i; ++p) {
387 by_vx[2 * p] = dot_product(v_row(p, k), conjugate.data(), n - k);
388 by_vx[(2 * p) + 1] = dot_product(x_row(p, k), conjugate.data(), n - k);
389 }
390 const std::size_t span {n - k - 1};
391 constexpr std::size_t chunk_width {64};
392 // Bᵀ v as the terms −(−v)·B, the chunk held through them (negation is exact, so each column takes the same
393 // additions): row by row, each term stored the chunk back (singular values of order 512 on one x86-64
394 // core: 46 → 42 ms).
395 buffer<T> minus(x.size(), T {});
396 std::transform(conjugate.begin(), conjugate.end(), minus.begin(), std::negate<T> {});
397 parallel_for((span + chunk_width - 1) / chunk_width, bidiagonal_product_weight * (n - k) * chunk_width, [&](std::size_t chunk) {
398 const std::size_t first {k + 1 + (chunk * chunk_width)};
399 const std::size_t count {std::min(chunk_width, n - first)};
400 buffer<T> sum(count, T {});
401 subtract_products(sum.data(), minus.data(), b.data() + (k * n) + first, n, n - k, count);
402 subtract_products(sum.data(), by_vx.data(), y_row(0, first), n, 2 * i, count);
403 for (std::size_t c {0}; c < count; ++c) {
404 *y_row(i, first + c) = conj_of(tau) * sum[c];
405 }
406 });
407 std::copy(x.begin(), x.end(), v_row(i, k));
408 left[k] = std::move(x);
409 left_tau[k] = tau;
410 }
411 else if constexpr (complex_entries) {
412 d[k] = static_cast<double>(std::abs(x[0]));
413 left_phase[k] = conj_of(phase_of(x[0]));
414 }
415 else {
416 d[k] = static_cast<double>(x[0]);
417 }
418 if (k + 1 == n) {
419 break;
420 }
421 buffer<T> y(b.begin() + static_cast<std::ptrdiff_t>((k * n) + k + 1), // row k past the diagonal, the left
422 b.begin() + static_cast<std::ptrdiff_t>((k + 1) * n)); // reflection included
423 for (std::size_t p {0}; p <= i; ++p) {
424 factors[p] = *v_row(p, k);
425 }
426 subtract_products(y.data(), factors.data(), y_row(0, k + 1), 2 * n, i + 1, n - k - 1);
427 for (std::size_t p {0}; p < i; ++p) {
428 factors[p] = *x_row(p, k);
429 }
430 subtract_products(y.data(), factors.data(), u_row(0, k + 1), 2 * n, i, n - k - 1);
431 if constexpr (complex_entries) { // the row times its phase, then conjugated: B ← B H with H yᴴ ∥ e₁
432 for (T& element : y) {
434 }
435 }
436 if (std::any_of(y.begin() + 1, y.end(), nonzero)) { // something past the superdiagonal to reflect
437 const auto [beta, tau] {larfg_in_place(y)}; // B ← B (I − τ u uᴴ), as LAPACK's dlabrd
438 if constexpr (complex_entries) { // the row's entry is β̄: its phase's conjugate turns it to |β|
439 e[k] = static_cast<double>(std::abs(beta));
440 right_phase[k] = phase_of(beta);
441 }
442 else {
443 e[k] = static_cast<double>(beta);
444 }
445 // x = τ (B − V Yᵀ − X Uᵀ) u on the rows past k: B u by rows, then the panel's terms.
446 const std::size_t rows {n - k - 1};
447 buffer<T> by_y(i + 1, T {}); // Yᵀ u over this and the earlier steps, Uᵀ u over the earlier
448 buffer<T> by_u(i, T {});
449 buffer<T> moved(rows, T {});
450#ifdef NUMERICAL_X86_COMPILED
451 if (rows >= bidiagonal_shared_least) {
452 // The coefficients run among B u's tasks, and the corrections by bands on the threads, the next column
453 // taking the earlier steps' terms in the same pass (its rows are these): each element the operations,
454 // in the order, of the branch above.
455 parallel_for(rows + (2 * i) + 1, bidiagonal_product_weight * 2 * (n - k), [&](std::size_t task) {
456 if (task < rows) {
457 moved[task] = dot_product(b.data() + ((k + 1 + task) * n) + k + 1, y.data(), y.size());
458 }
459 else if (task - rows <= i) {
460 by_y[task - rows] = dot_product(y_row(task - rows, k + 1), y.data(), y.size());
461 }
462 else {
463 by_u[task - rows - i - 1] = dot_product(u_row(task - rows - i - 1, k + 1), y.data(), y.size());
464 }
465 });
466 T* const next {k + 1 < k1 && i > 0 ? columns.data() + ((i + 1) * n) + k + 1 : nullptr};
467 for (std::size_t p {0}; next != nullptr && p < i; ++p) { // the next column's terms of the steps before this
468 next_factors[2 * p] = *y_row(p, k + 1);
469 next_factors[(2 * p) + 1] = *u_row(p, k + 1);
470 }
471 constexpr std::size_t band {256};
472 parallel_for((rows + band - 1) / band, band * 4 * (i + 1) * 8, [&](std::size_t c) {
473 const std::size_t first {c * band};
474 const std::size_t count {std::min(band, rows - first)};
475 subtract_products(moved.data() + first, by_y.data(), v_row(0, k + 1 + first), 2 * n, i + 1, count);
476 subtract_products(moved.data() + first, by_u.data(), x_row(0, k + 1 + first), 2 * n, i, count);
477 for (std::size_t r {first}; r < first + count; ++r) {
478 *x_row(i, k + 1 + r) = tau * moved[r];
479 }
480 if (next != nullptr) {
481 subtract_products(next + first, next_factors.data(), v_row(0, k + 1 + first), n, 2 * i, count);
482 }
483 });
484 column_ahead = next != nullptr;
485 }
486 else
487#endif
488 {
489 for (std::size_t p {0}; p <= i; ++p) {
490 by_y[p] = dot_product(y_row(p, k + 1), y.data(), y.size());
491 }
492 for (std::size_t p {0}; p < i; ++p) {
493 by_u[p] = dot_product(u_row(p, k + 1), y.data(), y.size());
494 }
495 parallel_for(rows, bidiagonal_product_weight * 2 * (n - k), [&](std::size_t row) {
496 moved[row] = dot_product(b.data() + ((k + 1 + row) * n) + k + 1, y.data(), y.size());
497 });
498 subtract_products(moved.data(), by_y.data(), v_row(0, k + 1), 2 * n, i + 1, rows);
499 subtract_products(moved.data(), by_u.data(), x_row(0, k + 1), 2 * n, i, rows);
500 for (std::size_t r {0}; r < rows; ++r) {
501 *x_row(i, k + 1 + r) = tau * moved[r];
502 }
503 }
504
505 std::transform(y.begin(), y.end(), u_row(i, k + 1), [](const T& value) { return conj_of(value); }); // Ū
506 right[k] = std::move(y);
507 right_tau[k] = tau;
508 }
509 else if constexpr (complex_entries) { // y₀ the entry's conjugate
510 e[k] = static_cast<double>(std::abs(y[0]));
511 right_phase[k] = phase_of(y[0]);
512 }
513 else {
514 e[k] = static_cast<double>(y[0]);
515 }
516 }
517 if (k1 < n) { // the trailing block from row and column k1: B −= V Yᵀ + X Uᵀ
518 const std::size_t rest {n - k1};
519 buffer<T> minus_v(rest * width, T {});
520 buffer<T> minus_x(rest * width, T {});
521 for (std::size_t r {0}; r < rest; ++r) {
522 for (std::size_t p {0}; p < width; ++p) {
523 minus_v[(r * width) + p] = -*v_row(p, k1 + r);
524 minus_x[(r * width) + p] = -*x_row(p, k1 + r);
525 }
526 }
527 T* trailing {b.data() + (k1 * n) + k1};
528 gemm(rest, rest, width, minus_v.data(), width, y_row(0, k1), 2 * n, trailing, n);
529 gemm(rest, rest, width, minus_x.data(), width, u_row(0, k1), 2 * n, trailing, n);
530 }
531 }
532 e[n - 1] = 0.0;
533 if (form) {
535 }
536 }
537
554 template <typename T>
556 std::size_t rows,
557 std::size_t n,
560 buffer<T>& ut,
561 buffer<T>& vt,
562 bool form)
563 {
564 std::vector<buffer<T>> left(n); // the left reflector of step k, empty where none was needed
565 std::vector<buffer<T>> right(n); // the right reflector acting on columns k+1…, likewise
566 std::vector<T> left_tau(n, T {});
567 std::vector<T> right_tau(n, T {});
568 buffer<T> left_phase(n, T {1});
569 buffer<T> right_phase(n, T {1});
570 for (std::size_t k {0}; k < n; ++k) {
571 buffer<T> x(rows - k, T {}); // column k from the diagonal down
572 for (std::size_t i {k}; i < rows; ++i) {
573 x[i - k] = b[(i * n) + k];
574 }
575 if (scaled_norm(x.data() + 1, x.size() - 1) > 0.0) { // as LAPACK's dgebd2: Hᴴ = I − τ̄ w wᴴ from the left
576 const auto [beta, tau] {larfg_in_place(x)};
577 reflect_rows(b, n, x, k, k + 1, conj_of(tau));
578 b[(k * n) + k] = beta;
579 left[k] = std::move(x);
580 left_tau[k] = tau;
581 }
582 left_phase[k] = conj_of(phase_of(b[(k * n) + k])); // row k times it puts |b_kk| on the diagonal
583 for (std::size_t j {k}; j < n; ++j) {
584 b[(k * n) + j] *= left_phase[k];
585 }
586 d[k] = static_cast<double>(std::abs(b[(k * n) + k]));
587 if (k + 1 == n) {
588 break;
589 }
590 buffer<T> y(n - k - 1, T {}); // row k right of the diagonal, conjugated: B ← B H with H yᴴ ∥ e₁
591 for (std::size_t j {k + 1}; j < n; ++j) {
592 y[j - k - 1] = conj_of(b[(k * n) + j]);
593 }
594 if (y.size() > 1 && scaled_norm(y.data() + 1, y.size() - 1) > 0.0) {
595 const auto [beta, tau] {larfg_in_place(y)};
596 parallel_for(rows - k - 1, 2 * y.size(), [&](std::size_t r) { // row ← row (I − τ y yᴴ); rows above k are zero there
597 T* row {b.data() + ((k + 1 + r) * n) + k + 1};
598 const T scale {tau * dot_product(row, y.data(), y.size())};
599 for (std::size_t j {0}; j < y.size(); ++j) {
600 row[j] -= scale * conj_of(y[j]);
601 }
602 });
603 b[(k * n) + k + 1] = beta; // row k is β e₁ past the diagonal: the rest is read no more
604 right[k] = std::move(y);
605 right_tau[k] = tau;
606 }
607 right_phase[k] = conj_of(phase_of(b[(k * n) + k + 1])); // column k+1 times it: |b_k,k+1| above
608 for (std::size_t i {k}; i < rows; ++i) {
609 b[(i * n) + k + 1] *= right_phase[k];
610 }
611 e[k] = static_cast<double>(std::abs(b[(k * n) + k + 1]));
612 }
613 if (n > 0) {
614 e[n - 1] = 0.0;
615 }
616 if (form) {
618 }
619 }
620
622 template <typename T>
624 std::size_t n,
627 buffer<T>& ut,
628 buffer<T>& vt,
629 bool form)
630 {
631 bidiagonalize_unblocked(b, n, n, d, e, ut, vt, form);
632 }
633
635 template <typename T>
636 requires(!std::is_floating_point_v<T> && !split_complex<T>)
638 std::size_t n,
641 buffer<T>& ut,
642 buffer<T>& vt,
643 bool form = true)
644 {
645 bidiagonalize_unblocked(b, n, d, e, ut, vt, form);
646 }
647
662 template <typename T>
665 buffer<T>& ut,
666 buffer<T>& vt,
667 std::size_t n,
668 std::size_t max_steps)
669 {
670 // The iteration reads only d and e: what it does to the rows of vt and ut is recorded and applied once
671 // at the end, in parallel by columns.
672 std::vector<row_operation> on_vt;
673 std::vector<row_operation> on_ut;
674 const bool record {!vt.empty()}; // the singular values alone record nothing
675 const double epsilon {std::numeric_limits<double>::epsilon()};
676 const double tiny {std::numeric_limits<double>::min() / epsilon};
677 constexpr std::size_t none {std::numeric_limits<std::size_t>::max()};
678 std::size_t p {n};
679 std::size_t steps {0};
680 bool down {true}; // the direction of the chase, chosen per block
681 std::size_t chased_top {n};
682 std::size_t chased_last {0};
683 // One implicit QR step on the block top…p−1 of the bidiagonal D, E (the entries of d and e as \p at maps their
684 // positions), shifted by the eigenvalue of the trailing 2 × 2 of BᵀB nearer its last diagonal entry: the bulge
685 // chased from top to bottom, its rotations recorded on the right and on the left.
686 const auto qr_step {[&](std::size_t first, std::size_t end, auto&& dd, auto&& ee, auto&& at, std::vector<row_operation>& right,
687 std::vector<row_operation>& left) {
688 const double scale {std::max({std::abs(dd(end - 1)), std::abs(dd(end - 2)), std::abs(ee(end - 2)),
689 std::abs(dd(first)), std::abs(ee(first))})};
690 const double sp {dd(end - 1) / scale};
691 const double spm1 {dd(end - 2) / scale};
692 const double epm1 {ee(end - 2) / scale};
693 const double sk {dd(first) / scale};
694 const double ek {ee(first) / scale};
695 const double bb {(((spm1 + sp) * (spm1 - sp)) + (epm1 * epm1)) / 2.0};
696 const double cc {(sp * epm1) * (sp * epm1)};
697 double shift {0.0};
698 if (bb != 0.0 || cc != 0.0) {
699 shift = std::sqrt((bb * bb) + cc);
700 shift = cc / (bb < 0.0 ? bb - shift : bb + shift);
701 }
702 double f {((sk + sp) * (sk - sp)) + shift};
703 double g {sk * ek};
704 for (std::size_t j {first}; j + 1 < end; ++j) {
705 double t {rotation_length(f, g)};
706 double cs {f / t};
707 double sn {g / t};
708 if (j != first) {
709 ee(j - 1) = t;
710 }
711 f = (cs * dd(j)) + (sn * ee(j));
712 ee(j) = (cs * ee(j)) - (sn * dd(j));
713 g = sn * dd(j + 1);
714 dd(j + 1) = cs * dd(j + 1);
715 if (record) {
716 right.push_back({row_operation::kind::rotate, at(j), at(j + 1), cs, sn});
717 }
718 t = rotation_length(f, g);
719 cs = f / t;
720 sn = g / t;
721 dd(j) = t;
722 f = (cs * ee(j)) + (sn * dd(j + 1));
723 dd(j + 1) = (cs * dd(j + 1)) - (sn * ee(j));
724 if (j + 2 < end) { // past the block, e is zero and stays so
725 g = sn * ee(j + 1);
726 ee(j + 1) = cs * ee(j + 1);
727 }
728 if (record) {
729 left.push_back({row_operation::kind::rotate, at(j), at(j + 1), cs, sn});
730 }
731 }
732 ee(end - 2) = f;
733 }};
734 while (p > 0) {
735 // The largest k < p−1 with a negligible e[k] (none: the loop ran out and wrapped).
736 std::size_t k {p - 1};
737 while (k-- > 0) {
738 if (std::abs(e[k]) <= tiny + (epsilon * (std::abs(d[k]) + std::abs(d[k + 1])))) {
739 e[k] = 0.0;
740 break;
741 }
742 }
743 const std::size_t top {k == none ? 0 : k + 1}; // the unreduced block is top…p−1
744 if (top == p - 1) { // d[p−1] has converged: make it non-negative, sort it into place
745 if (d[top] < 0.0) {
746 d[top] = -d[top];
747 if (record) {
748 on_vt.push_back({row_operation::kind::negate, top, top, 0.0, 0.0});
749 }
750 }
751 for (std::size_t j {top}; j + 1 < n && d[j] < d[j + 1]; ++j) {
752 std::swap(d[j], d[j + 1]);
753 if (record) {
754 on_vt.push_back({row_operation::kind::swap, j, j + 1, 0.0, 0.0});
755 on_ut.push_back({row_operation::kind::swap, j, j + 1, 0.0, 0.0});
756 }
757 }
758 --p;
759 continue;
760 }
761 // The last negligible d[zero] in the block (none: there is none).
762 std::size_t zero {none};
763 for (std::size_t ks {p}; ks-- > top;) {
764 const double around {std::abs(e[ks]) + (ks != top ? std::abs(e[ks - 1]) : 0.0)};
765 if (std::abs(d[ks]) <= tiny + (epsilon * around)) {
766 d[ks] = 0.0;
767 zero = ks;
768 break;
769 }
770 }
771 if (zero == p - 1) { // chase e[p−2] up the block with rotations on the right
772 double f {e[p - 2]};
773 e[p - 2] = 0.0;
774 for (std::size_t j {p - 1}; j-- > top;) {
775 const double t {rotation_length(d[j], f)};
776 const double cs {d[j] / t};
777 const double sn {f / t};
778 d[j] = t;
779 if (j != top) {
780 f = -sn * e[j - 1];
781 e[j - 1] = cs * e[j - 1];
782 }
783 if (record) {
784 on_vt.push_back({row_operation::kind::rotate, j, p - 1, cs, sn});
785 }
786 }
787 continue;
788 }
789 if (zero != none) { // split at d[zero] = 0: chase e[zero] along the row with rotations on the left
790 double f {e[zero]};
791 e[zero] = 0.0;
792 for (std::size_t j {zero + 1}; j < p; ++j) {
793 const double t {rotation_length(d[j], f)};
794 const double cs {d[j] / t};
795 const double sn {f / t};
796 d[j] = t;
797 f = -sn * e[j];
798 e[j] = cs * e[j];
799 if (record) {
800 on_ut.push_back({row_operation::kind::rotate, j, zero, cs, sn});
801 }
802 }
803 continue;
804 }
805 if (steps == max_steps) {
806 throw convergence_error("SVD: the bidiagonal QR iteration did not converge within its steps");
807 }
808 ++steps;
809 if (top > chased_last || p - 1 < chased_top) { // a new block: chase from its larger end
810 down = std::abs(d[top]) >= std::abs(d[p - 1]);
811 }
812 chased_top = top;
813 chased_last = p - 1;
814 if (down) {
815 qr_step(top, p, [&](std::size_t position) -> double& { return d[position]; },
816 [&](std::size_t position) -> double& { return e[position]; }, [](std::size_t position) { return position; }, on_vt, on_ut);
817 }
818 else {
819 // The step on the block turned end for end (J Bᵀ J, upper bidiagonal again): its rotations on the right are
820 // B's on the left at the mirrored rows, and the other way round.
821 const std::size_t ends {top + p - 1};
822 qr_step(top, p, [&](std::size_t position) -> double& { return d[ends - position]; },
823 [&](std::size_t position) -> double& { return e[ends - position - 1]; },
824 [ends](std::size_t position) { return ends - position; },
825 on_ut, on_vt);
826 }
827 }
828 if (!vt.empty()) {
831 }
832 }
833
838 template <typename Entry>
839 [[nodiscard]] double largest_magnitude(std::size_t rows,
840 std::size_t cols,
841 const Entry& entry)
842 {
843 const std::size_t bands {(rows + svd_band - 1) / svd_band};
844 std::vector<double> largest(bands, 0.0);
845 parallel_for(bands, memory_element_weight * svd_band * cols, [&](std::size_t band) {
846 double most {0.0};
847 for (std::size_t i {band * svd_band}; i < std::min(rows, (band + 1) * svd_band); ++i) {
848 for (std::size_t j {0}; j < cols; ++j) {
849 most = std::max(most, static_cast<double>(std::abs(entry(i, j))));
850 }
851 }
852 largest[band] = most;
853 });
854 const double scale {std::accumulate(largest.begin(), largest.end(), 0.0, [](double x, double y) { return std::max(x, y); })};
855 return power_of_two_scale(scale);
856 }
857
859 template <typename T>
861 {
862 const std::size_t rows {a.rows()};
863 const std::size_t cols {a.cols()};
864 buffer<T> entries(rows * cols);
865 const std::size_t piece {transpose_piece(cols * sizeof(T), rows * sizeof(T))};
866 parallel_for((cols + transpose_tile - 1) / transpose_tile, transpose_tile * rows, [&](std::size_t block) {
867 const std::size_t j0 {block * transpose_tile};
868 const std::size_t j1 {std::min(j0 + transpose_tile, cols)};
869 for (std::size_t i0 {0}; i0 < rows; i0 += transpose_tile) {
870 transpose_walk(j0, j1, i0, std::min(i0 + transpose_tile, rows), piece,
871 [&](std::size_t j, std::size_t i) { entries[(j * rows) + i] = conj_of(a(i, j)); });
872 }
873 });
874 return matrix<T> {cols, rows, std::move(entries)};
875 }
876
892 const buffer<double>& z,
893 std::size_t i,
894 std::size_t max_iterations,
895 double* below,
896 double* above)
897 {
898 buffer<double> delta(d.size(), double {});
899 const secular_solution root {solve_secular(z, 1.0, i, max_iterations, delta.data(), [&d](std::size_t o, std::size_t j) {
900 return (d[j] - d[o]) * (d[j] + d[o]);
901 })};
902 const double pole {d[root.origin]};
903 const double shift {root.offset / (pole + std::sqrt((pole * pole) + root.offset))}; // σ − d_o from σ² − d_o²
904 for (std::size_t j {0}; j < d.size(); ++j) {
905 below[j] = (d[j] - pole) - shift;
906 above[j] = (d[j] + pole) + shift;
907 }
908 return pole + shift;
909 }
910
913 std::size_t cols,
914 std::size_t a,
915 std::size_t b,
916 double c,
917 double s)
918 {
919 for (std::size_t r {0}; r < m.size() / cols; ++r) {
920 const double x {m[(r * cols) + a]};
921 const double y {m[(r * cols) + b]};
922 m[(r * cols) + a] = (c * x) + (s * y);
923 m[(r * cols) + b] = (c * y) - (s * x);
924 }
925 }
926
928 inline constexpr std::size_t sort_rows {64};
929
942
948 {
949 thread_local arrow_workspace work;
950 [[maybe_unused]] thread_local const bool registered {on_release([] { work = arrow_workspace {}; })};
951 return work;
952 }
953
956 {
957 for (workspace_buffer* buffer : {&work.below, &work.above, &work.new_u, &work.new_v,
958 &work.columns, &work.factor}) {
959 if (buffer->size > kept_workspace) {
960 buffer->data.reset();
961 buffer->size = 0;
962 }
963 }
964 }
965
991 double alpha,
992 double beta,
995 std::size_t n,
996 std::size_t m,
997 std::size_t split,
998 arrow_workspace& work)
999 {
1000 // The rows each column reaches: 1 the upper half's, 2 u's row `split` (the arrow's first), 4 the lower half's.
1001 // A rotation of two columns makes each reach the rows of both.
1002 std::vector<unsigned> reach_u(n, 4U);
1003 std::vector<unsigned> reach_v(m, 4U);
1004 reach_u[0] = 2U;
1005 reach_v[0] = m > n ? 5U : 1U; // the upper half's null vector, turned with the lower one's when there is one
1006 for (std::size_t j {1}; j <= split; ++j) {
1007 reach_u[j] = 1U;
1008 reach_v[j] = 1U;
1009 }
1010 const auto turned {[](std::vector<unsigned>& reach, std::size_t a, std::size_t b) {
1011 reach[a] = reach[b] = reach[a] | reach[b];
1012 }};
1013 std::vector<std::size_t> order(n - 1);
1014 for (std::size_t j {1}; j < n; ++j) {
1015 order[j - 1] = j;
1016 }
1017 std::sort(order.begin(), order.end(), [&d](std::size_t x, std::size_t y) { return d[x] < d[y]; });
1018 double largest {std::max(std::abs(alpha), std::abs(beta))};
1019 for (const double value : d) {
1020 largest = std::max(largest, value);
1021 }
1022 if (largest == 0.0) {
1023 return; // a zero arrow: its singular values are zeros, its vectors the bases as they are
1024 }
1025 const double tolerance {8.0 * std::numeric_limits<double>::epsilon() * largest};
1026 if (std::abs(z[0]) <= tolerance) {
1027 z[0] = tolerance; // the zero pole keeps a weight: the arrow moves by no more than the tolerance
1028 }
1029 std::vector<std::size_t> kept {0}; // by ascending d, the zero pole first
1030 std::vector<std::size_t> deflated; // the columns that keep their singular value
1031 std::size_t pending {n}; // the last column kept so far, still open to a rotation with the next
1032 for (const std::size_t j : order) {
1033 if (std::abs(z[j]) <= tolerance) {
1034 deflated.push_back(j);
1035 continue;
1036 }
1037 if (d[j] <= tolerance) {
1038 // Nearly the zero pole: its weight joins the zero pole's, and dⱼ deflates.
1039 const double length {std::hypot(z[0], z[j])};
1040 rotate_columns(v, m, 0, j, z[0] / length, z[j] / length);
1041 turned(reach_v, 0, j);
1042 z[0] = length;
1043 z[j] = 0.0;
1044 deflated.push_back(j);
1045 continue;
1046 }
1047 if (pending != n && d[j] - d[pending] <= tolerance) {
1048 // Close values: one rotation of both rows and columns zeroes the pending one's weight.
1049 const double length {std::hypot(z[j], z[pending])};
1050 const double c {z[j] / length};
1051 const double s {z[pending] / length};
1052 rotate_columns(v, m, j, pending, c, s);
1053 rotate_columns(u, n, j, pending, c, s);
1054 turned(reach_v, j, pending);
1055 turned(reach_u, j, pending);
1056 z[j] = length;
1057 z[pending] = 0.0;
1058 deflated.push_back(pending);
1059 }
1060 else if (pending != n) {
1061 kept.push_back(pending);
1062 }
1063 pending = j;
1064 }
1065 if (pending != n) {
1066 kept.push_back(pending);
1067 }
1068 const std::size_t k {kept.size()};
1069 buffer<double> poles(k, double {});
1070 buffer<double> weights(k, double {});
1071 for (std::size_t i {0}; i < k; ++i) {
1072 poles[i] = d[kept[i]];
1073 weights[i] = z[kept[i]];
1074 }
1075 buffer<double> roots(k, double {});
1076 double* const below {workspace_of(work.below, k * k)}; // below[i * k + j] = poles[j] − roots[i]
1077 double* const above {workspace_of(work.above, k * k)}; // above[i * k + j] = poles[j] + roots[i]
1078 parallel_for(k, 8 * k, [&](std::size_t i) {
1079 roots[i] = singular_secular_root(poles, weights, i, secular_iterations, below + (i * k), above + (i * k));
1080 });
1081 // below[i * k + j] ← (poles[j] − roots[i]) (poles[j] + roots[i]), the product each later use takes: above is free.
1082 parallel_for(k, k, [&](std::size_t i) {
1083 for (std::size_t j {0}; j < k; ++j) {
1084 below[(i * k) + j] *= above[(i * k) + j];
1085 }
1086 });
1087 double* const squares {below}; // squares[i * k + j] = poles[j]² − roots[i]²
1088 // Löwner: ẑⱼ² = Πᵢ (σᵢ² − dⱼ²) / Πᵢ≠ⱼ (dᵢ² − dⱼ²), each pole paired with its root, by blocks of poles on every
1089 // core, each pole's product in ascending order of the roots (a row of the gaps at a time, along the block).
1090 buffer<double> signed_weights(k, double {});
1091 parallel_for((k + lowner_block - 1) / lowner_block, lowner_block * k, [&](std::size_t block) {
1092 const std::size_t first {block * lowner_block};
1093 const std::size_t last {std::min(first + lowner_block, k)};
1094 std::array<double, lowner_block> product {};
1095 for (std::size_t j {first}; j < last; ++j) {
1096 product[j - first] = -squares[(j * k) + j];
1097 }
1098 for (std::size_t i {0}; i < k; ++i) {
1099 for (std::size_t j {first}; j < last; ++j) {
1100 if (i != j) {
1101 product[j - first] *= -squares[(i * k) + j] / ((poles[i] - poles[j]) * (poles[i] + poles[j]));
1102 }
1103 }
1104 }
1105 for (std::size_t j {first}; j < last; ++j) {
1106 signed_weights[j] = std::copysign(std::sqrt(product[j - first]), weights[j]);
1107 }
1108 });
1109 // The vectors by rows of poles, each on its own core: right[j][i] = ẑⱼ / (dⱼ² − σᵢ²), read a column of the squares,
1110 // into above's storage; then the left ones, poles[j] times the right, into the squares' (column i: the vectors of
1111 // roots[i], in the kept columns' basis).
1112 double* const right {above};
1113 parallel_for(k, 4 * k, [&](std::size_t j) {
1114 for (std::size_t i {0}; i < k; ++i) {
1115 right[(j * k) + i] = signed_weights[j] / squares[(i * k) + j]; // ẑⱼ / (dⱼ² − σᵢ²)
1116 }
1117 });
1118 double* const left {below};
1119 parallel_for(k, k, [&](std::size_t j) {
1120 for (std::size_t i {0}; i < k; ++i) {
1121 left[(j * k) + i] = j == 0 ? -1.0 : poles[j] * right[(j * k) + i];
1122 }
1123 });
1124 for (double* const vectors : {left, right}) {
1125 buffer<double> length(k, 0.0);
1126 for (std::size_t j {0}; j < k; ++j) { // by rows, each a contiguous update of every column's sum
1127 for (std::size_t i {0}; i < k; ++i) {
1128 length[i] += vectors[(j * k) + i] * vectors[(j * k) + i];
1129 }
1130 }
1131 for (double& l : length) {
1132 l = std::sqrt(l);
1133 }
1134 parallel_for(k, k, [&](std::size_t j) {
1135 for (std::size_t i {0}; i < k; ++i) {
1136 vectors[(j * k) + i] /= length[i];
1137 }
1138 });
1139 }
1140 // The kept columns times the arrow's vectors; the deflated columns as they are; then by ascending value.
1141 // By segments of rows, each taking the kept columns that reach it and their rows of the arrow's vectors: the
1142 // others are zero there, and an element's sum without them is the same to the bit.
1143 using segment = std::tuple<std::size_t, std::size_t, unsigned>; // first row, rows, the bit of reach
1144 const auto carried {[&](const buffer<double>& basis, std::size_t rows, const double* small,
1145 const std::vector<unsigned>& reach, const std::vector<segment>& segments, double* product) {
1146 for (const auto& [first, count, bit] : segments) {
1147 std::vector<std::size_t> reaching;
1148 for (std::size_t i {0}; i < k; ++i) {
1149 if ((reach[kept[i]] & bit) != 0U) {
1150 reaching.push_back(i);
1151 }
1152 }
1153 const std::size_t width {reaching.size()};
1154 double* const columns {workspace_of(work.columns, count * width)};
1155 double* const factor {workspace_of(work.factor, width * k)};
1156 parallel_for(count, width + k, [&](std::size_t r) {
1157 for (std::size_t c {0}; c < width; ++c) {
1158 columns[(r * width) + c] = basis[((first + r) * rows) + kept[reaching[c]]];
1159 }
1160 std::fill_n(product + ((first + r) * k), k, 0.0); // the product adds to it
1161 });
1162 for (std::size_t c {0}; c < width; ++c) {
1163 std::copy_n(small + (reaching[c] * k), k, factor + (c * k));
1164 }
1165 gemm(count, k, width, columns, width, factor, k, product + (first * k), k);
1166 }
1167 }};
1168 double* const new_u {workspace_of(work.new_u, n * k)};
1169 double* const new_v {workspace_of(work.new_v, m * k)};
1170 carried(u, n, left, reach_u, {{0, split, 1U}, {split, 1, 2U}, {split + 1, n - split - 1, 4U}}, new_u);
1171 carried(v, m, right, reach_v, {{0, split + 1, 1U}, {split + 1, m - split - 1, 4U}}, new_v);
1172 buffer<double> values(n, double {});
1173 std::vector<std::size_t> from(n); // where each value's vectors are: a kept root (< k) or a deflated column
1174 for (std::size_t i {0}; i < k; ++i) {
1175 values[i] = roots[i];
1176 from[i] = i;
1177 }
1178 for (std::size_t i {0}; i < deflated.size(); ++i) {
1179 values[k + i] = d[deflated[i]];
1180 from[k + i] = k + i;
1181 }
1182 std::vector<std::size_t> rank(n);
1183 for (std::size_t j {0}; j < n; ++j) {
1184 rank[j] = j;
1185 }
1186 std::sort(rank.begin(), rank.end(), [&values](std::size_t x, std::size_t y) { return values[x] < values[y]; });
1187 std::vector<std::size_t> source(n); // by sorted column: a kept root (< k) or a deflated column (k + its place)
1188 for (std::size_t c {0}; c < n; ++c) {
1189 source[c] = from[rank[c]];
1190 d[c] = values[rank[c]];
1191 }
1192 // Row by row on every core, in place: a row of the result reads only that row of the old basis (and of the
1193 // product), so each is gathered into a row of its own, then written over it (by columns, each write was a row
1194 // apart; a copy of each basis held one matrix more apiece). The right basis's null column, if any, stays last.
1195 parallel_for((m + sort_rows - 1) / sort_rows, sort_rows * n, [&](std::size_t block) {
1196 buffer<double> row(n); // written whole for each row
1197 for (std::size_t r {block * sort_rows}; r < std::min(m, (block + 1) * sort_rows); ++r) {
1198 if (r < n) { // m ≥ n: the right basis has the rows of both
1199 for (std::size_t c {0}; c < n; ++c) {
1200 row[c] = source[c] < k ? new_u[(r * k) + source[c]] : u[(r * n) + deflated[source[c] - k]];
1201 }
1202 std::copy(row.begin(), row.end(), u.begin() + static_cast<std::ptrdiff_t>(r * n));
1203 }
1204 for (std::size_t c {0}; c < n; ++c) {
1205 row[c] = source[c] < k ? new_v[(r * k) + source[c]] : v[(r * m) + deflated[source[c] - k]];
1206 }
1207 std::copy(row.begin(), row.end(), v.begin() + static_cast<std::ptrdiff_t>(r * m));
1208 }
1209 });
1210 }
1211
1213 inline constexpr std::size_t bidiagonal_leaf {32};
1214
1220 {
1221 const double* d {};
1222 const double* e {};
1223 std::size_t n {};
1224 std::size_t extra {};
1225 int exponent {0};
1226 buffer<double> scaled_d {};
1227 buffer<double> scaled_e {};
1228 std::size_t k {0};
1229 std::size_t first {};
1230 std::size_t second {};
1231 std::size_t depth {};
1235 };
1236
1243 NUMERICAL_OUT_OF_LINE inline std::size_t plan_bidiagonal(std::vector<bidiagonal_node>& nodes,
1244 const double* d,
1245 const double* e,
1246 std::size_t n,
1247 std::size_t extra,
1248 std::size_t depth)
1249 {
1250 double largest {0.0};
1251 for (std::size_t i {0}; i < n; ++i) {
1252 largest = std::max({largest, std::abs(d[i]), i + 1 < n + extra ? std::abs(e[i]) : 0.0});
1253 }
1254 bidiagonal_node node {.d = d, .e = e, .n = n, .extra = extra, .depth = depth};
1255 (void)std::frexp(largest, &node.exponent);
1256 if (node.exponent != 0) {
1257 node.scaled_d.assign(n, double {});
1258 node.scaled_e.assign(n, 0.0);
1259 for (std::size_t i {0}; i < n; ++i) {
1260 node.scaled_d[i] = std::ldexp(d[i], -node.exponent);
1261 node.scaled_e[i] = i + 1 < n + extra ? std::ldexp(e[i], -node.exponent) : 0.0;
1262 }
1263 node.d = node.scaled_d.data(); // the buffers' storage stays put as the node moves into the vector
1264 node.e = node.scaled_e.data();
1265 }
1266 const std::size_t index {nodes.size()};
1267 if (n <= bidiagonal_leaf) {
1268 nodes.push_back(std::move(node));
1269 return index;
1270 }
1271 node.k = n / 2;
1272 const double* const work_d {node.d};
1273 const double* const work_e {node.e};
1274 const std::size_t k {node.k};
1275 nodes.push_back(std::move(node));
1276 const std::size_t first {plan_bidiagonal(nodes, work_d, work_e, k, 1, depth + 1)};
1277 const std::size_t second {plan_bidiagonal(nodes, work_d + k + 1, work_e + k + 1, n - k - 1, extra, depth + 1)};
1278 nodes[index].first = first;
1279 nodes[index].second = second;
1280 return index;
1281 }
1282
1285 {
1286 const std::size_t m {node.n + node.extra};
1287 node.sigma.assign(node.n, 0.0);
1288 node.u.assign(node.n * node.n, 0.0);
1289 node.v.assign(m * m, 0.0);
1290 for (std::size_t i {0}; i < m; ++i) {
1291 node.v[(i * m) + i] = 1.0;
1292 }
1293 }
1294
1297 {
1299 const double* const d {node.d};
1300 const double* const e {node.e};
1301 const std::size_t n {node.n};
1302 const std::size_t extra {node.extra};
1303 const std::size_t m {n + extra};
1304 buffer<double>& sigma {node.sigma};
1305 buffer<double>& u {node.u};
1306 buffer<double>& v {node.v};
1307 buffer<double> diagonal(d, d + n);
1308 buffer<double> super(n, 0.0);
1309 std::copy_n(e, n - std::min<std::size_t>(n, 1), super.begin());
1310 // An extra column first: rotations of it against each column, from the last row up, chase its one entry
1311 // out (B G = [B' 0]), so the square B' remains.
1312 double fill {extra == 1 ? e[n - 1] : 0.0};
1313 for (std::size_t j {n}; extra == 1 && j-- > 0;) {
1314 const double length {std::hypot(diagonal[j], fill)};
1315 const double c {length == 0.0 ? 1.0 : diagonal[j] / length};
1316 const double s {length == 0.0 ? 0.0 : fill / length};
1317 diagonal[j] = length;
1318 rotate_columns(v, m, j, n, c, s);
1319 if (j > 0) {
1320 fill = -s * super[j - 1];
1321 super[j - 1] = c * super[j - 1];
1322 }
1323 }
1324 buffer<double> ut(n * n, 0.0);
1325 buffer<double> vt(n * n, 0.0);
1326 for (std::size_t i {0}; i < n; ++i) {
1327 ut[(i * n) + i] = 1.0;
1328 vt[(i * n) + i] = 1.0;
1329 }
1330 bidiagonal_qr(diagonal, super, ut, vt, n, svd_qr_steps_per_value * n); // descending
1331 const buffer<double> rotated {extra == 1 ? v : buffer<double> {}}; // G; without an extra column, the identity
1332 for (std::size_t c {0}; c < n; ++c) {
1333 const std::size_t source {n - 1 - c};
1334 sigma[c] = diagonal[source];
1335 for (std::size_t r {0}; r < n; ++r) {
1336 u[(r * n) + c] = ut[(source * n) + r];
1337 }
1338 for (std::size_t r {0}; r < m; ++r) { // G times B''s right vector
1339 double sum {extra == 1 ? 0.0 : vt[(source * n) + r]};
1340 for (std::size_t t {0}; extra == 1 && t < n; ++t) {
1341 sum += rotated[(r * m) + t] * vt[(source * n) + t];
1342 }
1343 v[(r * m) + c] = sum;
1344 }
1345 }
1346 }
1347
1351 const bidiagonal_node& one,
1352 const bidiagonal_node& two,
1353 arrow_workspace& work)
1354 {
1355 const std::size_t n {node.n};
1356 const std::size_t extra {node.extra};
1357 const std::size_t m {n + extra};
1358 const std::size_t k {node.k};
1359 const std::size_t lower {n - k - 1};
1360 const double alpha {node.d[k]};
1361 const double beta {node.e[k]};
1362 const buffer<double>& sigma1 {one.sigma};
1363 const buffer<double>& u1 {one.u};
1364 const buffer<double>& v1 {one.v};
1365 const buffer<double>& sigma2 {two.sigma};
1366 const buffer<double>& u2 {two.u};
1367 const buffer<double>& v2 {two.v};
1368 buffer<double>& u {node.u};
1369 buffer<double>& v {node.v};
1370 const std::size_t m1 {k + 1};
1371 const std::size_t m2 {lower + extra};
1372 buffer<double> arrow(n, 0.0);
1373 buffer<double> z(n, 0.0);
1374 // The bases: row k is the arrow's first row; the arrow's columns are the null vector, then the halves'.
1375 u[k * n] = 1.0;
1376 for (std::size_t c {0}; c < k; ++c) {
1377 arrow[1 + c] = sigma1[c];
1378 z[1 + c] = alpha * v1[(k * m1) + c];
1379 for (std::size_t r {0}; r < k; ++r) {
1380 u[(r * n) + 1 + c] = u1[(r * k) + c];
1381 }
1382 }
1383 for (std::size_t c {0}; c < lower; ++c) {
1384 arrow[k + 1 + c] = sigma2[c];
1385 z[k + 1 + c] = beta * v2[c];
1386 for (std::size_t r {0}; r < lower; ++r) {
1387 u[((k + 1 + r) * n) + k + 1 + c] = u2[(r * lower) + c];
1388 }
1389 }
1390 std::fill(v.begin(), v.end(), 0.0);
1391 for (std::size_t r {0}; r < m1; ++r) {
1392 v[(r * m) + 0] = v1[(r * m1) + k];
1393 for (std::size_t c {0}; c < k; ++c) {
1394 v[(r * m) + 1 + c] = v1[(r * m1) + c];
1395 }
1396 }
1397 for (std::size_t r {0}; r < m2; ++r) {
1398 for (std::size_t c {0}; c < lower; ++c) {
1399 v[((m1 + r) * m) + k + 1 + c] = v2[(r * m2) + c];
1400 }
1401 }
1402 z[0] = alpha * v1[(k * m1) + k];
1403 if (extra == 1) { // the two null vectors: one joins the arrow, the other is the whole's
1404 for (std::size_t r {0}; r < m2; ++r) {
1405 v[((m1 + r) * m) + n] = v2[(r * m2) + lower];
1406 }
1407 const double other {beta * v2[lower]};
1408 const double length {std::hypot(z[0], other)};
1409 const double c {length == 0.0 ? 1.0 : z[0] / length};
1410 const double s {length == 0.0 ? 0.0 : other / length};
1411 rotate_columns(v, m, 0, n, c, s);
1412 z[0] = length;
1413 }
1414 merge_arrow(arrow, std::move(z), alpha, beta, u, v, n, m, k, work);
1415 node.sigma = std::move(arrow);
1416 }
1417
1420 {
1421 if (node.exponent != 0) {
1422 for (double& value : node.sigma) {
1423 value = std::ldexp(value, node.exponent);
1424 }
1425 }
1426 }
1427
1429 NUMERICAL_OUT_OF_LINE inline void join_bidiagonal_halves(std::vector<bidiagonal_node>& nodes,
1430 std::size_t index,
1431 arrow_workspace& work)
1432 {
1433 bidiagonal_node& node {nodes[index]};
1434 join_bidiagonal_node(node, nodes[node.first], nodes[node.second], work);
1436 nodes[node.first] = bidiagonal_node {}; // read by no other join
1437 nodes[node.second] = bidiagonal_node {};
1438 }
1439
1441 NUMERICAL_OUT_OF_LINE inline void solve_bidiagonal_subtree(std::vector<bidiagonal_node>& nodes,
1442 std::size_t index,
1443 arrow_workspace& work)
1444 {
1445 if (nodes[index].k == 0) {
1448 return;
1449 }
1450 start_bidiagonal_node(nodes[index]); // before its halves, as the recursion did: their buffers then come back to it
1451 solve_bidiagonal_subtree(nodes, nodes[index].first, work);
1452 solve_bidiagonal_subtree(nodes, nodes[index].second, work);
1453 join_bidiagonal_halves(nodes, index, work);
1454 }
1455
1474 inline void bidiagonal_divide(const double* d,
1475 const double* e,
1476 std::size_t n,
1477 std::size_t extra,
1478 buffer<double>& sigma,
1479 buffer<double>& u,
1480 buffer<double>& v)
1481 {
1482 std::vector<bidiagonal_node> nodes;
1483 (void)plan_bidiagonal(nodes, d, e, n, extra, 0);
1484 const auto cut {static_cast<std::size_t>(std::bit_width(max_threads() - 1))};
1485 std::vector<std::size_t> tasks;
1486 for (std::size_t i {0}; i < nodes.size(); ++i) {
1487 if (nodes[i].depth == cut || (nodes[i].depth < cut && nodes[i].k == 0)) {
1488 tasks.push_back(i);
1489 }
1490 }
1491 const std::size_t task_order {nodes[tasks[0]].n};
1492 parallel_for(tasks.size(), tasks.size() > 1 ? task_order * task_order * task_order : 0, [&](std::size_t t) {
1495 });
1496 for (std::size_t level {cut}; level-- > 0;) {
1497 std::vector<std::size_t> joins;
1498 for (std::size_t i {0}; i < nodes.size(); ++i) {
1499 if (nodes[i].k != 0 && nodes[i].depth == level) {
1500 joins.push_back(i);
1501 }
1502 }
1503 const std::size_t order {joins.empty() ? 0 : nodes[joins[0]].n};
1504 parallel_for(joins.size(), joins.size() > 1 ? order * order * order / 4 : 0, [&](std::size_t j) {
1508 });
1509 }
1510 sigma = std::move(nodes[0].sigma);
1511 u = std::move(nodes[0].u);
1512 v = std::move(nodes[0].v);
1513 }
1514
1521 template <typename T>
1523 buffer<double>& e,
1524 buffer<T>& ut,
1525 buffer<T>& vt,
1526 std::size_t n)
1527 {
1528 if (n == 0) {
1529 return;
1530 }
1531 buffer<double> sigma;
1534 bidiagonal_divide(d.data(), e.data(), n, 0, sigma, u, v);
1535 buffer<double> left(n * n, double {}); // row c: the vectors of the c-th largest value
1536 buffer<double> right(n * n, double {});
1537 for (std::size_t c {0}; c < n; ++c) {
1538 d[c] = sigma[n - 1 - c];
1539 for (std::size_t r {0}; r < n; ++r) {
1540 left[(c * n) + r] = u[(r * n) + (n - 1 - c)];
1541 right[(c * n) + r] = v[(r * n) + (n - 1 - c)];
1542 }
1543 }
1546 }
1547 } // namespace detail
1548
1550 enum class svd_method
1551 {
1552 bidiagonal_qr,
1553 jacobi,
1554 divide_and_conquer
1555 };
1556
1557 namespace detail {
1559 [[nodiscard]] inline double singular_value_in_double(double x) noexcept
1560 {
1561 return x;
1562 }
1563
1570 [[nodiscard]] inline double singular_value_in_double(long double x)
1571 {
1572#if LDBL_MAX_EXP > DBL_MAX_EXP
1573 const double narrowed {static_cast<double>(x)};
1574 if (x != 0.0L && !(std::abs(narrowed) >= std::numeric_limits<double>::min() && std::abs(narrowed) <= std::numeric_limits<double>::max())) {
1575 throw argument_error("SVD: a singular value past double's range, in which the SVD of a long double matrix computes");
1576 }
1577 return narrowed;
1578#else
1579 return static_cast<double>(x);
1580#endif
1581 }
1582 } // namespace detail
1583
1599 template <field T>
1601 {
1602 public:
1603
1612 explicit svd_decomposition(const matrix<T>& a,
1613 svd_method method = svd_method::divide_and_conquer,
1614 bool full = false)
1615 {
1616 detail::require_finite(a, "SVD");
1617 if (a.rows() >= a.cols()) {
1618 factor(a, method, full);
1619 }
1620 else { // A = (Aᴴ)ᴴ = (U' Σ V'ᴴ)ᴴ = V' Σ U'ᴴ
1621 factor(detail::adjoint(a), method, full);
1622 std::swap(u_, v_);
1623 }
1624 }
1625
1636 svd_method method = svd_method::divide_and_conquer,
1637 bool full = false)
1638 {
1639 detail::require_finite(a, "SVD");
1640 if (a.rows() >= a.cols()) {
1641 factor(std::move(a), method, full);
1642 }
1643 else { // as the constructor of a constant matrix
1644 factor(detail::adjoint(a), method, full);
1645 std::swap(u_, v_);
1646 }
1647 }
1648
1650 [[nodiscard]] const vector<double>& singular_values() const noexcept
1651 {
1652 return singular_values_;
1653 }
1654
1656 [[nodiscard]] const matrix<T>& u() const& noexcept
1657 {
1658 return u_;
1659 }
1660
1662 [[nodiscard]] matrix<T> u() &&
1663 {
1664 return std::move(u_);
1665 }
1666
1668 [[nodiscard]] const matrix<T>& v() const& noexcept
1669 {
1670 return v_;
1671 }
1672
1675 [[nodiscard]] matrix<T> vh() const
1676 {
1677 return detail::adjoint(v_);
1678 }
1679
1680 private:
1681
1687 [[nodiscard]] static matrix<T> applied_left_vectors(const buffer<T>& left,
1688 const std::vector<detail::reflector_block<T>>& blocks,
1689 const std::vector<T>& phases,
1690 std::size_t rows,
1691 std::size_t cols,
1692 std::size_t width)
1693 {
1694 buffer<T> u(rows * width, T {});
1695 for (std::size_t i {0}; i < cols; ++i) {
1696 for (std::size_t j {0}; j < cols; ++j) {
1697 u[(i * width) + j] = phases[i] * left[(i * cols) + j];
1698 }
1699 }
1700 for (std::size_t i {cols}; i < width; ++i) {
1701 u[(i * width) + i] = T {1};
1702 }
1703 detail::apply_q(u, blocks, rows, width);
1704 return matrix<T> {rows, width, std::move(u)};
1705 }
1706
1711 [[nodiscard]] static matrix<T> left_vectors(buffer<T> q,
1712 buffer<T> left,
1713 std::size_t rows,
1714 std::size_t cols,
1715 std::size_t width)
1716 {
1717 if (width == cols) {
1718 return matrix<T> {rows, cols, std::move(q)} *matrix<T> {cols, cols, std::move(left)};
1719 }
1720 buffer<T> u(rows * rows, T {});
1721 detail::gemm(rows, cols, cols, q.data(), rows, left.data(), cols, u.data(), rows);
1722 for (std::size_t i {0}; i < rows; ++i) {
1723 for (std::size_t j {cols}; j < rows; ++j) {
1724 u[(i * rows) + j] = q[(i * rows) + j];
1725 }
1726 }
1727 return matrix<T> {rows, rows, std::move(u)};
1728 }
1729
1732 void factor(const matrix<T>& a,
1733 svd_method method,
1734 bool full)
1735 {
1736 factor_scaled(std::to_address(a.begin()), buffer<T>(a.rows() * a.cols()), a.rows(), a.cols(), method, full);
1737 }
1738
1741 svd_method method,
1742 bool full)
1743 {
1744 const std::size_t rows {a.rows()};
1745 const std::size_t cols {a.cols()};
1746 buffer<T> entries {std::move(a).elements()};
1747 const T* const source {entries.data()};
1748 factor_scaled(source, std::move(entries), rows, cols, method, full);
1749 }
1750
1755 void factor_scaled(const T* source,
1756 buffer<T> entries,
1757 std::size_t rows,
1758 std::size_t cols,
1759 svd_method method,
1760 bool full)
1761 {
1762 // Work on A divided by its largest magnitude: the sums of squares in the sweeps overflow near
1763 // 1e155 and underflow near 1e-155. The singular values are scaled back; the vectors do not change.
1764 // Both passes by bands of rows on the threads, bound by the memory: a band's largest magnitude, then the
1765 // largest of those (exact in any order), then the quotients.
1766 // In the scalar's carried type: a long double matrix past double's range scaled into it, where its largest
1767 // magnitude read as a double was 0 or infinite (and the scale 1).
1768 using carried = detail::carried_t<T>;
1769 const std::size_t bands {(rows + detail::svd_band - 1) / detail::svd_band};
1770 std::vector<carried> largest(bands, carried {0});
1771 detail::parallel_for(bands, detail::memory_element_weight * detail::svd_band * cols, [source, rows, cols, &largest](std::size_t band) {
1772 carried most {0};
1773 for (std::size_t e {band * detail::svd_band * cols}; e < std::min(rows, (band + 1) * detail::svd_band) * cols; ++e) {
1774 most = std::max(most, static_cast<carried>(std::abs(source[e])));
1775 }
1776 largest[band] = most;
1777 });
1778 // the largest over no band (no row) is 0, as over zeros
1779 const carried most {std::accumulate(largest.begin(), largest.end(), carried {0}, [](carried x, carried y) { return std::max(x, y); })};
1780 const carried scale {most == carried {0} ? carried {1} : std::ldexp(carried {1}, std::ilogb(most))};
1781 T* const into {entries.data()};
1782 const T divisor {detail::from_carried<T>(scale)};
1783 detail::parallel_for(bands, detail::memory_element_weight * detail::svd_band * cols, [source, into, rows, cols, divisor](std::size_t band) {
1784 for (std::size_t e {band * detail::svd_band * cols}; e < std::min(rows, (band + 1) * detail::svd_band) * cols; ++e) {
1785 into[e] = source[e] / divisor;
1786 }
1787 });
1788 // A square matrix is reduced to bidiagonal form as it is (as LAPACK's dgesdd does short of a tall one): a QR
1789 // first, its Q formed and multiplied in at the end, took a third of the decomposition's time at order 1024.
1790 const bool direct {rows == cols && method != svd_method::jacobi};
1791 const std::size_t width {full ? rows : cols};
1792 // A tall matrix's U is Q times R's, taken through Q's reflectors (applied), where Q formed then multiplied in took
1793 // as much work again and held a matrix more (ten AVX-512 cores, one thread, 1000 × 100: 9.8 → 8.4 ms).
1794 const bool applied {!direct && method != svd_method::jacobi};
1795 std::vector<detail::reflector_block<T>> blocks;
1796 std::vector<T> phases;
1797 detail::thin_qr<T> factors;
1798 if (direct) {
1799 factors.r = std::move(entries);
1800 }
1801 else if (applied) {
1802 detail::qr_reflections<T> reflections {detail::householder_reflect(std::move(entries), rows, cols)};
1803 blocks = std::move(reflections.blocks);
1804 factors.r = std::move(reflections.r);
1805 phases.resize(cols);
1806 for (std::size_t k {0}; k < cols; ++k) { // R's diagonal real and non-negative, as householder_qr makes it
1807 phases[k] = detail::phase_of(factors.r[(k * cols) + k]);
1808 for (std::size_t j {k}; j < cols; ++j) {
1809 factors.r[(k * cols) + j] *= detail::conj_of(phases[k]);
1810 }
1811 }
1812 }
1813 else {
1814 factors = detail::householder_qr(std::move(entries), rows, cols, full);
1815 }
1816 if (method != svd_method::jacobi) {
1817 buffer<double> d(cols, double {});
1818 buffer<double> e(cols, double {});
1819 buffer<T> ut;
1820 buffer<T> vt;
1821 detail::bidiagonalize(factors.r, cols, d, e, ut, vt);
1822 factors.r = buffer<T> {}; // read no more: its storage back before the vectors' updates
1823 if (method == svd_method::bidiagonal_qr) {
1824 detail::bidiagonal_qr(d, e, ut, vt, cols, detail::svd_qr_steps_per_value * cols);
1825 }
1826 else {
1827 detail::bidiagonal_divide_and_conquer(d, e, ut, vt, cols);
1828 }
1829 buffer<T> left(cols * cols); // rows of ut and vt are the vectors: made columns, each freed once copied
1830 detail::transpose_into(ut.data(), cols, cols, left.data());
1831 ut = buffer<T> {};
1832 buffer<T> right(cols * cols);
1833 detail::transpose_into(vt.data(), cols, cols, right.data());
1834 vt = buffer<T> {};
1835 for (double& value : d) {
1836 value = detail::singular_value_in_double(static_cast<carried>(value) * scale);
1837 }
1838 singular_values_ = vector<double> {std::move(d)};
1839 u_ = direct ? matrix<T> {cols, cols, std::move(left)} : applied_left_vectors(left, blocks, phases, rows, cols, width);
1840 v_ = matrix<T> {cols, cols, std::move(right)};
1841 return;
1842 }
1843 buffer<T> w {std::move(factors.r)}; // A = Q R, and R V = W with orthogonal columns
1844 buffer<T> right(cols * cols, T {});
1845 for (std::size_t i {0}; i < cols; ++i) {
1846 right[(i * cols) + i] = T {1};
1847 }
1848 detail::one_sided_jacobi(w, right, cols, detail::jacobi_sweeps);
1849
1850 buffer<double> norms(cols, double {});
1851 for (std::size_t j {0}; j < cols; ++j) {
1852 buffer<T> column(cols, T {});
1853 for (std::size_t i {0}; i < cols; ++i) {
1854 column[i] = w[(i * cols) + j];
1855 }
1856 norms[j] = static_cast<double>(detail::scaled_norm(column));
1857 }
1858 std::vector<std::size_t> order(cols);
1859 for (std::size_t j {0}; j < cols; ++j) {
1860 order[j] = j;
1861 }
1862 std::stable_sort(order.begin(), order.end(), [&norms](std::size_t x, std::size_t y) { return norms[x] > norms[y]; });
1863
1864 // The left vectors of R: each nonzero column of W over its norm; a zero one has none, and takes
1865 // the unit vector that leaves the largest residual against the columns already set, made
1866 // orthogonal to them.
1867 buffer<T> left(cols * cols, T {});
1868 buffer<T> sorted_right(cols * cols, T {});
1869 buffer<double> values(cols, double {});
1870 // the columns' storage's rounding: a float column's cosines are float's
1871 const double coarser_epsilon {std::max(static_cast<double>(std::numeric_limits<detail::value_range_t<T>>::epsilon()), std::numeric_limits<double>::epsilon())};
1872 // each unit vector e_k's residual against the columns already set, 1 − Σ |L(k, c)|²: a zero column takes the
1873 // largest's, made orthogonal to them (testing each unit vector by orthogonalising it cost n⁴ where most columns
1874 // are zero, a matrix of rank 1)
1875 std::vector<double> residual(cols, 1.0);
1876 for (std::size_t d {0}; d < cols; ++d) {
1877 if (d > 0) {
1878 for (std::size_t k {0}; k < cols; ++k) {
1879 residual[k] -= static_cast<double>(std::norm(left[(k * cols) + d - 1]));
1880 }
1881 }
1882 const std::size_t j {order[d]};
1883 values[d] = detail::singular_value_in_double(static_cast<carried>(norms[j]) * scale);
1884 for (std::size_t i {0}; i < cols; ++i) {
1885 sorted_right[(i * cols) + d] = right[(i * cols) + j];
1886 }
1887 if (norms[j] > 0.0) {
1888 buffer<T> unit(cols, T {});
1889 for (std::size_t i {0}; i < cols; ++i) {
1890 unit[i] = w[(i * cols) + j] / detail::from_carried<T>(norms[j]);
1891 }
1892 // a column off those before it past what the sweeps leave is rounding the sweeps could not part (a
1893 // numerically rank-deficient matrix: ones(10, 7) left a column of norm 1e-309 beside its first): its
1894 // direction holds nothing, and it is completed as a zero column is
1895 if (largest_cosine(unit, left, cols, d) <= separate_columns * std::sqrt(static_cast<double>(cols)) * coarser_epsilon) {
1896 for (std::size_t i {0}; i < cols; ++i) {
1897 left[(i * cols) + d] = unit[i];
1898 }
1899 continue;
1900 }
1901 }
1902 buffer<T> best(cols, T {});
1903 best[static_cast<std::size_t>(std::ranges::max_element(residual) - residual.begin())] = T {1};
1904 orthogonalise(best, left, cols, d);
1905 orthogonalise(best, left, cols, d); // a second pass restores orthogonality lost to rounding
1906 const auto norm {static_cast<double>(detail::scaled_norm(best))};
1907 for (std::size_t i {0}; i < cols; ++i) {
1908 left[(i * cols) + d] = best[i] / detail::from_carried<T>(norm);
1909 }
1910 }
1911 singular_values_ = vector<double> {std::move(values)};
1912 u_ = left_vectors(std::move(factors.q), std::move(left), rows, cols, width);
1913 v_ = matrix<T> {cols, cols, std::move(sorted_right)};
1914 }
1915
1918 static constexpr double separate_columns {64.0};
1919
1921 [[nodiscard]] static double largest_cosine(const buffer<T>& x,
1922 const buffer<T>& basis,
1923 std::size_t n,
1924 std::size_t count)
1925 {
1926 double largest {0.0};
1927 for (std::size_t c {0}; c < count; ++c) {
1928 T projection {};
1929 for (std::size_t i {0}; i < n; ++i) {
1930 projection += detail::conj_of(basis[(i * n) + c]) * x[i];
1931 }
1932 largest = std::max(largest, static_cast<double>(std::abs(projection)));
1933 }
1934 return largest;
1935 }
1936
1938 static void orthogonalise(buffer<T>& x,
1939 const buffer<T>& basis,
1940 std::size_t n,
1941 std::size_t count)
1942 {
1943 for (std::size_t c {0}; c < count; ++c) {
1944 T projection {};
1945 for (std::size_t i {0}; i < n; ++i) {
1946 projection += detail::conj_of(basis[(i * n) + c]) * x[i];
1947 }
1948 for (std::size_t i {0}; i < n; ++i) {
1949 x[i] -= projection * basis[(i * n) + c];
1950 }
1951 }
1952 }
1953
1957 };
1958
1959 namespace detail {
1960
1963 [[nodiscard]] inline std::size_t numerical_rank(const vector<double>& sigma,
1964 std::size_t rows,
1965 std::size_t cols,
1966 rank_cutoff cutoff = {})
1967 {
1968 double largest {0.0};
1969 for (std::size_t d {0}; d < sigma.size(); ++d) {
1970 largest = std::max(largest, sigma[d]);
1971 }
1972 const double tolerance {cutoff.magnitude(largest, rows, cols)};
1973 std::size_t rank {0};
1974 for (std::size_t d {0}; d < sigma.size(); ++d) {
1975 rank += static_cast<std::size_t>(sigma[d] > tolerance);
1976 }
1977 return rank;
1978 }
1979
1982 inline constexpr double qr_rank_margin {100.0};
1983
1986 template <typename T>
1987 [[nodiscard]] T scaled_by_two(const T& x,
1988 int exponent)
1989 {
1990 return std::scalbn(x, exponent);
1991 }
1992
1994 template <typename U>
1995 [[nodiscard]] std::complex<U> scaled_by_two(const std::complex<U>& x,
1996 int exponent)
1997 {
1998 return std::complex<U> {std::scalbn(x.real(), exponent), std::scalbn(x.imag(), exponent)};
1999 }
2000
2006 template <typename T>
2007 [[nodiscard]] buffer<T> upper_inverse(const buffer<T>& r,
2008 std::size_t n)
2009 {
2010 constexpr std::size_t width {64};
2011 buffer<T> x(n * n, T {});
2012 parallel_for((n + width - 1) / width, n * n * width / 2, [&](std::size_t chunk) {
2013 const std::size_t first {chunk * width};
2014 const std::size_t last {std::min(first + width, n)};
2015 for (std::size_t i {last}; i-- > 0;) {
2016 T* const row {x.data() + (i * n) + first};
2017 if (i >= first) {
2018 row[i - first] = T {1};
2019 }
2020 subtract_products(row, r.data() + (i * n) + i + 1, x.data() + ((i + 1) * n) + first, n, last - (i + 1), last - first);
2021 for (std::size_t c {0}; c < last - first; ++c) {
2022 row[c] = row[c] / r[(i * n) + i];
2023 }
2024 }
2025 });
2026 return x;
2027 }
2028
2029 template <typename T>
2030 [[nodiscard]] buffer<double> square_singular_values(buffer<T> b,
2031 std::size_t n,
2032 qd_index sweeps = dqds_sweeps);
2033
2051 template <typename T>
2052 [[nodiscard]] std::optional<matrix<T>> lstsq_by_qr(const matrix<T>& a,
2053 const matrix<T>& b,
2054 rank_cutoff cutoff,
2055 buffer<double>& values,
2056 std::pair<buffer<T>, int>* const r = nullptr)
2057 {
2058 const std::size_t m {a.rows()};
2059 const std::size_t n {a.cols()};
2060 const bool wide {m < n};
2061 const std::size_t rows {wide ? n : m}; // of the matrix factorised
2062 const std::size_t cols {wide ? m : n};
2063 double largest {0.0};
2064 for (std::size_t i {0}; i < m; ++i) {
2065 for (std::size_t j {0}; j < n; ++j) {
2066 largest = std::max(largest, static_cast<double>(std::abs(a(i, j))));
2067 }
2068 }
2069 if (largest == 0.0) {
2070 return std::nullopt;
2071 }
2072 const int exponent {std::ilogb(largest)};
2073 buffer<T> entries(rows * cols, T {});
2074 for (std::size_t i {0}; i < m; ++i) {
2075 for (std::size_t j {0}; j < n; ++j) {
2076 if (wide) {
2077 entries[(j * cols) + i] = scaled_by_two(conj_of(a(i, j)), -exponent);
2078 }
2079 else {
2080 entries[(i * cols) + j] = scaled_by_two(a(i, j), -exponent);
2081 }
2082 }
2083 }
2084 qr_reflections<T> factors {householder_reflect(std::move(entries), rows, cols)};
2085 const buffer<T> inverse {upper_inverse(factors.r, cols)};
2086 double r_squares {0.0};
2087 double inverse_squares {0.0};
2088 for (std::size_t e {0}; e < cols * cols; ++e) {
2089 r_squares += static_cast<double>(std::norm(factors.r[e]));
2090 inverse_squares += static_cast<double>(std::norm(inverse[e]));
2091 }
2092 const double smallest_bound {1.0 / std::sqrt(inverse_squares)};
2093 if (!(smallest_bound > qr_rank_margin * cutoff.scaled(exponent).magnitude(std::sqrt(r_squares), m, n))) {
2094 // The bound is loose (a coarse cutoff, single precision's): R's own singular values decide, A's to within
2095 // the factorisation's rounding, far under the margin.
2096 buffer<double> sigma {square_singular_values(buffer<T>(factors.r), cols)};
2097 if (!(sigma.back() > qr_rank_margin * cutoff.scaled(exponent).magnitude(sigma.front(), m, n))) {
2098 return std::nullopt;
2099 }
2100 values = std::move(sigma);
2101 }
2102 const std::size_t k {b.cols()};
2103 buffer<T> x(n * k, T {});
2104 if (wide) { // x = Q [R⁻ᴴ B; 0]: the blocks applied last first
2105 const matrix<T> inverse_adjoint {adjoint(matrix<T> {cols, cols, inverse})};
2106 const buffer<T> right(b.begin(), b.end());
2107 gemm(cols, k, cols, &*inverse_adjoint.begin(), cols, right.data(), k, x.data(), k);
2108 for (std::size_t block {factors.blocks.size()}; block-- > 0;) {
2109 apply_reflector_block(factors.blocks[block], false, x, k, 0, k);
2110 }
2111 }
2112 else { // x = R⁻¹ times the first rows of Qᴴ B: the blocks' adjoints applied first first
2113 buffer<T> y(b.begin(), b.end());
2114 for (const reflector_block<T>& block : factors.blocks) {
2115 apply_reflector_block(block, true, y, k, 0, k);
2116 }
2117 gemm(n, k, cols, inverse.data(), cols, y.data(), k, x.data(), k);
2118 }
2119 for (T& value : x) {
2120 value = scaled_by_two(value, -exponent);
2121 }
2122 if (r != nullptr) {
2123 *r = {std::move(factors.r), exponent};
2124 }
2125 return matrix<T> {n, k, std::move(x)};
2126 }
2127
2143 template <typename T>
2145 std::size_t rows,
2146 std::size_t n,
2147 qd_index sweeps = dqds_sweeps)
2148 {
2149 buffer<double> d(n, double {});
2150 buffer<double> e(n, double {});
2152 buffer<T> none_too;
2153 if (rows == n) {
2154 bidiagonalize(b, n, d, e, none, none_too, false);
2155 }
2156 else {
2157 bidiagonalize_unblocked(b, rows, n, d, e, none, none_too, false);
2158 }
2159 if (!dqds_singular_values(d, e, n, sweeps)) {
2160 bidiagonal_qr(d, e, none, none_too, n, svd_qr_steps_per_value * n);
2161 }
2162 return d;
2163 }
2164
2165 template <typename T>
2167 std::size_t n,
2168 qd_index sweeps)
2169 {
2170 return tall_singular_values(std::move(b), n, n, sweeps);
2171 }
2172
2177 template <typename T>
2179 std::size_t rank,
2180 const matrix<T>& b)
2181 {
2182 // Through the matrix product kernel, as inverse_on_kept: the coefficients `Uᴴ B` (each row over its σ), then
2183 // `V` times them; summed term by term, each coefficient read U and B a column apart.
2184 const vector<double>& sigma {s.singular_values()};
2185 const std::size_t rows {s.u().rows()};
2186 const std::size_t cols {s.v().rows()};
2187 const std::size_t sides {b.cols()};
2188 buffer<T> left_adjoint(rank * rows);
2189 buffer<T> right(cols * rank);
2190 for (std::size_t d {0}; d < rank; ++d) {
2191 for (std::size_t i {0}; i < rows; ++i) {
2192 left_adjoint[(d * rows) + i] = conj_of(s.u()(i, d));
2193 }
2194 for (std::size_t j {0}; j < cols; ++j) {
2195 right[(j * rank) + d] = s.v()(j, d);
2196 }
2197 }
2198 buffer<T> coefficients(rank * sides);
2199 gemm(rank, sides, rows, left_adjoint.data(), rows, std::to_address(b.begin()), sides, coefficients.data(), sides, c_start::zero);
2200 for (std::size_t d {0}; d < rank; ++d) {
2201 for (std::size_t c {0}; c < sides; ++c) {
2202 coefficients[(d * sides) + c] /= from_carried<T>(sigma[d]);
2203 }
2204 }
2205 buffer<T> x(cols * sides);
2206 gemm(cols, sides, rank, right.data(), rank, coefficients.data(), sides, x.data(), sides, c_start::zero);
2207 return matrix<T> {cols, sides, std::move(x)};
2208 }
2209 } // namespace detail
2210
2225 template <field T>
2226 [[nodiscard]] vector<T> lstsq(const matrix<T>& a,
2227 const vector<T>& b,
2228 rank_cutoff cutoff = {})
2229 {
2230 const matrix<T> column {lstsq(a, matrix<T> {b.size(), 1, buffer<T>(b.begin(), b.end())}, cutoff)};
2231 return vector<T> {buffer<T>(column.begin(), column.end())};
2232 }
2233
2247 template <field T>
2248 [[nodiscard]] matrix<T> lstsq(const matrix<T>& a,
2249 const matrix<T>& b,
2250 rank_cutoff cutoff = {})
2251 {
2252 if (b.rows() != a.rows()) {
2253 throw dimension_error("lstsq: right-hand side size differs from the matrix");
2254 }
2255 detail::require_finite(a, "lstsq");
2256 buffer<double> values; // R's singular values, where they decided; unread here
2257 if (std::optional<matrix<T>> fast {detail::lstsq_by_qr(a, b, cutoff, values)}) {
2258 return *std::move(fast);
2259 }
2260 const svd_decomposition<T> s {a};
2261 return detail::lstsq_from_svd(s, detail::numerical_rank(s.singular_values(), a.rows(), a.cols(), cutoff), b);
2262 }
2263
2273 template <field T>
2275 {
2276 detail::require_finite(a, "singular values");
2277 const bool tall {a.rows() >= a.cols()};
2278 const std::size_t rows {tall ? a.rows() : a.cols()};
2279 const std::size_t cols {tall ? a.cols() : a.rows()};
2280 // Divided by the power of two of its largest magnitude, as the decomposition is: the sums of squares overflow near
2281 // 1e155. The largest found by bands of rows on the threads (a maximum, whatever the order); each entry divided
2282 // once, copied by bands of rows, or by blocks where the matrix is read transposed.
2283 const double scale {detail::largest_magnitude(a.rows(), a.cols(), [&a](std::size_t i, std::size_t j) { return a(i, j); })};
2284 const T divisor {detail::from_carried<T>(scale)};
2285 buffer<T> entries(rows * cols);
2286 if (tall) {
2287 detail::parallel_for((rows + detail::svd_band - 1) / detail::svd_band, detail::memory_element_weight * detail::svd_band * cols, [&](std::size_t band) {
2288 for (std::size_t i {band * detail::svd_band}; i < std::min(rows, (band + 1) * detail::svd_band); ++i) {
2289 for (std::size_t j {0}; j < cols; ++j) {
2290 entries[(i * cols) + j] = a(i, j) / divisor;
2291 }
2292 }
2293 });
2294 }
2295 else {
2296 const std::size_t piece {detail::transpose_piece(rows * sizeof(T), cols * sizeof(T))};
2297 detail::parallel_for((rows + transpose_tile - 1) / transpose_tile, transpose_tile * cols, [&](std::size_t block) {
2298 const std::size_t i0 {block * transpose_tile};
2299 const std::size_t i1 {std::min(i0 + transpose_tile, rows)};
2300 for (std::size_t j0 {0}; j0 < cols; j0 += transpose_tile) {
2301 detail::transpose_walk(i0, i1, j0, std::min(j0 + transpose_tile, cols), piece,
2302 [&](std::size_t i, std::size_t j) { entries[(i * cols) + j] = detail::conj_of(a(j, i)) / divisor; });
2303 }
2304 });
2305 }
2306 const bool direct {rows != cols && cols < detail::bidiagonal_crossover && rows * 4 < cols * 5}; // under 1.25 times
2307 buffer<double> d {direct ? detail::tall_singular_values(std::move(entries), rows, cols)
2308 : detail::square_singular_values(rows == cols ? std::move(entries)
2309 : detail::householder_reflect(std::move(entries), rows, cols, false).r,
2310 cols)};
2311 for (double& value : d) {
2312 value *= scale;
2313 }
2314 return vector<double> {std::move(d)};
2315 }
2316
2327 template <field T>
2329 {
2330 const std::size_t n {a.rows()};
2331 if (a.cols() != n) {
2332 throw dimension_error("symmetric eigenvalues require a square matrix");
2333 }
2334 detail::require_finite_lower(a, "symmetric eigenvalues");
2335 // Divided by the power of two of its largest magnitude read, as the decompositions are: a sum of squares overflows
2336 // near 1e155. Found and divided by bands of rows on the threads, each row written whole (its upper part zero).
2337 const double scale {detail::largest_magnitude(n, n, [&a](std::size_t i, std::size_t j) {
2338 return j < i ? a(i, j) : j == i ? detail::from_carried<T>(detail::real_part(a(i, i))) : T {};
2339 })};
2340 buffer<T> entries(n * n);
2341 detail::parallel_for((n + detail::svd_band - 1) / detail::svd_band, detail::memory_element_weight * detail::svd_band * n, [&](std::size_t band) {
2342 for (std::size_t i {band * detail::svd_band}; i < std::min(n, (band + 1) * detail::svd_band); ++i) {
2343 for (std::size_t j {0}; j < i; ++j) {
2344 entries[(i * n) + j] = a(i, j) / detail::from_carried<T>(scale);
2345 }
2346 entries[(i * n) + i] = detail::from_carried<T>(detail::real_part(a(i, i)) / scale);
2347 std::fill(entries.begin() + static_cast<std::ptrdiff_t>((i * n) + i + 1), entries.begin() + static_cast<std::ptrdiff_t>((i + 1) * n), T {});
2348 }
2349 });
2350 buffer<double> d(n, double {});
2351 if (n > 0) {
2352 buffer<double> off(n, double {});
2354 static_cast<void>(detail::tridiagonalize(entries, n, d, off));
2355 detail::tridiagonal_ql(d, off, none, n, detail::ql_steps_per_value * n);
2356 }
2357 std::sort(d.begin(), d.end());
2358 for (double& value : d) {
2359 value *= scale;
2360 }
2361 return vector<double> {std::move(d)};
2362 }
2363
2364 namespace detail {
2369 [[nodiscard]] inline double scaled_tridiagonal(const vector<double>& d,
2370 const vector<double>& e,
2371 buffer<double>& diagonal,
2372 buffer<double>& off)
2373 {
2374 const std::size_t n {d.size()};
2375 if (e.size() + 1 != std::max<std::size_t>(n, 1)) {
2376 throw dimension_error("tridiagonal eigenvalues: the off-diagonal has one entry fewer than the diagonal");
2377 }
2378 double largest {0.0};
2379 for (std::size_t i {0}; i < n; ++i) {
2380 const double off_entry {i + 1 < n ? e[i] : 0.0};
2381 if (!std::isfinite(d[i]) || !std::isfinite(off_entry)) {
2382 throw non_finite_error("tridiagonal eigenvalues: an entry is infinite or NaN");
2383 }
2384 largest = std::max({largest, std::abs(d[i]), std::abs(off_entry)});
2385 }
2386 const double scale {power_of_two_scale(largest)};
2387 diagonal.assign(n, 0.0);
2388 off.assign(n, 0.0);
2389 for (std::size_t i {0}; i < n; ++i) {
2390 diagonal[i] = d[i] / scale;
2391 off[i] = i + 1 < n ? e[i] / scale : 0.0;
2392 }
2393 return scale;
2394 }
2395 } // namespace detail
2396
2406 const vector<double>& e)
2407 {
2409 buffer<double> off;
2410 const double scale {detail::scaled_tridiagonal(d, e, diagonal, off)};
2412 detail::tridiagonal_ql(diagonal, off, none, d.size(), detail::ql_steps_per_value * d.size());
2413 std::sort(diagonal.begin(), diagonal.end());
2414 for (double& value : diagonal) {
2415 value *= scale;
2416 }
2417 return vector<double> {std::move(diagonal)};
2418 }
2419
2420 namespace detail {
2421
2424 inline constexpr std::size_t sturm_bisection_work {256};
2425
2429 [[nodiscard]] inline std::size_t sturm_count(const double* d,
2430 const double* e2,
2431 std::size_t n,
2432 double x,
2433 double pivmin)
2434 {
2435 std::size_t count {0};
2436 double q {d[0] - x};
2437 for (std::size_t i {0};; ++i) {
2438 if (std::abs(q) < pivmin) {
2439 q = -pivmin;
2440 }
2441 count += q < 0.0 ? 1 : 0;
2442 if (i + 1 == n) {
2443 return count;
2444 }
2445 q = (d[i + 1] - x) - (e2[i] / q);
2446 }
2447 }
2448 } // namespace detail
2449
2460 const vector<double>& e,
2461 std::size_t first,
2462 std::size_t last)
2463 {
2465 buffer<double> off;
2466 const double scale {detail::scaled_tridiagonal(d, e, diagonal, off)};
2467 const std::size_t n {d.size()};
2468 if (first > last || last >= n) {
2469 throw dimension_error("tridiagonal_eigenvalues: the indices must satisfy first ≤ last < n");
2470 }
2471 constexpr double ulp {std::numeric_limits<double>::epsilon()};
2472 constexpr double safmin {std::numeric_limits<double>::min()};
2473 buffer<double> e2(n, 0.0);
2474 double largest {0.0};
2475 for (std::size_t i {0}; i + 1 < n; ++i) {
2476 e2[i] = off[i] * off[i];
2477 largest = std::max(largest, e2[i]);
2478 }
2479 const double pivmin {safmin * std::max(1.0, largest)};
2480 double low {diagonal[0]};
2481 double high {diagonal[0]};
2482 for (std::size_t i {0}; i < n; ++i) { // Gershgorin's discs
2483 const double radius {(i > 0 ? std::abs(off[i - 1]) : 0.0) + (i + 1 < n ? std::abs(off[i]) : 0.0)};
2484 low = std::min(low, diagonal[i] - radius);
2485 high = std::max(high, diagonal[i] + radius);
2486 }
2487 const double norm {std::max(std::abs(low), std::abs(high))};
2488 const double slack {(2.1 * ulp * norm * static_cast<double>(n)) + (2.0 * pivmin)};
2489 low -= slack;
2490 high += slack;
2491 const double tolerance {ulp * norm};
2492 buffer<double> out(last - first + 1);
2493 // Each eigenvalue's bisection from the same interval, on its own: the same bits on any number of threads.
2494 detail::parallel_for(last - first + 1, detail::sturm_bisection_work * n, [&](std::size_t index) {
2495 const std::size_t j {first + index};
2496 double lo {low};
2497 double hi {high};
2498 // past two spacings of the doubles there (at most ε |x| for a normal x, the least subnormal below), so that the
2499 // middle always lies strictly inside
2500 while (hi - lo > std::max({tolerance, 2.0 * ulp * std::max(std::abs(lo), std::abs(hi)), 2.0 * std::numeric_limits<double>::denorm_min()})) {
2501 const double middle {0.5 * (lo + hi)};
2502 (detail::sturm_count(diagonal.data(), e2.data(), n, middle, pivmin) > j ? hi : lo) = middle;
2503 }
2504 out[index] = 0.5 * (lo + hi) * scale;
2505 });
2506 return vector<double> {std::move(out)};
2507 }
2508
2516 [[nodiscard]] inline std::pair<std::ptrdiff_t, std::ptrdiff_t> tridiagonal_eigenvalue_range(const vector<double>& d,
2517 const vector<double>& e,
2518 double low,
2519 double high)
2520 {
2522 buffer<double> off;
2523 const double scale {detail::scaled_tridiagonal(d, e, diagonal, off)};
2524 const std::size_t n {d.size()};
2525 if (n == 0) {
2526 return {0, -1};
2527 }
2528 buffer<double> e2(n, 0.0);
2529 double largest {0.0};
2530 for (std::size_t i {0}; i + 1 < n; ++i) {
2531 e2[i] = off[i] * off[i];
2532 largest = std::max(largest, e2[i]);
2533 }
2534 const double pivmin {std::numeric_limits<double>::min() * std::max(1.0, largest)};
2535 const auto at_most = [&](double x) { // the eigenvalues ≤ x: those below the next double
2536 return detail::sturm_count(diagonal.data(), e2.data(), n, std::nextafter(x / scale, std::numeric_limits<double>::infinity()), pivmin);
2537 };
2538 return {static_cast<std::ptrdiff_t>(at_most(low)), static_cast<std::ptrdiff_t>(at_most(high)) - 1};
2539 }
2540
2541 namespace detail {
2542
2554
2560 inline void factor_shifted_tridiagonal(const double* diagonal,
2561 const double* off,
2562 std::size_t n,
2563 double lambda,
2565 {
2566 f.a.assign(diagonal, diagonal + n);
2567 f.b.assign(off, off + n - 1);
2568 f.c.assign(off, off + n - 1);
2569 f.d.assign(n, 0.0);
2570 f.swapped.assign(n, false);
2571 f.a[0] -= lambda;
2572 double scale1 {std::abs(f.a[0]) + std::abs(f.b[0])};
2573 for (std::size_t k {0}; k + 1 < n; ++k) {
2574 f.a[k + 1] -= lambda;
2575 double scale2 {std::abs(f.c[k]) + std::abs(f.a[k + 1])};
2576 if (k + 2 < n) {
2577 scale2 += std::abs(f.b[k + 1]);
2578 }
2579 const double piv1 {f.a[k] == 0.0 ? 0.0 : std::abs(f.a[k]) / scale1};
2580 if (f.c[k] == 0.0 || std::abs(f.c[k]) / scale2 <= piv1) { // no interchange
2581 scale1 = scale2;
2582 if (f.c[k] != 0.0) {
2583 f.c[k] /= f.a[k];
2584 f.a[k + 1] -= f.c[k] * f.b[k];
2585 }
2586 continue;
2587 }
2588 f.swapped[k] = true; // row k + 1 above row k
2589 const double multiplier {f.a[k] / f.c[k]};
2590 f.a[k] = f.c[k];
2591 const double below {f.a[k + 1]};
2592 f.a[k + 1] = f.b[k] - (multiplier * below);
2593 if (k + 2 < n) {
2594 f.d[k] = f.b[k + 1];
2595 f.b[k + 1] = -multiplier * f.d[k];
2596 }
2597 f.b[k] = below;
2598 f.c[k] = multiplier;
2599 }
2600 }
2601
2609 std::size_t n,
2610 double* y,
2611 double& tol)
2612 {
2613 constexpr double eps {std::numeric_limits<double>::epsilon()};
2614 constexpr double least {std::numeric_limits<double>::min()};
2615 constexpr double bignum {1.0 / least};
2616 if (tol <= 0.0) {
2617 tol = std::abs(f.a[0]);
2618 for (std::size_t k {1}; k < n; ++k) {
2619 tol = std::max({tol, std::abs(f.a[k]), std::abs(f.b[k - 1]), k >= 2 ? std::abs(f.d[k - 2]) : 0.0});
2620 }
2621 tol = tol == 0.0 ? eps : tol * eps;
2622 }
2623 for (std::size_t k {1}; k < n; ++k) { // P and L
2624 if (f.swapped[k - 1]) {
2625 const double above {y[k - 1]};
2626 y[k - 1] = y[k];
2627 y[k] = above - (f.c[k - 1] * y[k]);
2628 }
2629 else {
2630 y[k] -= f.c[k - 1] * y[k - 1];
2631 }
2632 }
2633 for (std::size_t k {n}; k-- > 0;) { // U, a pivot too small for the quotient moved away from zero
2634 double temp {y[k]};
2635 if (k + 1 < n) {
2636 temp -= f.b[k] * y[k + 1];
2637 }
2638 if (k + 2 < n) {
2639 temp -= f.d[k] * y[k + 2];
2640 }
2641 double ak {f.a[k]};
2642 double pert {std::copysign(tol, ak)};
2643 for (;;) {
2644 const double absak {std::abs(ak)};
2645 if (absak >= 1.0 || (absak >= least && std::abs(temp) <= absak * bignum)) {
2646 break;
2647 }
2648 if (absak >= least || absak == 0.0 || std::abs(temp) * least > absak) {
2649 ak += pert;
2650 pert *= 2.0;
2651 continue;
2652 }
2653 temp *= bignum; // a subnormal pivot the quotient survives: both scaled up
2654 ak *= bignum;
2655 break;
2656 }
2657 y[k] = temp / ak;
2658 }
2659 }
2660
2663 inline void start_vector(std::size_t index,
2664 double* x,
2665 std::size_t n) noexcept
2666 {
2667 std::uint64_t state {0x9e3779b97f4a7c15ULL * (static_cast<std::uint64_t>(index) + 1)};
2668 for (std::size_t i {0}; i < n; ++i) {
2669 state += 0x9e3779b97f4a7c15ULL;
2670 std::uint64_t z {state};
2671 z = (z ^ (z >> 30U)) * 0xbf58476d1ce4e5b9ULL;
2672 z = (z ^ (z >> 27U)) * 0x94d049bb133111ebULL;
2673 z ^= z >> 31U;
2674 x[i] = (static_cast<double>(z >> 11U) * 0x1.0p-52) - 1.0;
2675 }
2676 }
2677
2680 inline constexpr std::size_t inverse_iteration_cluster_most {64};
2681
2698 inline bool inverse_iteration(const buffer<double>& diagonal,
2699 const buffer<double>& off,
2700 std::size_t n,
2701 const buffer<double>& values,
2702 buffer<double>& z,
2703 std::size_t most_solves = 5)
2704 {
2705 constexpr std::size_t extra {2};
2706 constexpr double eps {std::numeric_limits<double>::epsilon()};
2707 const std::size_t k {values.size()};
2708 double one_norm {0.0};
2709 for (std::size_t i {0}; i < n; ++i) {
2710 one_norm = std::max(one_norm, std::abs(diagonal[i]) + (i > 0 ? std::abs(off[i - 1]) : 0.0) + (i + 1 < n ? std::abs(off[i]) : 0.0));
2711 }
2712 const double cluster_gap {1e-3 * one_norm};
2713 const double growth {std::sqrt(0.1 / static_cast<double>(n))};
2714 buffer<double> shifts(k);
2715 std::vector<std::size_t> starts; // each cluster's first eigenvalue, then k
2716 for (std::size_t j {0}; j < k; ++j) {
2717 shifts[j] = values[j];
2718 if (j > 0 && shifts[j] - shifts[j - 1] < 10.0 * std::abs(eps * shifts[j])) {
2719 shifts[j] = shifts[j - 1] + (10.0 * std::abs(eps * shifts[j]));
2720 }
2721 if (j == 0 || std::abs(shifts[j] - shifts[j - 1]) > cluster_gap) {
2722 starts.push_back(j);
2723 }
2724 }
2725 starts.push_back(k);
2726 for (std::size_t c {0}; c + 1 < starts.size(); ++c) {
2727 if (starts[c + 1] - starts[c] > inverse_iteration_cluster_most) {
2728 return false;
2729 }
2730 }
2731 z.resize(k * n);
2732 std::atomic<bool> converged {true};
2733 const std::size_t clusters {starts.size() - 1};
2734 parallel_for(clusters, (k / clusters) * n * 64, [&](std::size_t c) { // some ten operations an entry a solve
2736 for (std::size_t j {starts[c]}; j < starts[c + 1]; ++j) {
2737 double* const x {z.data() + (j * n)};
2738 start_vector(j, x, n);
2739 factor_shifted_tridiagonal(diagonal.data(), off.data(), n, shifts[j], f);
2740 double tol {0.0};
2741 std::size_t checks {0};
2742 bool done {false};
2743 for (std::size_t solve {0}; solve < most_solves && !done; ++solve) {
2744 double sum {0.0};
2745 for (std::size_t i {0}; i < n; ++i) {
2746 sum += std::abs(x[i]);
2747 }
2748 const double scale {static_cast<double>(n) * one_norm * std::max(eps, std::abs(f.a[n - 1])) / sum};
2749 for (std::size_t i {0}; i < n; ++i) {
2750 x[i] *= scale;
2751 }
2752 solve_shifted_tridiagonal(f, n, x, tol);
2753 for (std::size_t p {starts[c]}; p < j; ++p) { // against the cluster's vectors so far
2754 const double* const v {z.data() + (p * n)};
2755 double dot {0.0};
2756 for (std::size_t i {0}; i < n; ++i) {
2757 dot += x[i] * v[i];
2758 }
2759 for (std::size_t i {0}; i < n; ++i) {
2760 x[i] -= dot * v[i];
2761 }
2762 }
2763 double largest {0.0};
2764 for (std::size_t i {0}; i < n; ++i) {
2765 largest = std::max(largest, std::abs(x[i]));
2766 }
2767 checks += largest >= growth ? 1 : 0;
2768 done = checks > extra;
2769 }
2770 if (!done) {
2771 converged.store(false, std::memory_order_relaxed);
2772 }
2773 double squares {0.0};
2774 std::size_t at {0};
2775 for (std::size_t i {0}; i < n; ++i) {
2776 squares += x[i] * x[i];
2777 at = std::abs(x[i]) > std::abs(x[at]) ? i : at;
2778 }
2779 const double unit {(x[at] < 0.0 ? -1.0 : 1.0) / std::sqrt(squares)}; // its largest entry positive, as dstein
2780 for (std::size_t i {0}; i < n; ++i) {
2781 x[i] *= unit;
2782 }
2783 }
2784 });
2785 return converged.load();
2786 }
2787 } // namespace detail
2788
2801 const vector<double>& e,
2802 const vector<double>& values)
2803 {
2805 buffer<double> off;
2806 const double scale {detail::scaled_tridiagonal(d, e, diagonal, off)};
2807 const std::size_t n {d.size()};
2808 const std::size_t k {values.size()};
2809 if (k > n) {
2810 throw dimension_error("tridiagonal_eigenvectors: at most n eigenvalues");
2811 }
2812 buffer<double> shifted(k);
2813 for (std::size_t j {0}; j < k; ++j) {
2814 if (!std::isfinite(values[j])) {
2815 throw non_finite_error("tridiagonal_eigenvectors: an eigenvalue is infinite or NaN");
2816 }
2817 if (j > 0 && values[j] < values[j - 1]) {
2818 throw dimension_error("tridiagonal_eigenvectors: the eigenvalues must be ascending");
2819 }
2820 shifted[j] = values[j] / scale;
2821 }
2823 if (n == 1) {
2824 z.assign(k, 1.0);
2825 }
2826 else if (n > 1 && !detail::inverse_iteration(diagonal, off, n, shifted, z)) { // the whole spectrum's nearest
2829 detail::divide_and_conquer(all.data(), off.data(), n, q);
2830 z.resize(k * n);
2831 std::size_t next {0}; // the first column not taken: each eigenvalue its own, ascending, as near as leaves room
2832 for (std::size_t j {0}; j < k; ++j) {
2833 auto column {static_cast<std::size_t>(std::lower_bound(all.begin() + static_cast<std::ptrdiff_t>(next), all.end(), shifted[j]) - all.begin())};
2834 if (column > next && (column == n || shifted[j] - all[column - 1] <= all[column] - shifted[j])) {
2835 --column;
2836 }
2837 column = std::min(column, n - (k - j));
2838 next = column + 1;
2839 for (std::size_t i {0}; i < n; ++i) {
2840 z[(j * n) + i] = q[(i * n) + column];
2841 }
2842 }
2843 }
2844 buffer<double> columns(n * k);
2845 for (std::size_t j {0}; j < k; ++j) {
2846 for (std::size_t i {0}; i < n; ++i) {
2847 columns[(i * k) + j] = z[(j * n) + i];
2848 }
2849 }
2850 return matrix<double> {n, k, std::move(columns)};
2851 }
2852
2862 [[nodiscard]] inline std::pair<vector<double>, matrix<double>> tridiagonal_eigen(const vector<double>& d,
2863 const vector<double>& e)
2864 {
2865 const std::size_t n {d.size()};
2867 buffer<double> off;
2868 const double scale {detail::scaled_tridiagonal(d, e, diagonal, off)};
2870 if (n > 0) {
2871 detail::divide_and_conquer(diagonal.data(), off.data(), n, q);
2872 }
2873 for (double& value : diagonal) {
2874 value *= scale;
2875 }
2876 return {vector<double> {std::move(diagonal)}, matrix<double> {n, n, std::move(q)}};
2877 }
2878
2880 template <typename T>
2886
2887 namespace detail {
2888
2894 template <typename T>
2896 const matrix<T>& a,
2897 const std::function<std::pair<std::ptrdiff_t, std::ptrdiff_t>(const vector<double>&, const vector<double>&, double)>& select,
2898 bool vectors,
2899 const std::string& name)
2900 {
2901 const std::size_t n {a.rows()};
2902 if (a.cols() != n) {
2903 throw dimension_error(name + ": expected a square matrix");
2904 }
2905 require_finite_lower(a, name.c_str());
2906 double largest {0.0};
2907 for (std::size_t i {0}; i < n; ++i) {
2908 for (std::size_t j {0}; j <= i; ++j) {
2909 largest = std::max(largest, static_cast<double>(std::abs(a(i, j))));
2910 }
2911 }
2912 const double scale {power_of_two_scale(largest)};
2913 buffer<T> work(n * n, T {});
2914 for (std::size_t i {0}; i < n; ++i) { // the lower triangle divided, nothing above it
2915 for (std::size_t j {0}; j <= i; ++j) {
2916 work[(i * n) + j] = a(i, j) / T {scale};
2917 }
2918 }
2919 buffer<double> diagonal(n, 0.0);
2920 buffer<double> off(n, 0.0);
2921 const tridiagonal_reduction<T> reduction {n > 0 ? tridiagonalize(work, n, diagonal, off) : tridiagonal_reduction<T> {}};
2922 work = buffer<T> {};
2924 const vector<double> e {buffer<double>(off.begin(), off.begin() + static_cast<std::ptrdiff_t>(n > 0 ? n - 1 : 0))};
2925 const auto [first, last] {select(d, e, scale)};
2926 if (last < first) {
2927 return {vector<double> {buffer<double> {}}, matrix<T> {n, 0, buffer<T> {}}};
2928 }
2929 const auto from {static_cast<std::size_t>(first)};
2930 const auto k {static_cast<std::size_t>(last - first + 1)};
2931 const vector<double> found {tridiagonal_eigenvalues(d, e, from, static_cast<std::size_t>(last))};
2932 buffer<double> values(found.begin(), found.end());
2934 std::transform(values.begin(), values.end(), scaled.begin(), [scale](double value) { return value * scale; });
2935 if (!vectors) {
2936 return {vector<double> {std::move(scaled)}, matrix<T> {n, 0, buffer<T> {}}};
2937 }
2939 if (n == 1) {
2940 z.assign(1, 1.0);
2941 }
2942 else if (!inverse_iteration(diagonal, off, n, values, z)) { // the whole spectrum's
2944 divide_and_conquer(diagonal.data(), off.data(), n, q);
2945 z.resize(k * n);
2946 for (std::size_t j {0}; j < k; ++j) {
2947 for (std::size_t i {0}; i < n; ++i) {
2948 z[(j * n) + i] = q[(i * n) + from + j];
2949 }
2950 }
2951 }
2952 buffer<T> rows(z.begin(), z.end()); // the vectors as rows, k × n, in T's basis, then the matrix's
2953 to_matrix_basis(reduction, rows, n, k);
2954 buffer<T> columns(n * k);
2955 for (std::size_t j {0}; j < k; ++j) {
2956 for (std::size_t i {0}; i < n; ++i) {
2957 columns[(i * k) + j] = rows[(j * n) + i];
2958 }
2959 }
2960 return {vector<double> {std::move(scaled)}, matrix<T> {n, k, std::move(columns)}};
2961 }
2962 } // namespace detail
2963
2976 template <typename T>
2977 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2979 std::size_t first,
2980 std::size_t last,
2981 bool vectors = true)
2982 {
2983 if (first > last || last >= a.rows()) {
2984 throw dimension_error("hermitian_eigen_subset: the indices must satisfy first ≤ last < n");
2985 }
2986 return detail::hermitian_subset<T>(a, [first, last](const vector<double>&, const vector<double>&, double) {
2987 return std::pair {static_cast<std::ptrdiff_t>(first), static_cast<std::ptrdiff_t>(last)};
2988 }, vectors, "hermitian_eigen_subset");
2989 }
2990
2998 template <typename T>
2999 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3001 double low,
3002 double high,
3003 bool vectors = true)
3004 {
3005 return detail::hermitian_subset<T>(a, [low, high](const vector<double>& d, const vector<double>& e, double scale) {
3006 return tridiagonal_eigenvalue_range(d, e, low / scale, high / scale);
3007 }, vectors, "hermitian_eigen_subset_by_value");
3008 }
3009
3011 template <typename T>
3019
3030 template <typename T>
3032 const matrix<T>& b,
3033 rank_cutoff cutoff = {})
3034 {
3035 if (b.rows() != a.rows()) {
3036 throw dimension_error("lstsq: right-hand side size differs from the matrix");
3037 }
3038 detail::require_finite(a, "lstsq");
3039 // The singular values from what the solution took: the QR's R (A's over a power of two), else the decomposition.
3040 std::pair<buffer<T>, int> r;
3041 buffer<double> decided; // R's singular values, where they decided the rank
3042 std::optional<matrix<T>> fast {detail::lstsq_by_qr(a, b, cutoff, decided, &r)};
3043 std::optional<svd_decomposition<T>> s;
3044 if (!fast) {
3045 s.emplace(a);
3046 }
3047 buffer<double> values {!fast ? buffer<double>(s->singular_values().begin(), s->singular_values().end())
3048 : decided.empty() ? detail::square_singular_values(std::move(r.first), std::min(a.rows(), a.cols()))
3049 : std::move(decided)};
3050 if (fast) {
3051 for (double& value : values) {
3052 value = std::ldexp(value, r.second);
3053 }
3054 }
3055 const vector<double> sigma {std::move(values)};
3056 const std::size_t rank {detail::numerical_rank(sigma, a.rows(), a.cols(), cutoff)};
3057 matrix<T> x {fast ? *std::move(fast) : detail::lstsq_from_svd(*s, rank, b)};
3058 buffer<double> residuals;
3059 if (rank == a.cols() && a.rows() > a.cols()) {
3060 const matrix<T> fitted {a * x};
3061 residuals.assign(b.cols(), 0.0);
3062 for (std::size_t i {0}; i < b.rows(); ++i) {
3063 for (std::size_t c {0}; c < b.cols(); ++c) {
3064 residuals[c] += std::norm(b(i, c) - fitted(i, c)); // |·|², real or complex
3065 }
3066 }
3067 }
3068 return least_squares_solution<T> {.solution = std::move(x),
3069 .residuals = vector<double> {std::move(residuals)},
3070 .rank = rank,
3071 .singular_values = sigma};
3072 }
3073
3074 namespace detail {
3075
3078 template <typename T>
3080 {
3081 const std::size_t n {a.rows()};
3082 buffer<T> entries(n * n, T {});
3083 for (std::size_t i {0}; i < n; ++i) {
3084 for (std::size_t j {0}; j < i; ++j) {
3085 entries[(i * n) + j] = a(i, j);
3086 entries[(j * n) + i] = conj_of(a(i, j));
3087 }
3088 entries[(i * n) + i] = from_carried<T>(real_part(a(i, i)));
3089 }
3090 return matrix<T> {n, n, std::move(entries)};
3091 }
3092
3100 template <typename T>
3101 [[nodiscard]] matrix<T> inverse_on_kept(const vector<double>& sigma,
3102 const matrix<T>& right,
3103 const matrix<T>& left,
3104 rank_cutoff cutoff)
3105 {
3106 const std::size_t rows {left.rows()};
3107 const std::size_t cols {right.rows()};
3108 double largest {0.0};
3109 for (std::size_t d {0}; d < sigma.size(); ++d) {
3110 largest = std::max(largest, std::abs(sigma[d]));
3111 }
3112 const double tolerance {cutoff.magnitude(largest, rows, cols)};
3113 std::vector<std::size_t> kept;
3114 for (std::size_t d {0}; d < sigma.size(); ++d) {
3115 if (std::abs(sigma[d]) > tolerance) {
3116 kept.push_back(d);
3117 }
3118 }
3119 const std::size_t rank {kept.size()};
3120 buffer<T> scaled(cols * rank, T {});
3121 buffer<T> left_adjoint(rank * rows, T {});
3122 for (std::size_t e {0}; e < rank; ++e) {
3123 const std::size_t d {kept[e]};
3124 const auto inverse {from_carried<T>(1.0 / sigma[d])};
3125 for (std::size_t i {0}; i < cols; ++i) {
3126 scaled[(i * rank) + e] = right(i, d) * inverse;
3127 }
3128 for (std::size_t j {0}; j < rows; ++j) {
3129 left_adjoint[(e * rows) + j] = conj_of(left(j, d));
3130 }
3131 }
3132 buffer<T> out(cols * rows, T {});
3133 gemm(cols, rows, rank, scaled.data(), rank, left_adjoint.data(), rows, out.data(), rows);
3134 return matrix<T> {cols, rows, std::move(out)};
3135 }
3136
3141 template <typename T>
3143 {
3145 }
3146
3149 template <typename T>
3151 {
3152 const vector<double> signed_values {symmetric_eigenvalues(a)};
3153 buffer<double> values(signed_values.begin(), signed_values.end());
3154 for (double& value : values) {
3155 value = std::abs(value);
3156 }
3157 return vector<double> {std::move(values)};
3158 }
3159
3162 {
3163 return eigenvalue_magnitudes(a);
3164 }
3165
3167 [[nodiscard]] inline vector<double> hermitian_singular_values(const matrix<std::complex<double>>& a)
3168 {
3169 return eigenvalue_magnitudes(a);
3170 }
3171
3176 template <typename T>
3178 rank_cutoff cutoff)
3179 {
3181 return inverse_on_kept(s.singular_values(), s.v(), s.u(), cutoff);
3182 }
3183
3186 rank_cutoff cutoff)
3187 {
3188 const symmetric_eigen decomposition {a};
3189 const matrix<double>& vectors {decomposition.vectors()};
3190 return inverse_on_kept(decomposition.values(), vectors, vectors, cutoff);
3191 }
3192
3194 [[nodiscard]] inline matrix<std::complex<double>> hermitian_pseudo_inverse(const matrix<std::complex<double>>& a,
3195 rank_cutoff cutoff)
3196 {
3197 const hermitian_eigen decomposition {a};
3198 const matrix<std::complex<double>>& vectors {decomposition.vectors()};
3199 return inverse_on_kept(decomposition.values(), vectors, vectors, cutoff);
3200 }
3201 } // namespace detail
3202
3214 template <field T>
3215 [[nodiscard]] std::size_t matrix_rank(const matrix<T>& a,
3216 rank_cutoff cutoff = {},
3217 bool hermitian = false)
3218 {
3219 if (hermitian) {
3220 if (a.cols() != a.rows()) {
3221 throw dimension_error("matrix_rank: a Hermitian matrix is square");
3222 }
3223 detail::require_finite_lower(a, "matrix_rank");
3224 return detail::numerical_rank(detail::hermitian_singular_values(a), a.rows(), a.cols(), cutoff);
3225 }
3226 return detail::numerical_rank(singular_values(a), a.rows(), a.cols(), cutoff);
3227 }
3228
3240 template <field T>
3241 [[nodiscard]] matrix<T> pinv(const matrix<T>& a,
3242 rank_cutoff cutoff = {},
3243 bool hermitian = false)
3244 {
3245 if (hermitian) {
3246 if (a.cols() != a.rows()) {
3247 throw dimension_error("pinv: a Hermitian matrix is square");
3248 }
3249 detail::require_finite_lower(a, "pinv");
3250 return detail::hermitian_pseudo_inverse(a, cutoff);
3251 }
3252 detail::require_finite(a, "pinv");
3253 const svd_decomposition<T> s {a};
3254 return detail::inverse_on_kept(s.singular_values(), s.v(), s.u(), cutoff);
3255 }
3256} // namespace numerical
3257
3258#endif // NUMERICAL_SVD_HPP
#define NUMERICAL_OUT_OF_LINE
Definition buffer.hpp:30
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Definition vector.hpp:87
Thrown when an iterative algorithm has not converged within its bound of sweeps.
Thrown when an operation's operands have incompatible shapes.
Definition vector.hpp:76
The eigenvalues and eigenvectors of a complex Hermitian matrix.
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...
The magnitude at or under which a singular value counts as zero, in a rank (matrix_rank),...
rank_cutoff scaled(int exponent) const noexcept
The same cutoff for the matrix divided by 2^exponent.
double magnitude(double largest, std::size_t rows, std::size_t cols) const noexcept
The cutoff for a rows × cols matrix whose largest singular value is largest.
The singular value decomposition A = U Σ Vᴴ of an m × n matrix.
Definition svd.hpp:1601
matrix< T > u_
m×k left singular vectors.
Definition svd.hpp:1955
static void orthogonalise(buffer< T > &x, const buffer< T > &basis, std::size_t n, std::size_t count)
Removes from x its components along the first count columns of the n × n basis.
Definition svd.hpp:1938
const matrix< T > & v() const &noexcept
The right singular vectors V (columns): n × k, or n × n full.
Definition svd.hpp:1668
static matrix< T > applied_left_vectors(const buffer< T > &left, const std::vector< detail::reflector_block< T > > &blocks, const std::vector< T > &phases, std::size_t rows, std::size_t cols, std::size_t width)
U = Q [D L; 0] (rows × width): the left vectors left of R (cols × cols), each row times its diagonal'...
Definition svd.hpp:1687
matrix< T > v_
n×k right singular vectors.
Definition svd.hpp:1956
const matrix< T > & u() const &noexcept
The left singular vectors U (columns): m × k, or m × m full.
Definition svd.hpp:1656
svd_decomposition(const matrix< T > &a, svd_method method=svd_method::divide_and_conquer, bool full=false)
Decomposes a.
Definition svd.hpp:1612
void factor_scaled(const T *source, buffer< T > entries, std::size_t rows, std::size_t cols, svd_method method, bool full)
The decomposition of the rows × cols matrix at source (row-major), its scaled copy written into entri...
Definition svd.hpp:1755
void factor(matrix< T > &&a, svd_method method, bool full)
factor of an expiring matrix, its elements scaled in place.
Definition svd.hpp:1740
matrix< T > vh() const
Vᴴ (k × n, or n × n full), so that A = U Σ Vᴴ reads u() * diag(singular_values()) * vh() (full,...
Definition svd.hpp:1675
matrix< T > u() &&
U, moved out of an expiring decomposition (v and the singular values stay).
Definition svd.hpp:1662
vector< double > singular_values_
Singular values, descending.
Definition svd.hpp:1954
static matrix< T > left_vectors(buffer< T > q, buffer< T > left, std::size_t rows, std::size_t cols, std::size_t width)
U from the Householder q (rows × width) and the left vectors left of R (cols × cols): Q times them,...
Definition svd.hpp:1711
svd_decomposition(matrix< T > &&a, svd_method method=svd_method::divide_and_conquer, bool full=false)
Decomposes a in its own storage, an expiring matrix's elements taken over: its scaled copy is made in...
Definition svd.hpp:1635
void factor(const matrix< T > &a, svd_method method, bool full)
Decomposes an m × n a with m ≥ n into u_, singular_values_ and v_, U square when full.
Definition svd.hpp:1732
static double largest_cosine(const buffer< T > &x, const buffer< T > &basis, std::size_t n, std::size_t count)
The largest |⟨b, x⟩| over the first count columns b of the n × n basis.
Definition svd.hpp:1921
const vector< double > & singular_values() const noexcept
The singular values, descending.
Definition svd.hpp:1650
The eigenvalues and eigenvectors of a real symmetric matrix.
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
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
Definition simd.hpp:188
The scalar types NumericAL's factorisations and solvers take: a field of floating-point numbers,...
The singular values of a real bidiagonal by the dqds algorithm (Fernando and Parlett's differential q...
The LU, Cholesky and QR factorisations and the symmetric and Hermitian eigen-decompositions.
std::ptrdiff_t qd_index
An index into the qd array, one-based and signed as LAPACK's.
Definition dqds.hpp:23
arrow_workspace & thread_arrow_workspace()
The calling thread's arrow_workspace, kept from one decomposition to the next. A join uses it whole o...
Definition svd.hpp:947
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
Definition buffer.hpp:65
void factor_shifted_tridiagonal(const double *diagonal, const double *off, std::size_t n, double lambda, shifted_tridiagonal &f)
Factorises T − λ I, n from 2, T of diagonal diagonal and off-diagonal off, with partial pivoting as L...
Definition svd.hpp:2560
matrix< T > inverse_on_kept(const vector< double > &sigma, const matrix< T > &right, const matrix< T > &left, rank_cutoff cutoff)
Σ_d right_d (1 / σ_d) left_dᴴ over the columns d of right (cols × k) and left (rows × k) whose sigma ...
Definition svd.hpp:3101
double rotation_length(double a, double b) noexcept
√(a² + b²) for a plane rotation of the QR and QL iterations, as LAPACK's dlartg takes it: the plain s...
double scaled_tridiagonal(const vector< double > &d, const vector< double > &e, buffer< double > &diagonal, buffer< double > &off)
The diagonal d and off-diagonal e of a symmetric tridiagonal matrix divided by the power of two of th...
Definition svd.hpp:2369
void bidiagonal_qr(buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, std::size_t n, std::size_t max_steps)
The singular values of the real upper bidiagonal (d, e) by implicit-shift QR with deflation (the Golu...
Definition svd.hpp:663
vector< double > hermitian_singular_values(const matrix< T > &a)
The singular values of the real symmetric or complex Hermitian matrix whose lower triangle is a's: of...
Definition svd.hpp:3142
matrix< T > hermitian_pseudo_inverse(const matrix< T > &a, rank_cutoff cutoff)
The pseudo-inverse of the real symmetric or complex Hermitian matrix whose lower triangle is a's: fro...
Definition svd.hpp:3177
void transpose_walk(std::size_t i0, std::size_t i1, std::size_t j0, std::size_t j1, std::size_t piece, const Copy &copy)
transpose_pieces of side piece (transpose_piece's 8 or the whole tile), each side its own instance: a...
Definition simd.hpp:142
void solve_shifted_tridiagonal(const shifted_tridiagonal &f, std::size_t n, double *y, double &tol)
Solves (T − λ I) x = y in place in y from factor_shifted_tridiagonal's factors, as LAPACK's dlagts (j...
Definition svd.hpp:2608
constexpr std::size_t sturm_bisection_work
One eigenvalue's bisection in parallel_for's units per order of the matrix: some 60 halvings,...
Definition svd.hpp:2424
void start_vector(std::size_t index, double *x, std::size_t n) noexcept
A start vector of n entries in [−1, 1) for tridiagonal_eigenvectors' eigenvalue index,...
Definition svd.hpp:2663
double one_norm(const buffer< T > &a, std::size_t n)
The 1-norm of the n × n row-major a (n from 1): its largest column sum of moduli.
buffer< T > upper_inverse(const buffer< T > &r, std::size_t n)
R⁻¹, upper triangular, of the n × n upper-triangular r (row-major): back substitution against the ide...
Definition svd.hpp:2007
std::complex< R > scaled(R c, const std::complex< R > &v) noexcept
c · v of a real c and a complex v: each part's product, rounded.
Definition fft.hpp:1290
carried_t< T > real_part(const T &x)
The real part of a real (or general) scalar, in carried_t.
void solve_bidiagonal_leaf(bidiagonal_node &node)
Decomposes the leaf node by implicit-shift QR.
Definition svd.hpp:1296
void one_sided_jacobi(buffer< T > &w, buffer< T > &v, std::size_t n, std::size_t max_sweeps)
One-sided (Hestenes) Jacobi on the columns of the n × n row-major w: plane rotations,...
Definition svd.hpp:64
vector< double > eigenvalue_magnitudes(const matrix< T > &a)
The magnitudes of the eigenvalues of the real symmetric or complex Hermitian a, its lower triangle re...
Definition svd.hpp:3150
void bidiagonalize(buffer< T > &b, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form=true)
Reduces the square n × n row-major b to upper-bidiagonal form, B = U_b D V_bᴴ, by panels of bidiagona...
Definition svd.hpp:302
void subtract_products(double *y, const double *f, const double *x, std::size_t ldx, std::size_t terms, std::size_t count)
y[i] -= Σₜ f[t] · x[(t · ldx) + i] for double, the units chosen as subtract_product chooses them,...
Definition gemm.hpp:522
void join_bidiagonal_node(bidiagonal_node &node, const bidiagonal_node &one, const bidiagonal_node &two, arrow_workspace &work)
Joins the two decomposed halves of node, one and two, by merge_arrow, node started (start_bidiagonal_...
Definition svd.hpp:1350
std::size_t sturm_count(const double *d, const double *e2, std::size_t n, double x, double pivmin)
The number of eigenvalues below x of the symmetric tridiagonal of diagonal d and squared off-diagonal...
Definition svd.hpp:2429
void reflect_columns(T *panel, std::size_t height, const buffer< T > &v, std::size_t first, std::size_t from, std::size_t to, const T &s=T {2})
Applies I − s v vᴴ from the left (s 2 for a unit v) to the columns from…to-1 of the column-major pane...
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::size_t plan_bidiagonal(std::vector< bidiagonal_node > &nodes, const double *d, const double *e, std::size_t n, std::size_t extra, std::size_t depth)
Appends the block (d, e, n, extra) and everything below it to nodes, parents before children,...
Definition svd.hpp:1243
constexpr std::size_t kept_workspace
The most elements a buffer of a thread's merge_workspace keeps from one decomposition to the next: 2 ...
void release_large_arrow_workspace(arrow_workspace &work)
Releases the buffers of work longer than kept_workspace.
Definition svd.hpp:955
constexpr double qr_rank_margin
How far above the rank cutoff a bound on the smallest singular value must stay for lstsq_by_qr to ans...
Definition svd.hpp:1982
tridiagonal_reduction< T > tridiagonalize(buffer< T > &a, std::size_t n, buffer< double > &d, buffer< double > &e)
Reduces the Hermitian (real: symmetric) n × n row-major a, of which the lower triangle is read,...
@ split
arm64's real kernel's (gemm_split): Re a·Re b from zero, −Im a·Im b fused into it; Re a·Im b,...
void require_finite_lower(const matrix< T > &a, const char *what)
require_finite over what a Hermitian eigensolver reads: the lower triangle, and the diagonal's real p...
qr_reflections< T > householder_reflect(buffer< T > a, std::size_t rows, std::size_t cols, bool reflectors=true)
The reflections of householder_qr, without forming Q: A = Q R with Q the product of the blocks' refle...
constexpr std::size_t bidiagonal_block
The rows from which a step of the blocked bidiagonal reduction shares its coefficients and correction...
Definition svd.hpp:263
double largest_magnitude(std::size_t rows, std::size_t cols, const Entry &entry)
The power_of_two_scale of the largest magnitude of entry over rows rows of cols: by bands of rows on ...
Definition svd.hpp:839
constexpr std::size_t bidiagonal_crossover
The order below which a real bidiagonal reduction goes a reflection at a time, as LAPACK's dgebrd fal...
Definition svd.hpp:191
void bidiagonal_divide_and_conquer(buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, std::size_t n)
The singular values of the upper bidiagonal (d, e) into d, descending, the singular vectors accumulat...
Definition svd.hpp:1522
std::conditional_t< std::is_same_v< T, float >||std::is_same_v< T, std::complex< float > >, float, carried_t< T > > value_range_t
The real type whose range a T's values take: float for a single-precision scalar, real or complex; ca...
double * workspace_of(workspace_buffer &buffer, std::size_t size)
buffer at least size elements long, its storage kept for the next join. A larger one is mapped fresh,...
bool dqds_singular_values(buffer< double > &d, const buffer< double > &e, std::size_t n, qd_index sweeps=dqds_sweeps)
The singular values of the real upper bidiagonal (d, e) of order n by dqds (LAPACK's dlasq1),...
Definition dqds.hpp:831
reflector_block< T > gather_reflectors(const std::vector< buffer< T > > &reflectors, std::size_t k0, std::size_t k1, std::size_t rows, const std::vector< T > *taus=nullptr)
Gathers the reflectors reflectors[k0…k1-1] (each I − τ_k v vᴴ: τ_k from taus, else 2 for a unit v; an...
void apply_reflector_block(const reflector_block< T > &block, bool adjoint, buffer< T > &a, std::size_t cols, std::size_t from, std::size_t to)
Applies I − V T Vᴴ (or its adjoint I − V Tᴴ Vᴴ) from the left to the block's rows of a row-major arra...
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
double singular_value_in_double(double x) noexcept
A singular value of a decomposition carried in double: x itself.
Definition svd.hpp:1559
void merge_arrow(buffer< double > &d, buffer< double > z, double alpha, double beta, buffer< double > &u, buffer< double > &v, std::size_t n, std::size_t m, std::size_t split, arrow_workspace &work)
The singular value decomposition of the arrow M (first row z, diagonal d, d₀ = 0),...
Definition svd.hpp:989
void join_bidiagonal_halves(std::vector< bidiagonal_node > &nodes, std::size_t index, arrow_workspace &work)
Joins the halves of nodes' block index in work, then lets them go.
Definition svd.hpp:1429
matrix< T > hermitian_from_lower(const matrix< T > &a)
The real symmetric or complex Hermitian matrix whose lower triangle is the square a's,...
Definition svd.hpp:3079
void reflect_rows(buffer< T > &a, std::size_t cols, const buffer< T > &v, std::size_t first, std::size_t from, const T &s=T {2})
Applies I − s v vᴴ from the left (s 2 for a unit v) to the rows first…first+|v|-1 of a row-major arra...
constexpr double jacobi_large
The |ζ| past which one-sided Jacobi takes the rotation's tangent as 1 / (2|ζ|): ζ² stays finite under...
Definition svd.hpp:47
std::size_t numerical_rank(const vector< double > &sigma, std::size_t rows, std::size_t cols, rank_cutoff cutoff={})
How many of the singular values sigma of an rows × cols matrix exceed cutoff: its numerical rank (the...
Definition svd.hpp:1963
constexpr std::size_t inverse_iteration_cluster_most
The most eigenvalues tridiagonal_eigenvectors reorthogonalises together: a larger cluster's vectors c...
Definition svd.hpp:2680
std::size_t transpose_piece(std::size_t from_bytes, std::size_t to_bytes) noexcept
The side of the square pieces a transposing copy walks a tile by, from the bytes between rows of its ...
Definition simd.hpp:100
std::optional< matrix< T > > lstsq_by_qr(const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff, buffer< double > &values, std::pair< buffer< T >, int > *const r=nullptr)
The least-squares solution of A X ≈ B by a QR factorisation, of A, or of Aᴴ for a wide A (the minimum...
Definition svd.hpp:2052
void solve_bidiagonal_subtree(std::vector< bidiagonal_node > &nodes, std::size_t index, arrow_workspace &work)
Decomposes the block index of nodes and everything below it, each block right after its halves.
Definition svd.hpp:1441
std::pair< T, T > larfg_in_place(buffer< T > &w)
The reflector LAPACK's dlarfg (zlarfg) forms of w, in place: H = I − τ w wᴴ with w₀ = 1 and Hᴴ x = β ...
constexpr double cancelled
The fall of a column's norm, in units of √n ε, past which one_sided_jacobi takes what a rotation left...
Definition svd.hpp:51
void gemm(std::size_t m, std::size_t n, std::size_t k, const T *a, std::size_t lda, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
C += A·B, every element of C summed in ascending order of the depth.
Definition gemm.hpp:4583
void apply_row_operations(buffer< T > &m, std::size_t n, const std::vector< row_operation > &operations)
Applies the recorded operations, in order, to the row-major m (n per row). Each column takes them ind...
void form_bidiagonal_bases(const std::vector< buffer< T > > &left, std::vector< buffer< T > > right, const std::vector< T > &left_tau, const std::vector< T > &right_tau, const buffer< T > &left_phase, const buffer< T > &right_phase, std::size_t n, buffer< T > &ut, buffer< T > &vt)
The bases of a bidiagonal reduction from its reflectors: U_b = (H₀ H₁ …) diag(conj left phases) and V...
Definition svd.hpp:213
constexpr std::size_t qr_block
The reflectors of one panel of the blocked QR.
double dot_product(const double *x, const double *y, std::size_t count)
Σ x[i] · y[i] for double, as subtract_product chooses its units (in another order of summation there,...
Definition gemm.hpp:715
void apply_transposed_reflector_block(const reflector_block< T > &block, buffer< T > &at, std::size_t cols, std::size_t from, std::size_t to, bool adjoint=false)
apply_reflector_block to A held transposed: at is Aᵀ (row-major, cols columns), and A ← (I − V T Vᴴ) ...
void rotate_columns(buffer< double > &m, std::size_t cols, std::size_t a, std::size_t b, double c, double s)
Columns a and b of the row-major m (cols per row) rotated: a ← c a + s b, b ← c b − s a.
Definition svd.hpp:912
void bidiagonal_divide(const double *d, const double *e, std::size_t n, std::size_t extra, buffer< double > &sigma, buffer< double > &u, buffer< double > &v)
The singular value decomposition of the upper bidiagonal n × (n + extra) (extra 0 or 1) with diagonal...
Definition svd.hpp:1474
T phase_of(const T &x)
The unit-modulus factor of x: x / |x| (its sign, for a real scalar), and 1 at 0. A subnormal x is sca...
void divide_and_conquer(double *d, const double *e, std::size_t n, buffer< double > &q)
The eigenvalues, ascending, of the symmetric tridiagonal with diagonal d[0…n-1] and subdiagonal e[0…n...
constexpr std::size_t lowner_block
The poles a task of merge_rank_one's Löwner products takes, and the side of its tiles of u.
constexpr std::size_t secular_iterations
The iterations one root of the secular equation may take: it converges in a few; the bound turns a no...
T scaled_by_two(const T &x, int exponent)
x times two to the exponent, exactly where the result is a normal number (no power of two is formed,...
Definition svd.hpp:1987
bool inverse_iteration(const buffer< double > &diagonal, const buffer< double > &off, std::size_t n, const buffer< double > &values, buffer< double > &z, std::size_t most_solves=5)
The eigenvectors (rows of z, k × n) of the symmetric tridiagonal of diagonal diagonal and off-diagona...
Definition svd.hpp:2698
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
@ zero
C = A·B: C's elements before the product are not read.
matrix< T > lstsq_from_svd(const svd_decomposition< T > &s, std::size_t rank, const matrix< T > &b)
The minimum-norm least-squares solution of A X ≈ B from the singular value decomposition s of A (m × ...
Definition svd.hpp:2178
constexpr std::size_t bidiagonal_leaf
The order up to which bidiagonal_divide decomposes by implicit-shift QR.
Definition svd.hpp:1213
constexpr std::size_t svd_band
The rows of an SVD's input one thread scales and copies at a time.
double singular_secular_root(const buffer< double > &d, const buffer< double > &z, std::size_t i, std::size_t max_iterations, double *below, double *above)
Singular value i of the arrow M whose first row is z and whose diagonal is d (d₀ = 0,...
Definition svd.hpp:891
matrix< T > adjoint(const matrix< T > &a)
The conjugate transpose of a, as numerical::transpose copies (by blocks, on the threads).
Definition svd.hpp:860
carried_t< T > scaled_norm(const T *x, std::size_t count)
The Euclidean norm of the count elements at x, by norm_at_scale for this type.
constexpr std::size_t bidiagonal_product_weight
The weight of a multiply-add of the bidiagonal reduction's matrix-vector products,...
Definition svd.hpp:271
double power_of_two_scale(double largest) noexcept
The power of two a decomposition divides a matrix by whose largest magnitude is largest: its leading ...
secular_solution solve_secular(const buffer< double > &z, double rho, std::size_t i, std::size_t max_iterations, double *delta, const Offset &offset)
Root i of 1/ρ + Σⱼ zⱼ²/(Pⱼ − x) = 0, poles P strictly ascending, no zⱼ zero, ρ > 0,...
eigen_subset< T > hermitian_subset(const matrix< T > &a, const std::function< std::pair< std::ptrdiff_t, std::ptrdiff_t >(const vector< double > &, const vector< double > &, double)> &select, bool vectors, const std::string &name)
hermitian_eigen_subset of the indices select gives from the tridiagonal form's diagonal and off-diago...
Definition svd.hpp:2895
constexpr std::size_t svd_qr_steps_per_value
The QR steps the bidiagonal singular value iteration may take per value: it converges in two or three...
Definition svd.hpp:186
void unscale_bidiagonal_node(bidiagonal_node &node)
The singular values of a solved node scaled back.
Definition svd.hpp:1419
std::conditional_t< std::is_same_v< magnitude_t< T >, long double >, long double, double > carried_t
The real type a T's norms, reflector lengths and pivot magnitudes are carried in: long double for a l...
constexpr std::size_t bidiagonal_basis_crossover
The order below which the bases of a bidiagonal reduction are formed a reflector at a time: the block...
Definition svd.hpp:196
void start_bidiagonal_node(bidiagonal_node &node)
Its singular values and vectors into node's, from scratch: u zero, v the identity.
Definition svd.hpp:1284
void multiply_real_left(const buffer< double > &left, buffer< T > &zt, std::size_t n)
zt ← left · zt, n × n, row-major, for any other element type: the real factor converted.
constexpr std::size_t sort_rows
The rows a task of merge_arrow reorders in place, one row's buffer between them.
Definition svd.hpp:928
void bidiagonalize_unblocked(buffer< T > &b, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form=true)
bidiagonalize_unblocked of the square n × n row-major b.
Definition svd.hpp:623
void to_matrix_basis(const tridiagonal_reduction< T > &reduction, buffer< T > &at, std::size_t n, std::size_t rows)
The rows rows of at (n columns, every row by default), vectors in the tridiagonal's basis,...
buffer< double > tall_singular_values(buffer< T > b, std::size_t rows, std::size_t n, qd_index sweeps=dqds_sweeps)
The singular values of the square n × n row-major b, descending, without its vectors: those of its Go...
Definition svd.hpp:2144
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
Definition parallel.hpp:760
constexpr double jacobi_tiny
The sum of squares under which one-sided Jacobi judges a pair of columns over their norms: below it a...
Definition svd.hpp:44
buffer< double > square_singular_values(buffer< T > b, std::size_t n, qd_index sweeps=dqds_sweeps)
Definition svd.hpp:2166
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
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
Definition parallel.hpp:995
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 ...
vector< T > solve(matrix< T > a, const vector< T > &b)
Solves the linear system A x = b for a square A.
matrix< T > pinv(const matrix< T > &a, rank_cutoff cutoff={}, bool hermitian=false)
The Moore–Penrose pseudo-inverse of the m × n a (n × m), as numpy.linalg.pinv gives it: V Σ⁺ Uᴴ,...
Definition svd.hpp:3241
constexpr std::size_t transpose_tile
The square blocks transpose copies one at a time: a block's rows of the source and of the result both...
Definition matrix.hpp:243
std::pair< vector< double >, matrix< double > > tridiagonal_eigen(const vector< double > &d, const vector< double > &e)
The eigenvalues, ascending, and the orthonormal eigenvectors (the columns, in their order) of the rea...
Definition svd.hpp:2862
eigen_subset< T > hermitian_eigen_subset_by_value(const matrix< T > &a, double low, double high, bool vectors=true)
hermitian_eigen_subset of the eigenvalues in (low, high], as scipy.linalg.eigh(a, subset_by_value=[lo...
Definition svd.hpp:3000
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
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
eigen_subset< T > hermitian_eigen_subset(const matrix< T > &a, std::size_t first, std::size_t last, bool vectors=true)
The eigenvalues of indices first to last (ascending, from 0) of the real symmetric or complex Hermiti...
Definition svd.hpp:2978
std::vector< tensor< std::int64_t > > nonzero(const tensor< T > &t)
The indices of the nonzero elements (x != T {}: a NaN is one), one tensor per axis,...
svd_method
How numerical::svd_decomposition computes the decomposition of R, after a Householder QR.
Definition svd.hpp:1551
@ bidiagonal_qr
Golub–Kahan bidiagonalisation then implicit-shift QR, as LAPACK's dgesvd.
@ jacobi
Cyclic Jacobi rotations: several times slower, kept as an independent second method.
tensor< T > diagonal(const tensor< T > &t, std::ptrdiff_t offset)
The offset diagonal of each matrix of t (its last two axes), as numpy.linalg.diagonal: above the main...
std::size_t matrix_rank(const matrix< T > &a, rank_cutoff cutoff={}, bool hermitian=false)
The numerical rank of a, as numpy.linalg.matrix_rank counts it: its singular values above cutoff.
Definition svd.hpp:3215
matrix< double > tridiagonal_eigenvectors(const vector< double > &d, const vector< double > &e, const vector< double > &values)
The orthonormal eigenvectors (the columns, in their order) of the real symmetric tridiagonal matrix o...
Definition svd.hpp:2800
vector< T > lstsq(const matrix< T > &a, const vector< T > &b, rank_cutoff cutoff={})
The minimum-norm least-squares solution of A x ≈ b, as NumPy's lstsq gives it.
Definition svd.hpp:2226
T min(const tensor< T > &t)
The smallest element (a NaN, if there is one), of a transpose's elements as they lie (in any order th...
vector< double > singular_values(const matrix< T > &a)
The singular values of a, descending, without its singular vectors, as numpy.linalg....
Definition svd.hpp:2274
matrix< T > inverse(matrix< T > a)
The inverse of a square matrix.
std::pair< std::ptrdiff_t, std::ptrdiff_t > tridiagonal_eigenvalue_range(const vector< double > &d, const vector< double > &e, double low, double high)
The indices [first, last] (ascending, from 0) of the eigenvalues in (low, high] of the real symmetric...
Definition svd.hpp:2516
vector< double > tridiagonal_eigenvalues(const vector< double > &d, const vector< double > &e)
The eigenvalues of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e,...
Definition svd.hpp:2405
vector< double > symmetric_eigenvalues(const matrix< T > &a)
The eigenvalues of the real symmetric or complex Hermitian a, ascending, without its eigenvectors,...
Definition svd.hpp:2328
tensor< T > full(std::vector< std::size_t > shape, const T &value)
A tensor of shape with every element value.
The buffers merge_arrow works in, kept by each thread from one join to the next (thread_arrow_workspa...
Definition svd.hpp:934
workspace_buffer above
poles[j] + roots[i]; then the right vectors.
Definition svd.hpp:936
workspace_buffer factor
The rows of the arrow's vectors for those columns.
Definition svd.hpp:940
workspace_buffer new_v
The kept columns of v times the right vectors.
Definition svd.hpp:938
workspace_buffer below
poles[j] − roots[i], row by root; then their product with above, then the left vectors.
Definition svd.hpp:935
workspace_buffer new_u
The kept columns of u times the left vectors.
Definition svd.hpp:937
workspace_buffer columns
One segment's rows of the kept columns that reach it.
Definition svd.hpp:939
One block of bidiagonal_divide's tree: the bidiagonal it decomposes (its own copies scaled by a power...
Definition svd.hpp:1220
const double * d
The diagonal it is solved on.
Definition svd.hpp:1221
The reflections of a Householder QR, Q left as its blocks of reflectors.
The reflectors of one panel of the blocked QR, I − V T Vᴴ as LAPACK's dlarft forms it.
A root of a secular equation: the pole it was sought from, and its offset from that pole.
The factors of T − λ I for a symmetric tridiagonal T, as LAPACK's dlagtf leaves them: P (T − λ I) = L...
Definition svd.hpp:2547
buffer< double > a
U's diagonal.
Definition svd.hpp:2548
std::vector< bool > swapped
Whether rows k and k + 1 were interchanged at step k.
Definition svd.hpp:2552
buffer< double > d
U's second superdiagonal.
Definition svd.hpp:2551
buffer< double > c
L's multipliers.
Definition svd.hpp:2550
buffer< double > b
U's first superdiagonal.
Definition svd.hpp:2549
A thin QR factorisation, row-major: q is rows × cols with orthonormal columns, r is cols × cols upper...
buffer< T > q
The orthonormal factor.
buffer< T > r
The triangular factor.
The unitary M = Q Dᴴ of a reduction to real tridiagonal form, A = M T Mᴴ, kept as its factors.
One buffer of merge_workspace: its storage and how many elements it holds.
Some eigenvalues of a Hermitian matrix and their eigenvectors (hermitian_eigen_subset).
Definition svd.hpp:2882
matrix< T > vectors
n × k, orthonormal, a column an eigenvalue in its order (n × 0 without vectors).
Definition svd.hpp:2884
vector< double > values
Ascending.
Definition svd.hpp:2883
A least-squares solution and what numpy.linalg.lstsq reports beside it (least_squares).
Definition svd.hpp:3013
vector< double > singular_values
The singular values of A, descending (singular_values).
Definition svd.hpp:3017
matrix< T > solution
The minimum-norm x of A x ≈ B (n × k), lstsq's.
Definition svd.hpp:3014
vector< double > residuals
Per column of B, ‖B − A x‖²: for a tall A of full column rank, else empty.
Definition svd.hpp:3015