7#ifndef NUMERICAL_SVD_HPP
8#define NUMERICAL_SVD_HPP
44 inline constexpr double jacobi_tiny {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()};
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]);
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())};
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)};
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]));
99 double magnitude {
static_cast<double>(std::abs(
gamma))};
111 for (std::size_t i {0}; i < n; ++i) {
114 const double size {
static_cast<double>(std::abs(
cosine))};
118 const double held {2.0 * std::sqrt(
static_cast<double>(n)) *
static_cast<double>(std::numeric_limits<value_range_t<T>>
::denorm_min())
127 if (magnitude <=
epsilon * std::sqrt(
alpha) * std::sqrt(beta)) {
130 zeta = (beta -
alpha) / (2.0 * magnitude);
140 const double c {1.0 / std::sqrt(1.0 + (t * t))};
141 const double s {c * t};
146 T*
mp {
side->data() + (p * n)};
147 T*
mq {
side->data() + (q * n)};
148 for (std::size_t i {0}; i < n; ++i) {
154 after_p +=
static_cast<double>(std::norm(
mp[i]));
155 after_q +=
static_cast<double>(std::norm(
mq[i]));
167 std::fill_n(w.data() + (
column * n), n,
T {});
179 throw convergence_error(
"SVD: one-sided Jacobi did not converge within its sweeps");
212 template <
typename T>
227 ut.assign(n * n,
T {});
228 vt.assign(n * n,
T {});
229 for (std::size_t k {0}; k < n; ++k) {
233 std::vector<buffer<T>>
shifted(n);
235 for (std::size_t k {0}; k + 1 < n; ++k) {
240 for (std::size_t k {n}; k-- > 0;) {
246 for (std::size_t
k1 {n};
k1 > 0;) {
258#ifdef NUMERICAL_X86_COMPILED
268#ifdef NUMERICAL_X86_COMPILED
274 template <
typename T>
300 template <
typename T>
314 std::vector<buffer<T>>
left(n);
315 std::vector<buffer<T>>
right(n);
320 const auto nonzero {[](
const T& value) {
return value !=
T {}; }};
330#ifdef NUMERICAL_X86_COMPILED
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) {
339 for (std::size_t k {
k0}; k < std::min(
k1, r + 1); ++k) {
340 columns[((k -
k0) * n) + r] = b[(r * n) + k];
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
350 for (std::size_t k {
k0}; k <
k1; ++k) {
351 const std::size_t i {k -
k0};
352#ifdef NUMERICAL_X86_COMPILED
356 constexpr std::size_t
from {0};
358 for (std::size_t p {
from}; p < i; ++p) {
360 factors[(2 * (p -
from)) + 1] = *
u_row(p, k);
362 T*
const column {columns.data() + (i * n) + k};
366 for (std::size_t r {0}; r < n - k; ++r) {
372 if (std::any_of(x.begin() + 1, x.end(),
nonzero)) {
375 d[k] =
static_cast<double>(std::abs(beta));
379 d[k] =
static_cast<double>(beta);
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) {
390 const std::size_t
span {n - k - 1};
398 const std::size_t first {k + 1 + (chunk *
chunk_width)};
399 const std::size_t count {std::min(
chunk_width, n - first)};
403 for (std::size_t c {0}; c < count; ++c) {
407 std::copy(x.begin(), x.end(),
v_row(i, k));
408 left[k] = std::move(x);
412 d[k] =
static_cast<double>(std::abs(x[0]));
416 d[k] =
static_cast<double>(x[0]);
421 buffer<T> y(b.begin() +
static_cast<std::ptrdiff_t
>((k * n) + k + 1),
422 b.begin() +
static_cast<std::ptrdiff_t
>((k + 1) * n));
423 for (std::size_t p {0}; p <= i; ++p) {
424 factors[p] = *
v_row(p, k);
427 for (std::size_t p {0}; p < i; ++p) {
428 factors[p] = *
x_row(p, k);
436 if (std::any_of(
y.begin() + 1,
y.end(),
nonzero)) {
439 e[k] =
static_cast<double>(std::abs(beta));
443 e[k] =
static_cast<double>(beta);
446 const std::size_t rows {n - k - 1};
450#ifdef NUMERICAL_X86_COMPILED
459 else if (
task - rows <= i) {
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) {
471 constexpr std::size_t
band {256};
473 const std::size_t first {c *
band};
474 const std::size_t count {std::min(
band, rows - first)};
477 for (std::size_t r {first}; r < first + count; ++r) {
480 if (next !=
nullptr) {
489 for (std::size_t p {0}; p <= i; ++p) {
492 for (std::size_t p {0}; p < i; ++p) {
500 for (std::size_t r {0}; r < rows; ++r) {
505 std::transform(
y.begin(),
y.end(),
u_row(i, k + 1), [](
const T& value) {
return conj_of(value); });
510 e[k] =
static_cast<double>(std::abs(
y[0]));
514 e[k] =
static_cast<double>(
y[0]);
518 const std::size_t
rest {n -
k1};
521 for (std::size_t r {0}; r <
rest; ++r) {
522 for (std::size_t p {0}; p < width; ++p) {
554 template <
typename T>
564 std::vector<buffer<T>>
left(n);
565 std::vector<buffer<T>>
right(n);
570 for (std::size_t k {0}; k < n; ++k) {
572 for (std::size_t i {k}; i < rows; ++i) {
573 x[i - k] = b[(i * n) + k];
575 if (
scaled_norm(x.data() + 1, x.size() - 1) > 0.0) {
578 b[(k * n) + k] = beta;
579 left[k] = std::move(x);
583 for (std::size_t j {k}; j < n; ++j) {
586 d[k] =
static_cast<double>(std::abs(b[(k * n) + k]));
591 for (std::size_t j {k + 1}; j < n; ++j) {
592 y[j - k - 1] =
conj_of(b[(k * n) + j]);
594 if (
y.size() > 1 &&
scaled_norm(
y.data() + 1,
y.size() - 1) > 0.0) {
596 parallel_for(rows - k - 1, 2 *
y.size(), [&](std::size_t r) {
597 T* row {b.data() + ((k + 1 + r) * n) + k + 1};
599 for (std::size_t j {0}; j <
y.size(); ++j) {
603 b[(k * n) + k + 1] = beta;
608 for (std::size_t i {k}; i < rows; ++i) {
611 e[k] =
static_cast<double>(std::abs(b[(k * n) + k + 1]));
622 template <
typename T>
635 template <
typename T>
662 template <
typename T>
672 std::vector<row_operation>
on_vt;
673 std::vector<row_operation>
on_ut;
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()};
679 std::size_t steps {0};
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};
698 if (
bb != 0.0 ||
cc != 0.0) {
704 for (std::size_t j {first}; j + 1 < end; ++j) {
711 f = (cs *
dd(j)) + (sn *
ee(j));
712 ee(j) = (cs *
ee(j)) - (sn *
dd(j));
714 dd(j + 1) = cs *
dd(j + 1);
716 right.push_back({row_operation::kind::rotate, at(j), at(j + 1), cs, sn});
722 f = (cs *
ee(j)) + (sn *
dd(j + 1));
723 dd(j + 1) = (cs *
dd(j + 1)) - (sn *
ee(j));
726 ee(j + 1) = cs *
ee(j + 1);
729 left.push_back({row_operation::kind::rotate, at(j), at(j + 1), cs, sn});
736 std::size_t k {p - 1};
738 if (std::abs(e[k]) <= tiny + (
epsilon * (std::abs(d[k]) + std::abs(d[k + 1])))) {
743 const std::size_t
top {k ==
none ? 0 : k + 1};
748 on_vt.push_back({row_operation::kind::negate,
top,
top, 0.0, 0.0});
751 for (std::size_t j {
top}; j + 1 < n && d[j] < d[j + 1]; ++j) {
752 std::swap(d[j], d[j + 1]);
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});
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)};
774 for (std::size_t j {p - 1}; j-- >
top;) {
776 const double cs {d[j] / t};
777 const double sn {f / t};
781 e[j - 1] = cs * e[j - 1];
784 on_vt.push_back({row_operation::kind::rotate, j, p - 1, cs, sn});
792 for (std::size_t j {
zero + 1}; j < p; ++j) {
794 const double cs {d[j] / t};
795 const double sn {f / t};
800 on_ut.push_back({row_operation::kind::rotate, j,
zero, cs, sn});
806 throw convergence_error(
"SVD: the bidiagonal QR iteration did not converge within its steps");
810 down = std::abs(d[
top]) >= std::abs(d[p - 1]);
821 const std::size_t
ends {
top + p - 1};
838 template <
typename Entry>
844 std::vector<double> largest(
bands, 0.0);
848 for (std::size_t j {0}; j < cols; ++j) {
849 most = std::max(
most,
static_cast<double>(std::abs(
entry(i, j))));
854 const double scale {std::accumulate(largest.begin(), largest.end(), 0.0, [](
double x,
double y) { return std::max(x, y); })};
859 template <
typename T>
862 const std::size_t rows {a.
rows()};
863 const std::size_t cols {a.
cols()};
871 [&](std::size_t j, std::size_t i) { entries[(j * rows) + i] =
conj_of(a(i, j)); });
874 return matrix<T> {cols, rows, std::move(entries)};
900 return (d[j] - d[o]) * (d[j] + d[o]);
904 for (std::size_t j {0}; j < d.size(); ++j) {
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);
1002 std::vector<unsigned>
reach_u(n, 4U);
1003 std::vector<unsigned>
reach_v(m, 4U);
1006 for (std::size_t j {1}; j <=
split; ++j) {
1010 const auto turned {[](std::vector<unsigned>&
reach, std::size_t a, std::size_t b) {
1013 std::vector<std::size_t> order(n - 1);
1014 for (std::size_t j {1}; j < n; ++j) {
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);
1022 if (largest == 0.0) {
1025 const double tolerance {8.0 * std::numeric_limits<double>::epsilon() * largest};
1029 std::vector<std::size_t>
kept {0};
1030 std::vector<std::size_t> deflated;
1032 for (
const std::size_t j : order) {
1034 deflated.push_back(j);
1039 const double length {std::hypot(z[0], z[j])};
1044 deflated.push_back(j);
1049 const double length {std::hypot(z[j], z[
pending])};
1050 const double c {z[j] / length};
1051 const double s {z[
pending] / length};
1068 const std::size_t k {
kept.size()};
1071 for (std::size_t i {0}; i < k; ++i) {
1083 for (std::size_t j {0}; j < k; ++j) {
1084 below[(i * k) + j] *= above[(i * k) + j];
1087 double*
const squares {below};
1094 std::array<double, lowner_block>
product {};
1095 for (std::size_t j {first}; j <
last; ++j) {
1098 for (std::size_t i {0}; i < k; ++i) {
1099 for (std::size_t j {first}; j <
last; ++j) {
1105 for (std::size_t j {first}; j <
last; ++j) {
1112 double*
const right {above};
1114 for (std::size_t i {0}; i < k; ++i) {
1118 double*
const left {below};
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];
1124 for (
double*
const vectors : {
left,
right}) {
1126 for (std::size_t j {0}; j < k; ++j) {
1127 for (std::size_t i {0}; i < k; ++i) {
1128 length[i] += vectors[(j * k) + i] * vectors[(j * k) + i];
1131 for (
double& l : length) {
1135 for (std::size_t i {0}; i < k; ++i) {
1136 vectors[(j * k) + i] /= length[i];
1143 using segment = std::tuple<std::size_t, std::size_t, unsigned>;
1146 for (
const auto& [first, count,
bit] :
segments) {
1148 for (std::size_t i {0}; i < k; ++i) {
1153 const std::size_t width {
reaching.size()};
1157 for (std::size_t c {0}; c < width; ++c) {
1160 std::fill_n(
product + ((first + r) * k), k, 0.0);
1162 for (std::size_t c {0}; c < width; ++c) {
1163 std::copy_n(small + (
reaching[c] * k), k, factor + (c * k));
1165 gemm(count, k, width, columns, width, factor, k,
product + (first * k), 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);
1173 std::vector<std::size_t>
from(n);
1174 for (std::size_t i {0}; i < k; ++i) {
1175 values[i] = roots[i];
1178 for (std::size_t i {0}; i < deflated.size(); ++i) {
1179 values[k + i] = d[deflated[i]];
1180 from[k + i] = k + i;
1182 std::vector<std::size_t> rank(n);
1183 for (std::size_t j {0}; j < n; ++j) {
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);
1188 for (std::size_t c {0}; c < n; ++c) {
1190 d[c] = values[rank[c]];
1197 for (std::size_t r {block *
sort_rows}; r < std::min(m, (block + 1) *
sort_rows); ++r) {
1199 for (std::size_t c {0}; c < n; ++c) {
1202 std::copy(
row.begin(),
row.end(), u.begin() +
static_cast<std::ptrdiff_t
>(r * n));
1204 for (std::size_t c {0}; c < n; ++c) {
1207 std::copy(
row.begin(),
row.end(), v.begin() +
static_cast<std::ptrdiff_t
>(r * m));
1224 std::size_t extra {};
1229 std::size_t first {};
1230 std::size_t second {};
1231 std::size_t depth {};
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});
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;
1266 const std::size_t index {
nodes.size()};
1272 const double*
const work_d {
node.d};
1273 const double*
const work_e {
node.e};
1274 const std::size_t k {
node.k};
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;
1286 const std::size_t m {
node.n +
node.extra};
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;
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};
1309 std::copy_n(e, n - std::min<std::size_t>(n, 1),
super.begin());
1312 double fill {extra == 1 ? e[n - 1] : 0.0};
1313 for (std::size_t j {n}; extra == 1 && j-- > 0;) {
1315 const double c {length == 0.0 ? 1.0 :
diagonal[j] / length};
1316 const double s {length == 0.0 ? 0.0 :
fill / length};
1326 for (std::size_t i {0}; i < n; ++i) {
1327 ut[(i * n) + i] = 1.0;
1328 vt[(i * n) + i] = 1.0;
1332 for (std::size_t c {0}; c < n; ++c) {
1333 const std::size_t
source {n - 1 - c};
1335 for (std::size_t r {0}; r < n; ++r) {
1336 u[(r * n) + c] =
ut[(
source * n) + r];
1338 for (std::size_t r {0}; r < m; ++r) {
1339 double sum {extra == 1 ? 0.0 :
vt[(
source * n) + r]};
1340 for (std::size_t t {0}; extra == 1 && t < n; ++t) {
1343 v[(r * m) + c] =
sum;
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};
1361 const double beta {
node.e[k]};
1370 const std::size_t
m1 {k + 1};
1371 const std::size_t
m2 {lower + extra};
1376 for (std::size_t c {0}; c < k; ++c) {
1379 for (std::size_t r {0}; r < k; ++r) {
1380 u[(r * n) + 1 + c] =
u1[(r * k) + c];
1383 for (std::size_t c {0}; c < lower; ++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];
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];
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];
1404 for (std::size_t r {0}; r <
m2; ++r) {
1405 v[((
m1 + r) * m) + n] =
v2[(r *
m2) + lower];
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};
1421 if (
node.exponent != 0) {
1422 for (
double& value :
node.sigma) {
1423 value = std::ldexp(value,
node.exponent);
1445 if (
nodes[index].k == 0) {
1482 std::vector<bidiagonal_node>
nodes;
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) {
1497 std::vector<std::size_t>
joins;
1498 for (std::size_t i {0}; i <
nodes.size(); ++i) {
1510 sigma = std::move(
nodes[0].sigma);
1511 u = std::move(
nodes[0].u);
1512 v = std::move(
nodes[0].v);
1521 template <
typename T>
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)];
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");
1579 return static_cast<double>(x);
1613 svd_method method = svd_method::divide_and_conquer,
1616 detail::require_finite(a,
"SVD");
1618 factor(a, method,
full);
1621 factor(detail::adjoint(a), method,
full);
1636 svd_method method = svd_method::divide_and_conquer,
1639 detail::require_finite(a,
"SVD");
1640 if (a.rows() >= a.cols()) {
1641 factor(std::move(a), method,
full);
1644 factor(detail::adjoint(a), method,
full);
1652 return singular_values_;
1664 return std::move(u_);
1677 return detail::adjoint(v_);
1689 const std::vector<T>& phases,
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];
1700 for (std::size_t i {cols}; i < width; ++i) {
1701 u[(i * width) + i] = T {1};
1703 detail::apply_q(u, blocks, rows, width);
1704 return matrix<T> {rows, width, std::move(u)};
1717 if (width == cols) {
1718 return matrix<T> {rows, cols, std::move(q)} *
matrix<T> {cols, cols, std::move(left)};
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];
1727 return matrix<T> {rows, rows, std::move(u)};
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);
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) {
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])));
1776 largest[band] = most;
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;
1790 const bool direct {rows == cols && method != svd_method::jacobi};
1791 const std::size_t width {
full ? rows : cols};
1794 const bool applied {!direct && method != svd_method::jacobi};
1795 std::vector<detail::reflector_block<T>> blocks;
1796 std::vector<T> phases;
1799 factors.
r = std::move(entries);
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) {
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]);
1814 factors = detail::householder_qr(std::move(entries), rows, cols,
full);
1816 if (method != svd_method::jacobi) {
1821 detail::bidiagonalize(factors.
r, cols, d, e, ut, vt);
1823 if (method == svd_method::bidiagonal_qr) {
1824 detail::bidiagonal_qr(d, e, ut, vt, cols, detail::svd_qr_steps_per_value * cols);
1827 detail::bidiagonal_divide_and_conquer(d, e, ut, vt, cols);
1830 detail::transpose_into(ut.data(), cols, cols, left.data());
1833 detail::transpose_into(vt.data(), cols, cols, right.data());
1835 for (
double& value : d) {
1836 value = detail::singular_value_in_double(
static_cast<carried
>(value) * scale);
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)};
1845 for (std::size_t i {0}; i < cols; ++i) {
1846 right[(i * cols) + i] = T {1};
1848 detail::one_sided_jacobi(w, right, cols, detail::jacobi_sweeps);
1851 for (std::size_t j {0}; j < cols; ++j) {
1853 for (std::size_t i {0}; i < cols; ++i) {
1854 column[i] = w[(i * cols) + j];
1856 norms[j] =
static_cast<double>(detail::scaled_norm(column));
1858 std::vector<std::size_t> order(cols);
1859 for (std::size_t j {0}; j < cols; ++j) {
1862 std::stable_sort(order.begin(), order.end(), [&norms](std::size_t x, std::size_t y) { return norms[x] > norms[y]; });
1868 buffer<T> sorted_right(cols * cols, T {});
1871 const double coarser_epsilon {std::max(
static_cast<double>(std::numeric_limits<
detail::value_range_t<T>>::epsilon()), std::numeric_limits<double>::epsilon())};
1875 std::vector<double> residual(cols, 1.0);
1876 for (std::size_t d {0}; d < cols; ++d) {
1878 for (std::size_t k {0}; k < cols; ++k) {
1879 residual[k] -=
static_cast<double>(std::norm(left[(k * cols) + d - 1]));
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];
1887 if (norms[j] > 0.0) {
1889 for (std::size_t i {0}; i < cols; ++i) {
1890 unit[i] = w[(i * cols) + j] / detail::from_carried<T>(norms[j]);
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];
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);
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);
1912 u_ = left_vectors(std::move(factors.
q), std::move(left), rows, cols, width);
1913 v_ =
matrix<T> {cols, cols, std::move(sorted_right)};
1918 static constexpr double separate_columns {64.0};
1926 double largest {0.0};
1927 for (std::size_t c {0}; c < count; ++c) {
1929 for (std::size_t i {0}; i < n; ++i) {
1930 projection += detail::conj_of(basis[(i * n) + c]) * x[i];
1932 largest = std::max(largest,
static_cast<double>(std::abs(projection)));
1943 for (std::size_t c {0}; c < count; ++c) {
1945 for (std::size_t i {0}; i < n; ++i) {
1946 projection += detail::conj_of(basis[(i * n) + c]) * x[i];
1948 for (std::size_t i {0}; i < n; ++i) {
1949 x[i] -= projection * basis[(i * n) + c];
1968 double largest {0.0};
1969 for (std::size_t d {0}; d < sigma.
size(); ++d) {
1970 largest = std::max(largest, sigma[d]);
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);
1986 template <
typename T>
1990 return std::scalbn(x, exponent);
1994 template <
typename U>
1998 return std::complex<U> {std::scalbn(x.real(), exponent), std::scalbn(x.imag(), exponent)};
2006 template <
typename T>
2010 constexpr std::size_t width {64};
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};
2018 row[i - first] = T {1};
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];
2029 template <
typename T>
2032 qd_index sweeps = dqds_sweeps);
2051 template <
typename T>
2056 std::pair<
buffer<T>,
int>*
const r =
nullptr)
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};
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))));
2069 if (largest == 0.0) {
2070 return std::nullopt;
2072 const int exponent {std::ilogb(largest)};
2074 for (std::size_t i {0}; i < m; ++i) {
2075 for (std::size_t j {0}; j < n; ++j) {
2080 entries[(i * cols) + j] =
scaled_by_two(a(i, j), -exponent);
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]));
2092 const double smallest_bound {1.0 / std::sqrt(inverse_squares)};
2098 return std::nullopt;
2100 values = std::move(sigma);
2102 const std::size_t k {b.
cols()};
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;) {
2117 gemm(n, k, cols,
inverse.data(), cols, y.data(), k, x.data(), k);
2119 for (T& value : x) {
2123 *r = {std::move(factors.r), exponent};
2143 template <
typename T>
2165 template <
typename T>
2177 template <
typename T>
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()};
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));
2194 for (std::size_t j {0}; j < cols; ++j) {
2195 right[(j * rank) + d] = s.
v()(j, d);
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]);
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)};
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())};
2253 throw dimension_error(
"lstsq: right-hand side size differs from the matrix");
2255 detail::require_finite(a,
"lstsq");
2256 buffer<double> values;
2257 if (std::optional<matrix<T>> fast {detail::lstsq_by_qr(a, b, cutoff, values)}) {
2258 return *std::move(fast);
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);
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()};
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)};
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;
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; });
2306 const bool direct {rows != cols && cols < detail::bidiagonal_crossover && rows * 4 < cols * 5};
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,
2311 for (
double& value : d) {
2330 const std::size_t n {a.
rows()};
2331 if (a.
cols() != n) {
2332 throw dimension_error(
"symmetric eigenvalues require a square matrix");
2334 detail::require_finite_lower(a,
"symmetric eigenvalues");
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 {};
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);
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 {});
2354 static_cast<void>(detail::tridiagonalize(entries, n, d, off));
2355 detail::tridiagonal_ql(d, off,
none, n, detail::ql_steps_per_value * n);
2357 std::sort(d.begin(), d.end());
2358 for (
double& value : d) {
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");
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");
2384 largest = std::max({largest, std::abs(d[i]), std::abs(off_entry)});
2389 for (std::size_t i {0}; i < n; ++i) {
2391 off[i] = i + 1 < n ? e[i] / scale : 0.0;
2410 const double scale {detail::scaled_tridiagonal(d, e,
diagonal, off)};
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) {
2441 count += q < 0.0 ? 1 : 0;
2445 q = (d[i + 1] - x) - (e2[i] / q);
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");
2471 constexpr double ulp {std::numeric_limits<double>::epsilon()};
2472 constexpr double safmin {std::numeric_limits<double>::min()};
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]);
2479 const double pivmin {safmin * std::max(1.0, largest)};
2482 for (std::size_t i {0}; i < n; ++i) {
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);
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)};
2491 const double tolerance {ulp * norm};
2494 detail::parallel_for(last - first + 1, detail::sturm_bisection_work * n, [&](std::size_t index) {
2495 const std::size_t j {first + index};
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;
2504 out[index] = 0.5 * (lo + hi) * scale;
2523 const double scale {detail::scaled_tridiagonal(d, e,
diagonal, off)};
2524 const std::size_t n {d.
size()};
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]);
2534 const double pivmin {std::numeric_limits<double>::min() * std::max(1.0, largest)};
2535 const auto at_most = [&](
double x) {
2536 return detail::sturm_count(
diagonal.data(), e2.data(), n, std::nextafter(x / scale, std::numeric_limits<double>::infinity()), pivmin);
2538 return {
static_cast<std::ptrdiff_t
>(at_most(low)),
static_cast<std::ptrdiff_t
>(at_most(high)) - 1};
2567 f.
b.assign(off, off + n - 1);
2568 f.
c.assign(off, off + n - 1);
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])};
2577 scale2 += std::abs(f.
b[k + 1]);
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) {
2582 if (f.
c[k] != 0.0) {
2584 f.
a[k + 1] -= f.
c[k] * f.
b[k];
2589 const double multiplier {f.
a[k] / f.
c[k]};
2591 const double below {f.
a[k + 1]};
2592 f.
a[k + 1] = f.
b[k] - (multiplier * below);
2594 f.
d[k] = f.
b[k + 1];
2595 f.
b[k + 1] = -multiplier * f.
d[k];
2598 f.
c[k] = multiplier;
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};
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});
2621 tol = tol == 0.0 ? eps : tol * eps;
2623 for (std::size_t k {1}; k < n; ++k) {
2625 const double above {y[k - 1]};
2627 y[k] = above - (f.
c[k - 1] * y[k]);
2630 y[k] -= f.
c[k - 1] * y[k - 1];
2633 for (std::size_t k {n}; k-- > 0;) {
2636 temp -= f.
b[k] * y[k + 1];
2639 temp -= f.
d[k] * y[k + 2];
2642 double pert {std::copysign(tol, ak)};
2644 const double absak {std::abs(ak)};
2645 if (absak >= 1.0 || (absak >= least && std::abs(temp) <= absak * bignum)) {
2648 if (absak >= least || absak == 0.0 || std::abs(temp) * least > absak) {
2665 std::size_t n)
noexcept
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;
2674 x[i] = (
static_cast<double>(z >> 11U) * 0x1.0p-52) - 1.0;
2703 std::size_t most_solves = 5)
2705 constexpr std::size_t extra {2};
2706 constexpr double eps {std::numeric_limits<double>::epsilon()};
2707 const std::size_t k {values.size()};
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));
2712 const double cluster_gap {1e-3 *
one_norm};
2713 const double growth {std::sqrt(0.1 /
static_cast<double>(n))};
2715 std::vector<std::size_t> starts;
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]));
2721 if (j == 0 || std::abs(shifts[j] - shifts[j - 1]) > cluster_gap) {
2722 starts.push_back(j);
2725 starts.push_back(k);
2726 for (std::size_t c {0}; c + 1 < starts.size(); ++c) {
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) {
2736 for (std::size_t j {starts[c]}; j < starts[c + 1]; ++j) {
2737 double*
const x {z.data() + (j * n)};
2741 std::size_t checks {0};
2745 for (std::size_t i {0}; i < n; ++i) {
2746 sum += std::abs(x[i]);
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) {
2753 for (std::size_t p {starts[c]}; p < j; ++p) {
2754 const double*
const v {z.data() + (p * n)};
2756 for (std::size_t i {0}; i < n; ++i) {
2759 for (std::size_t i {0}; i < n; ++i) {
2763 double largest {0.0};
2764 for (std::size_t i {0}; i < n; ++i) {
2765 largest = std::max(largest, std::abs(x[i]));
2767 checks += largest >= growth ? 1 : 0;
2768 done = checks > extra;
2771 converged.store(
false, std::memory_order_relaxed);
2773 double squares {0.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;
2779 const double unit {(x[at] < 0.0 ? -1.0 : 1.0) / std::sqrt(squares)};
2780 for (std::size_t i {0}; i < n; ++i) {
2785 return converged.load();
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()};
2810 throw dimension_error(
"tridiagonal_eigenvectors: at most n eigenvalues");
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");
2817 if (j > 0 && values[j] < values[j - 1]) {
2818 throw dimension_error(
"tridiagonal_eigenvectors: the eigenvalues must be ascending");
2820 shifted[j] = values[j] / scale;
2826 else if (n > 1 && !detail::inverse_iteration(
diagonal, off, n, shifted, z)) {
2829 detail::divide_and_conquer(all.data(), off.data(), n, q);
2831 std::size_t next {0};
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])) {
2837 column = std::min(column, n - (k - j));
2839 for (std::size_t i {0}; i < n; ++i) {
2840 z[(j * n) + i] = q[(i * n) + column];
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];
2865 const std::size_t n {d.
size()};
2868 const double scale {detail::scaled_tridiagonal(d, e,
diagonal, off)};
2871 detail::divide_and_conquer(
diagonal.data(), off.data(), n, q);
2880 template <
typename T>
2894 template <
typename T>
2899 const std::string& name)
2901 const std::size_t n {a.
rows()};
2902 if (a.
cols() != n) {
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))));
2914 for (std::size_t i {0}; i < n; ++i) {
2915 for (std::size_t j {0}; j <= i; ++j) {
2916 work[(i * n) + j] = a(i, j) / T {scale};
2925 const auto [first, last] {select(d, e, scale)};
2929 const auto from {
static_cast<std::size_t
>(first)};
2930 const auto k {
static_cast<std::size_t
>(last - first + 1)};
2934 std::transform(values.begin(), values.end(),
scaled.begin(), [scale](
double value) { return value * scale; });
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];
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];
2976 template <
typename T>
2977 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2981 bool vectors =
true)
2983 if (first > last || last >= a.
rows()) {
2984 throw dimension_error(
"hermitian_eigen_subset: the indices must satisfy first ≤ last < n");
2987 return std::pair {
static_cast<std::ptrdiff_t
>(first),
static_cast<std::ptrdiff_t
>(last)};
2988 }, vectors,
"hermitian_eigen_subset");
2998 template <
typename T>
2999 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
3003 bool vectors =
true)
3007 }, vectors,
"hermitian_eigen_subset_by_value");
3011 template <
typename T>
3016 std::size_t rank {0};
3030 template <
typename T>
3036 throw dimension_error(
"lstsq: right-hand side size differs from the matrix");
3038 detail::require_finite(a,
"lstsq");
3040 std::pair<buffer<T>,
int> r;
3041 buffer<double> decided;
3042 std::optional<matrix<T>> fast {detail::lstsq_by_qr(a, b, cutoff, decided, &r)};
3043 std::optional<svd_decomposition<T>> s;
3047 buffer<double> values {!fast ? buffer<double>(s->singular_values().begin(), s->singular_values().end())
3049 : std::move(decided)};
3051 for (
double& value : values) {
3052 value = std::ldexp(value, r.second);
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;
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));
3068 return least_squares_solution<T> {.solution = std::move(x),
3069 .residuals = vector<double> {std::move(residuals)},
3071 .singular_values = sigma};
3078 template <
typename T>
3081 const std::size_t n {a.
rows()};
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));
3088 entries[(i * n) + i] = from_carried<T>(
real_part(a(i, i)));
3090 return matrix<T> {n, n, std::move(entries)};
3100 template <
typename T>
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]));
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) {
3119 const std::size_t rank {
kept.size()};
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) {
3128 for (std::size_t j {0}; j < rows; ++j) {
3129 left_adjoint[(e * rows) + j] =
conj_of(left(j, d));
3133 gemm(cols, rows, rank,
scaled.data(), rank, left_adjoint.data(), rows, out.data(), rows);
3134 return matrix<T> {cols, rows, std::move(out)};
3141 template <
typename T>
3149 template <
typename T>
3153 buffer<double> values(signed_values.begin(), signed_values.end());
3154 for (
double& value : values) {
3155 value = std::abs(value);
3176 template <
typename T>
3190 return inverse_on_kept(decomposition.values(), vectors, vectors, cutoff);
3199 return inverse_on_kept(decomposition.values(), vectors, vectors, cutoff);
3217 bool hermitian =
false)
3221 throw dimension_error(
"matrix_rank: a Hermitian matrix is square");
3223 detail::require_finite_lower(a,
"matrix_rank");
3224 return detail::numerical_rank(detail::hermitian_singular_values(a), a.
rows(), a.
cols(), cutoff);
3243 bool hermitian =
false)
3247 throw dimension_error(
"pinv: a Hermitian matrix is square");
3249 detail::require_finite_lower(a,
"pinv");
3250 return detail::hermitian_pseudo_inverse(a, cutoff);
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);
#define NUMERICAL_OUT_OF_LINE
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
Thrown when an iterative algorithm has not converged within its bound of sweeps.
Thrown when an operation's operands have incompatible shapes.
The eigenvalues and eigenvectors of a complex Hermitian matrix.
A dense, row-major matrix of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element (row-major).
std::size_t rows() const noexcept
The number of rows.
std::size_t cols() const noexcept
The number of columns.
Thrown when a decomposition's input holds an infinite or NaN entry: no factorisation of it means anyt...
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.
matrix< T > u_
m×k left singular vectors.
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.
const matrix< T > & v() const &noexcept
The right singular vectors V (columns): n × k, or n × n full.
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'...
matrix< T > v_
n×k right singular vectors.
const matrix< T > & u() const &noexcept
The left singular vectors U (columns): m × k, or m × m full.
svd_decomposition(const matrix< T > &a, svd_method method=svd_method::divide_and_conquer, bool full=false)
Decomposes a.
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...
void factor(matrix< T > &&a, svd_method method, bool full)
factor of an expiring matrix, its elements scaled in place.
matrix< T > vh() const
Vᴴ (k × n, or n × n full), so that A = U Σ Vᴴ reads u() * diag(singular_values()) * vh() (full,...
matrix< T > u() &&
U, moved out of an expiring decomposition (v and the singular values stay).
vector< double > singular_values_
Singular values, descending.
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,...
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...
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.
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.
const vector< double > & singular_values() const noexcept
The singular values, descending.
The eigenvalues and eigenvectors of a real symmetric matrix.
A dense vector of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
std::size_t size() const noexcept
The number of elements.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element.
A complex number of float or double, which gemm_split multiplies through the real kernel and the kern...
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.
arrow_workspace & thread_arrow_workspace()
The calling thread's arrow_workspace, kept from one decomposition to the next. A join uses it whole o...
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
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...
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 ...
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...
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...
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...
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...
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 ©)
transpose_pieces of side piece (transpose_piece's 8 or the whole tile), each side its own instance: a...
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...
constexpr std::size_t sturm_bisection_work
One eigenvalue's bisection in parallel_for's units per order of the matrix: some 60 halvings,...
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,...
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...
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.
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.
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,...
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...
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...
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,...
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_...
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...
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,...
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.
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...
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...
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 ...
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...
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...
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),...
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).
double singular_value_in_double(double x) noexcept
A singular value of a decomposition carried in double: x itself.
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),...
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.
matrix< T > hermitian_from_lower(const matrix< T > &a)
The real symmetric or complex Hermitian matrix whose lower triangle is the square a's,...
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...
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...
constexpr std::size_t inverse_iteration_cluster_most
The most eigenvalues tridiagonal_eigenvectors reorthogonalises together: a larger cluster's vectors c...
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 ...
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...
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.
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...
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.
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...
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,...
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.
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...
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,...
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...
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 × ...
constexpr std::size_t bidiagonal_leaf
The order up to which bidiagonal_divide decomposes by implicit-shift QR.
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,...
matrix< T > adjoint(const matrix< T > &a)
The conjugate transpose of a, as numerical::transpose copies (by blocks, on the threads).
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,...
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...
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...
void unscale_bidiagonal_node(bidiagonal_node &node)
The singular values of a solved node scaled back.
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...
void start_bidiagonal_node(bidiagonal_node &node)
Its singular values and vectors into node's, from scratch: u zero, v the identity.
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.
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.
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...
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,...
constexpr double jacobi_tiny
The sum of squares under which one-sided Jacobi judges a pair of columns over their norms: below it a...
buffer< double > square_singular_values(buffer< T > b, std::size_t n, qd_index sweeps=dqds_sweeps)
The NumericAL public API.
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
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ᴴ,...
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...
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...
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...
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...
@ 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...
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.
@ 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.
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...
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.
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....
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...
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,...
vector< double > symmetric_eigenvalues(const matrix< T > &a)
The eigenvalues of the real symmetric or complex Hermitian a, ascending, without its eigenvectors,...
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...
workspace_buffer above
poles[j] + roots[i]; then the right vectors.
workspace_buffer factor
The rows of the arrow's vectors for those columns.
workspace_buffer new_v
The kept columns of v times the right vectors.
workspace_buffer below
poles[j] − roots[i], row by root; then their product with above, then the left vectors.
workspace_buffer new_u
The kept columns of u times the left vectors.
workspace_buffer columns
One segment's rows of the kept columns that reach it.
One block of bidiagonal_divide's tree: the bidiagonal it decomposes (its own copies scaled by a power...
const double * d
The diagonal it is solved on.
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...
buffer< double > a
U's diagonal.
std::vector< bool > swapped
Whether rows k and k + 1 were interchanged at step k.
buffer< double > d
U's second superdiagonal.
buffer< double > c
L's multipliers.
buffer< double > b
U's first superdiagonal.
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).
matrix< T > vectors
n × k, orthonormal, a column an eigenvalue in its order (n × 0 without vectors).
vector< double > values
Ascending.
A least-squares solution and what numpy.linalg.lstsq reports beside it (least_squares).
vector< double > singular_values
The singular values of A, descending (singular_values).
matrix< T > solution
The minimum-norm x of A x ≈ B (n × k), lstsq's.
vector< double > residuals
Per column of B, ‖B − A x‖²: for a tall A of full column rank, else empty.