22#ifndef NUMERICAL_FACTORIZATIONS_HPP
23#define NUMERICAL_FACTORIZATIONS_HPP
84 const R largest {std::max(std::abs(pivot.real()), std::abs(pivot.imag()))};
106 template <
typename T>
118 template <
typename R>
122 return std::complex<R> {x.real() /
diagonal.real(), x.imag() /
diagonal.real()};
126 template <
typename T>
135 template <
typename R>
137 const std::complex<R>& a,
138 const std::complex<R>& b)
147#ifdef NUMERICAL_X86_COMPILED
176 static_assert(std::has_single_bit(
lu_small_block) && std::has_single_bit(
lu_block),
"a panel is a mask away");
177 static_assert(std::has_single_bit(
lu_wide_block),
"a panel is a mask away");
197#ifdef NUMERICAL_X86_COMPILED
206#ifdef NUMERICAL_X86_COMPILED
218#ifdef NUMERICAL_X86_COMPILED
242 return largest == 0.0 ? 1.0 : std::ldexp(1.0, std::ilogb(largest));
248#ifdef NUMERICAL_X86_COMPILED
275#ifdef NUMERICAL_X86_COMPILED
315 template <
typename T>
322 template <
typename U>
329 template <
typename T>
333 template <
typename T>
341 template <
typename U>
344 return std::abs(x.real()) + std::abs(x.imag());
349 template <
typename T>
350 using carried_t = std::conditional_t<std::is_same_v<magnitude_t<T>,
long double>,
long double,
double>;
354 template <
typename T>
361 template <
typename T>
368 template <
typename U>
376 template <
typename T>
378 std::conditional_t<std::is_same_v<T, float> || std::is_same_v<T, std::complex<float>>,
float,
carried_t<T>>;
382 template <
typename T>
389 template <
typename T>
393 constexpr real
least {
static_cast<real
>(std::numeric_limits<value_range_t<T>>
::min())};
398 template <std::
floating_po
int R>
402 return std::ldexp(x, e);
406 template <std::
floating_po
int R>
413 template <std::
floating_po
int U>
416 return std::max(std::abs(x.real()), std::abs(x.imag()));
420 template <std::
floating_po
int U>
424 return {std::ldexp(x.real(), e), std::ldexp(x.imag(), e)};
433 template <
typename T,
441 for (std::size_t i {0}; i < count; ++i) {
445 const auto f {factor(i)};
463 template <
typename T>
477 template <
typename T>
493 template <
typename T>
499 for (std::size_t i {0}; i < count; ++i) {
500 largest = std::max(largest,
static_cast<real
>(std::abs(x[i])));
506 for (std::size_t i {0}; i < count; ++i) {
507 const real
ratio {
static_cast<real
>(std::abs(x[i])) / largest};
510 return largest * std::sqrt(
sum);
522 template <
typename T>
528 return std::sqrt(
plain);
534 template <
typename T>
553 const auto*
const parts {
reinterpret_cast<const double*
>(x)};
558 template <
typename T>
574 constexpr double low {0x1p-500};
575 constexpr double high {0x1p500};
576 const double larger {std::max(std::abs(a), std::abs(b))};
577 if (larger > low && larger < high) {
578 return std::sqrt((a * a) + (b * b));
580 return std::hypot(a, b);
610 template <
typename T>
613 return std::isfinite(x);
617 template <
typename U>
620 return std::isfinite(x.real()) && std::isfinite(x.imag());
627 template <
typename T>
631 for (std::size_t i {0}; i < a.
rows(); ++i) {
632 for (std::size_t j {0}; j < a.
cols(); ++j) {
634 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
645 template <
typename T>
667 std::atomic<bool> finite {
true};
671 finite.store(
false, std::memory_order_relaxed);
674 return finite.load(std::memory_order_relaxed);
682 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
690 const auto*
const parts {
reinterpret_cast<const double*
>(std::to_address(a.begin()))};
692 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
698 template <
typename T>
701 for (std::size_t i {0}; i < a.
rows(); ++i) {
702 bool finite {std::isfinite(
real_part(a(i, i)))};
703 for (std::size_t j {0}; j < i; ++j) {
718 template <
typename T>
723 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
736 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
744 const auto*
const parts {
reinterpret_cast<const double*
>(std::to_address(a.begin()))};
746 throw non_finite_error(std::string {what} +
": the matrix holds an infinite or NaN entry");
755 template <
typename T>
762 for (std::size_t t {0}; t < terms; ++t) {
771 const double* columns,
784 template <
typename T>
785 inline constexpr bool real_rows {std::is_same_v<T, double> || std::is_same_v<T, float>};
819 if (a.cols() !=
n_) {
823 lu_ = std::move(a).elements();
825 for (std::size_t i {0}; i <
n_; ++i) {
841 throw dimension_error(
"solve: right-hand side size differs from the matrix");
847 for (std::size_t i {0}; i <
n_; ++i) {
849 for (std::size_t j {0}; j < i; ++j) {
854 for (std::size_t i {
n_}; i-- > 0;) {
856 for (std::size_t j {i + 1}; j <
n_; ++j) {
882 return {
T {0}, -std::numeric_limits<double>::infinity()};
886 for (std::size_t i {0}; i <
n_; ++i) {
887 const T pivot {
lu_[(i *
n_) + i]};
889 logarithm += std::log(
static_cast<double>(std::abs(pivot)));
917 const std::size_t n {
n_};
918 T*
const at {rows.data()};
919 const std::size_t*
const to {
pivots_.data()};
924 std::copy_n(at + (r * n), n,
held.data());
925 for (std::size_t i {0}; i < n; ++i) {
926 at[(r * n) +
to[i]] =
held[i];
930 return matrix<T> {n, n, std::move(rows)};
946 const std::size_t n {
n_};
951 std::fill_n(rows + (r * n), n,
T {});
952 rows[(r * n) + r] =
T {1};
973 throw dimension_error(
"solve: right-hand side row count differs from the matrix");
978 const std::size_t cols {b.
cols()};
980 for (std::size_t i {0}; i <
n_; ++i) {
981 for (std::size_t c {0}; c < cols; ++c) {
982 rows[(i * cols) + c] = b(
pivots_[i], c);
999 if (b.rows() !=
n_) {
1000 throw dimension_error(
"solve: right-hand side row count differs from the matrix");
1005 const std::size_t cols {b.cols()};
1006 buffer<T> rows {std::move(b).elements()};
1008 std::vector<bool> placed(
n_,
false);
1010 for (std::size_t start {0}; start <
n_; ++start) {
1011 if (placed[start] ||
pivots_[start] == start) {
1014 std::copy_n(rows.data() + (start * cols), cols,
held.data());
1015 std::size_t i {start};
1017 std::copy_n(rows.data() + (
from * cols), cols, rows.data() + (i * cols));
1020 std::copy_n(
held.data(), cols, rows.data() + (i * cols));
1077 bool lower =
false)
const
1085#ifdef NUMERICAL_X86_COMPILED
1098 const auto start {[
this,
slice,
slices, cols, lower](std::size_t s) {
1117#ifdef NUMERICAL_X86_COMPILED
1136 std::size_t cols)
const
1138 const auto n {
static_cast<double>(
n_)};
1139 const auto weight {[n](
double c) {
return (n * n * c) + (((n * n * n) - ((n - c) * (n - c) * (n - c))) / 3.0); }};
1140 const double target {
weight(
static_cast<double>(cols)) *
static_cast<double>(s) /
static_cast<double>(
slices)};
1141 std::size_t low {0};
1142 std::size_t high {cols};
1143 while (low < high) {
1144 const std::size_t
middle {low + ((high - low) / 2)};
1152 return std::min(cols, (low + 7) / 8 * 8);
1165 constexpr std::size_t width {64};
1166 const std::size_t chunks {(c1 -
c0 + width - 1) / width};
1168 const std::size_t end {std::min(
k0 +
block_,
n_)};
1169 const std::size_t
reach {lower ? std::min(end, c1) : c1};
1174 const std::size_t first {
c0 + (chunk * width)};
1175 const std::size_t
last {std::min(first + width,
reach)};
1176 for (std::size_t i {
k0 + 1}; i < end; ++i) {
1182 for (std::size_t
k1 {
n_};
k1 > 0;) {
1185 const std::size_t first {
c0 + (chunk * width)};
1186 const std::size_t
last {std::min(first + width, c1)};
1187 for (std::size_t i {
k1}; i-- >
k0;) {
1190 for (std::size_t c {first}; c <
last; ++c) {
1210 std::size_t cols)
const
1222 for (std::size_t i {
i0 + 1}; i <
i0 +
group; ++i) {
1226 for (std::size_t i {std::max<std::size_t>(
i0, 1)}; i <
n_; ++i) {
1234 const auto finish {[
this, &
y, cols](std::size_t i) {
1240 for (std::size_t c {0}; c < cols; ++c) {
1244 std::size_t
i1 {
n_};
1254 for (std::size_t i {
i1}; i-- >
top;) {
1263 return i & ~(
block_ - 1);
1275 std::size_t
last)
const
1280 y.data() + (
r0 * cols) + first, cols);
1289 std::size_t c1)
const
1291 out.resize((
r1 -
r0) * (c1 -
c0));
1292 for (std::size_t r {
r0}; r <
r1; ++r) {
1293 for (std::size_t c {
c0}; c < c1; ++c) {
1294 out[((r -
r0) * (c1 -
c0)) + (c -
c0)] = -
lu_[(r *
n_) + c];
1303 std::size_t c1)
const
1306 for (std::size_t r {
r0}; r <
r1; ++r) {
1307 for (std::size_t c {
c0}; c < c1; ++c) {
1308 out[((r -
r0) * (c1 -
c0)) + (c -
c0)] = -
lu_[(r *
n_) + c];
1335 const std::size_t end {std::min(
block_,
n_)};
1357 for (std::size_t
k0 {0}; end <
n_;) {
1358 const std::size_t next {std::min(end +
block_,
n_)};
1361 const std::size_t
right {
n_ - next};
1376 const std::size_t width {std::max(
block_, (
right + (2 * helpers) - 1) / (2 * helpers))};
1377 const std::size_t blocks {(
right + width - 1) / width};
1395 [&](std::size_t block) {
1396 const std::size_t first {next + (block * width)};
1397 const std::size_t
last {std::min(first + width,
n_)};
1406 for (std::size_t c {next}; c <
n_; ++c) {
1407 std::swap(
lu_[(a *
n_) + c],
lu_[(b *
n_) + c]);
1428 const std::size_t rows {
n_ -
k0};
1429 const std::size_t width {end -
k0};
1445 const std::size_t width {end -
k0};
1446#ifdef NUMERICAL_X86_COMPILED
1452 for (std::size_t j {0}; j < width; ++j) {
1453 for (std::size_t r {
r0}; r <
r1; ++r) {
1459 for (std::size_t j {0}; j < width; ++j) {
1460 for (std::size_t r {
r0}; r <
r1; ++r) {
1469 for (std::size_t r {0}; r < rows; ++r) {
1470 for (std::size_t j {0}; j < width; ++j) {
1500 for (std::size_t j {first}; j <
last; ++j) {
1502 std::size_t pivot {0};
1517 for (std::size_t c {0}; c < end -
k0; ++c) {
1518 std::swap(
panel[(c * rows) + j],
panel[(c * rows) + pivot]);
1525 for (std::size_t r {j + 1}; r < rows; ++r) {
1528 for (std::size_t c {j + 1}; c <
last; ++c) {
1535 const std::size_t
mid {first + ((
last - first) / 2)};
1537 for (std::size_t c {
mid}; c <
last; ++c) {
1539 for (std::size_t j {first}; j <
mid; ++j) {
1545 const std::size_t depth {
mid - first};
1547 for (std::size_t c {
mid}; c <
last; ++c) {
1548 for (std::size_t j {first}; j <
mid; ++j) {
1571 std::swap(
lu_[(a *
n_) + c],
lu_[(b *
n_) + c]);
1590 const std::size_t c0 {p * block_};
1591 const std::size_t c1 {
c0 +
block_};
1593 [](
const auto& swap, std::size_t
row) { return swap.first < row; })};
1594 for (
auto swap {first}; swap !=
left_swaps_.end(); ++swap) {
1595 std::swap_ranges(
lu_.data() + (swap->first *
n_) +
c0,
lu_.data() + (swap->first *
n_) + c1,
1596 lu_.data() + (swap->second *
n_) +
c0);
1608 constexpr std::size_t width {64};
1609 const std::size_t blocks {((n_ - end) + width - 1) / width};
1611 const std::size_t first {end + (block * width)};
1612 solve_columns(
k0, end, first, std::min(first + width, n_));
1623 for (std::size_t i {
k0 + 1}; i < end; ++i) {
1635 const std::size_t end {
k0 +
left.k};
1644 bool singular_ {
false};
1645 std::size_t swap_limit_ {n_};
1659 const double* x {std::to_address(m.
begin())};
1660 const std::size_t count {m.
rows() * m.
cols()};
1666 for (; i + 4 <= count; i += 4) {
1667 l0 = std::max(l0, std::abs(x[i]));
1668 l1 = std::max(l1, std::abs(x[i + 1]));
1669 l2 = std::max(l2, std::abs(x[i + 2]));
1670 l3 = std::max(l3, std::abs(x[i + 3]));
1672 for (; i < count; ++i) {
1673 l0 = std::max(l0, std::abs(x[i]));
1676 static_cast<void>(std::frexp(std::max(std::max(l0, l1), std::max(l2, l3)), &exponent));
1677 exponent = std::max(exponent, -1021);
1678 const double scale {std::ldexp(1.0, -exponent)};
1680 std::transform(m.
begin(), m.
end(), out.begin(), [scale](
double v) { return static_cast<float>(v * scale); });
1691 return std::numeric_limits<double>::quiet_NaN();
1694 for (std::size_t j {0}; j < x.
cols(); ++j) {
1695 double x_norm {0.0};
1696 double r_norm {0.0};
1697 for (std::size_t i {0}; i < x.
rows(); ++i) {
1698 x_norm = std::max(x_norm, std::abs(x(i, j)));
1699 r_norm = std::max(r_norm, std::abs(r(i, j)));
1701 ratio = std::max(ratio, r_norm / x_norm);
1726 double* reciprocal_condition =
nullptr)
1728 const std::size_t n {a.
rows()};
1729 double a_norm {0.0};
1730 for (
auto row = a.
begin(); row != a.
end(); row +=
static_cast<std::ptrdiff_t
>(n)) {
1731 std::array<double, 4> sums {};
1732 for (std::size_t j {0}; j < n; ++j) {
1733 sums[j % 4] += std::abs(row[
static_cast<std::ptrdiff_t
>(j)]);
1735 a_norm = std::max(a_norm, (sums[0] + sums[1]) + (sums[2] + sums[3]));
1738 return std::nullopt;
1740 const double bound {a_norm * (std::numeric_limits<double>::epsilon() / 2.0) * std::sqrt(
static_cast<double>(n))};
1743 if (factored.singular()) {
1744 return std::nullopt;
1746 const auto solved = [&factored, a_exponent](std::pair<matrix<float>,
int> rhs) {
1747 const matrix<float> y {factored.solve(std::move(rhs.first))};
1748 const double up {std::ldexp(1.0, rhs.second)};
1749 const double down {std::ldexp(1.0, -a_exponent)};
1751 std::transform(y.begin(), y.end(), out.begin(), [up, down](
float v) { return (static_cast<double>(v) * up) * down; });
1757 double previous {std::numeric_limits<double>::infinity()};
1758 while (!(ratio <= bound)) {
1759 if (!(ratio <= previous / 8.0)) {
1760 return std::nullopt;
1768 std::vector<double> sums(n, 0.0);
1769 for (std::size_t i {0}; i < n; ++i) {
1770 for (std::size_t j {0}; j < n; ++j) {
1771 sums[j] += std::abs(a(i, j));
1774 *
reciprocal_condition = factored.reciprocal_condition(std::ldexp(*std::max_element(sums.begin(), sums.end()), -a_exponent));
1861 template <
typename T>
1874 const std::size_t width {last - first};
1876 std::array<T, triangular_block> terms {};
1877 for (std::size_t step {0}; step < width; ++step) {
1878 const std::size_t i {lower ? first + step : last - 1 - step};
1879 T*
const row {x + (i * ldx)};
1880 const std::size_t from {lower ? first : i + 1};
1881 const std::size_t to {lower ? i : last};
1882 const T* f {a + (i * n) + from};
1884 for (std::size_t j {from}; j < to; ++j) {
1885 terms[j - from] = a[(j * n) + i];
1892 for (std::size_t c {0}; c < k; ++c) {
1900 const std::size_t solved_first {lower ? first : middle};
1901 const std::size_t solved_last {lower ? middle : last};
1902 const std::size_t other_first {lower ? middle : first};
1903 const std::size_t other_last {lower ? last : middle};
1904 triangular_halves(a, n, lower, transposed, unit, x, ldx, k, solved_first, solved_last, minus);
1905 const std::size_t depth {solved_last - solved_first};
1906 for (std::size_t r {0}; r < depth; ++r) {
1907 for (std::size_t c {0}; c < k; ++c) {
1908 minus[(r * k) + c] = -x[((solved_first + r) * ldx) + c];
1911 const std::size_t rows {other_last - other_first};
1913 gemm_at(rows, k, depth, a + (solved_first * n) + other_first, n, minus, k, x + (other_first * ldx), ldx);
1916 gemm(rows, k, depth, a + (other_first * n) + solved_first, n, minus, k, x + (other_first * ldx), ldx);
1918 triangular_halves(a, n, lower, transposed, unit, x, ldx, k, other_first, other_last, minus);
1929 template <
typename T>
1938 if (k == 1 && !transposed) {
1939 for (std::size_t step {0}; step < n; ++step) {
1940 const std::size_t i {lower ? step : n - 1 - step};
1941 const std::size_t from {lower ? 0 : i + 1};
1942 const std::size_t count {lower ? i : n - i - 1};
1943 const T value {x[i] -
dot_product(a + (i * n) + from, x + from, count)};
1944 x[i] = unit ? value : value / a[(i * n) + i];
1949 for (std::size_t step {0}; step < n; ++step) {
1950 const std::size_t j {lower ? n - 1 - step : step};
1952 x[j] /= a[(j * n) + j];
1954 const std::size_t from {lower ? 0 : j + 1};
1955 subtract_product(x + from, a + (j * n) + from, x[j], lower ? j : n - j - 1);
1959 const bool m_lower {lower != transposed};
1962 triangular_halves(a, n, m_lower, transposed, unit, x, k, k, 0, n, minus.data());
1971 triangular_halves(a, n, m_lower, transposed, unit, x + start, k, count, 0, n, minus.data());
1979 template <
typename T>
1983 return std::all_of(x, x + count, [](
const T& value) {
return is_finite_entry(value); });
2002 template <
typename T>
2007 for (std::size_t i {0}; i < n; ++i) {
2008 const T*
const row {a + (i * n)};
2022 template <
typename T>
2030 throw non_finite_error(
"solve_triangular: the matrix holds an infinite or NaN entry");
2033 throw non_finite_error(
"solve_triangular: the right-hand side holds an infinite or NaN entry");
2041 template <
typename T>
2050 for (std::size_t i {0}; i < n && !unit_diagonal; ++i) {
2051 if (a[(i * n) + i] == T {}) {
2052 throw singular_matrix_error(
"singular matrix: resolution failed at diagonal " + std::to_string(i + 1));
2055 const bool adjoint {op == triangular_op::adjoint};
2057 std::transform(x, x + (n * k), x, [](
const T& value) {
return conj_of(value); });
2059 triangular_rows(a, n, lower, op != triangular_op::none, unit_diagonal, x, k);
2061 std::transform(x, x + (n * k), x, [](
const T& value) {
return conj_of(value); });
2070 template <
typename T>
2085 template <std::
floating_po
int R>
2089 sign = x >= R {} ? 1 : -1;
2090 return static_cast<R
>(sign);
2095 template <std::
floating_po
int R>
2100 const R modulus {std::abs(x)};
2101 return modulus > std::numeric_limits<R>::min() ? x / modulus : std::complex<R> {1};
2105 template <std::
floating_po
int R>
2109 return (x >= R {} ? 1 : -1) == sign;
2113 template <std::
floating_po
int R>
2122 template <std::
floating_po
int R>
2126 return last == std::abs(largest);
2130 template <std::
floating_po
int R>
2132 std::complex<R> largest)
noexcept
2134 return std::abs(last) == std::abs(largest);
2149 template <
typename T>
2151 const std::function<
void(T*,
bool)>& apply)
2153 constexpr std::size_t most_climbs {5};
2154 buffer<T> x(n, T {
static_cast<decltype(std::abs(T {}))
>(1.0 /
static_cast<double>(n))});
2155 std::vector<int> signs(n, 0);
2156 const auto product = [&](
bool adjoint) {
2160 const auto sum = [&] {
2162 for (
const T& value : x) {
2163 total +=
static_cast<double>(std::abs(value));
2167 const auto largest_at = [&] {
2169 for (std::size_t i {1}; i < n; ++i) {
2170 if (std::abs(x[i]) > std::abs(x[at])) {
2176 const auto to_signs = [&] {
2177 for (std::size_t i {0}; i < n; ++i) {
2181 if (!product(
false)) {
2182 return std::numeric_limits<double>::infinity();
2185 return static_cast<double>(std::abs(x[0]));
2187 double estimate {
sum()};
2189 if (!product(
true)) {
2190 return std::numeric_limits<double>::infinity();
2192 std::size_t j {largest_at()};
2193 for (std::size_t climb {2};; ++climb) {
2194 std::fill(x.begin(), x.end(), T {});
2196 if (!product(
false)) {
2197 return std::numeric_limits<double>::infinity();
2199 const double previous {estimate};
2201 bool repeated {
true};
2202 for (std::size_t i {0}; i < n && repeated; ++i) {
2205 if (repeated || estimate <= previous) {
2209 if (!product(
true)) {
2210 return std::numeric_limits<double>::infinity();
2212 const std::size_t last {j};
2214 if (
climb_ends(x[last], x[j]) || climb >= most_climbs) {
2218 for (std::size_t i {0}; i < n; ++i) {
2219 const double magnitude {1.0 + (
static_cast<double>(i) /
static_cast<double>(n - 1))};
2220 x[i] = T {
static_cast<decltype(std::abs(T {}))
>(i % 2 == 0 ? magnitude : -magnitude)};
2222 if (!product(
false)) {
2223 return std::numeric_limits<double>::infinity();
2225 return std::max(estimate, 2.0 * (
sum() /
static_cast<double>(3 * n)));
2231 template <
typename T>
2234 const std::function<
void(T*,
bool)>& apply)
2242 return (1.0 / one_norm_estimate<T>(n, apply)) /
one_norm;
2250 template <
typename T>
2255 for (std::size_t i {0}; i < n; ++i) {
2256 if (lu[(i * n) + i] == T {}) {
2260 return reciprocal_condition<T>(n,
one_norm, [lu, n](T* x,
bool adjoint) {
2272 template <
typename T>
2278 return reciprocal_condition<T>(n,
one_norm, [factor, n, lower](T* x,
bool ) {
2289 template <
typename T>
2294 std::vector<double> sums(n, 0.0);
2295 for (std::size_t i {0}; i < n; ++i) {
2296 if (a[(i * n) + i] == T {}) {
2299 for (std::size_t j {lower ? 0 : i}; j <= (lower ? i : n - 1); ++j) {
2300 sums[j] +=
static_cast<double>(std::abs(a[(i * n) + j]));
2303 const double one_norm {n == 0 ? 0.0 : *std::max_element(sums.begin(), sums.end())};
2304 return reciprocal_condition<T>(n,
one_norm, [a, n, lower](T* x,
bool adjoint) {
2313 return detail::lu_reciprocal_condition(lu_.data(), n_, one_norm);
2327 [[nodiscard]]
double triangular_reciprocal_condition(
const matrix<T>& a,
2330 const std::size_t n {a.
rows()};
2331 if (a.
cols() != n) {
2332 throw dimension_error(
"triangular_reciprocal_condition: expected a square matrix");
2334 const T*
const at {std::to_address(a.
begin())};
2335 detail::require_finite_triangle(at, n, lower, at, 0);
2336 return detail::triangular_reciprocal_condition(at, n, lower);
2359 bool unit_diagonal =
false)
2361 const std::size_t n {a.
rows()};
2362 if (a.
cols() != n) {
2365 if (b.
rows() != n) {
2366 throw dimension_error(
"solve_triangular: right-hand side row count differs from the matrix");
2368 const std::size_t k {b.
cols()};
2370 detail::solve_triangular_in_place(std::to_address(a.
begin()), n, lower, op, unit_diagonal, x.data(), k);
2380 bool unit_diagonal =
false)
2383 return vector<T> {std::move(column).elements()};
2387 template <
typename T>
2399 template <
typename T>
2407 for (std::size_t i {0}; i < rows; ++i) {
2408 for (std::size_t j {0}; j < k; ++j) {
2409 l[(i * k) + j] = i == j ? T {1} : (j < i ? lu[(i * cols) + j] : T {});
2412 for (std::size_t i {0}; i < k; ++i) {
2413 for (std::size_t j {i}; j < cols; ++j) {
2414 u[(i * cols) + j] = lu[(i * cols) + j];
2428 template <
typename T>
2434 std::vector<std::size_t>& rows)
2437 for (std::size_t j {first}; j < last; ++j) {
2438 T*
const column {panel + (j * m)};
2439 std::size_t pivot {0};
2453 for (std::size_t c {0}; c < n; ++c) {
2454 std::swap(panel[(c * m) + j], panel[(c * m) + pivot]);
2456 std::swap(rows[j], rows[pivot]);
2459 for (std::size_t r {j + 1}; r < m; ++r) {
2462 for (std::size_t c {j + 1}; c < last; ++c) {
2463 T*
const target {panel + (c * m)};
2469 const std::size_t mid {first + ((last - first) / 2)};
2471 for (std::size_t c {mid}; c < last; ++c) {
2472 T*
const target {panel + (c * m)};
2473 for (std::size_t j {first}; j < mid; ++j) {
2474 subtract_product(target + j + 1, panel + (j * m) + j + 1, target[j], mid - (j + 1));
2478 const std::size_t depth {mid - first};
2479 buffer<T> minus_u((last - mid) * depth, T {});
2480 for (std::size_t c {mid}; c < last; ++c) {
2481 for (std::size_t j {first}; j < mid; ++j) {
2482 minus_u[((c - mid) * depth) + (j - first)] = -panel[(c * m) + j];
2485 gemm_rows(last - mid, m - mid, depth, minus_u.data(), depth, panel + (first * m) + mid, m, panel + (mid * m) + mid, m);
2505 template <
typename T>
2506 requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
2509 const std::size_t m {a.
rows()};
2510 const std::size_t n {a.
cols()};
2511 const std::size_t k {std::min(m, n)};
2512 detail::require_finite(a,
"LU decomposition");
2513 std::vector<std::size_t> identity(m);
2514 std::iota(identity.begin(), identity.end(), std::size_t {0});
2520 for (std::size_t i {0}; i < m; ++i) {
2521 std::copy_n(&a(i, 0), m, square.data() + (i * m));
2526 for (std::size_t i {0}; i < m; ++i) {
2527 std::copy_n(&lu(i, 0), m, combined.data() + (i * n));
2531 for (std::size_t i {0}; i < m; ++i) {
2532 std::copy_n(&a(f.pivots()[i], m), n - m, rest.data() + (i * (n - m)));
2534 detail::solve_triangular_in_place(std::to_address(lu.begin()), m,
true, triangular_op::none,
true, rest.data(), n - m);
2535 for (std::size_t i {0}; i < m; ++i) {
2536 std::copy_n(rest.data() + (i * (n - m)), n - m, combined.data() + (i * n) + m);
2539 auto [l, u] {detail::split_lu(combined.data(), m, n, k)};
2540 return {f.pivots(), std::move(l), std::move(u)};
2542 if (m <= detail::lu_tall_ratio * n) {
2544 for (std::size_t i {0}; i < m; ++i) {
2545 std::copy_n(&a(i, 0), n, padded.data() + (i * m));
2549 auto [l, u] {detail::split_lu(std::to_address(lu.begin()), m, m, k)};
2551 for (std::size_t i {0}; i < k; ++i) {
2552 std::copy_n(&u(i, 0), n, top.data() + (i * n));
2554 return {f.pivots(), std::move(l),
matrix<T> {k, n, std::move(top)}};
2557 for (std::size_t i {0}; i < m; ++i) {
2558 for (std::size_t j {0}; j < n; ++j) {
2559 panel[(j * m) + i] = a(i, j);
2562 detail::tall_lu_columns(panel.data(), m, n, 0, n, identity);
2564 for (std::size_t i {0}; i < m; ++i) {
2565 for (std::size_t j {0}; j < n; ++j) {
2566 combined[(i * n) + j] = panel[(j * m) + i];
2569 auto [l, u] {detail::split_lu(combined.data(), m, n, k)};
2570 return {std::move(identity), std::move(l), std::move(u)};
2580 std::size_t order = 0)
2581 : tagged(message), order_ {order}
2585 [[nodiscard]] std::size_t
order() const noexcept
2630 if (a.cols() != n_) {
2631 throw dimension_error(
"Cholesky decomposition requires a square matrix");
2633 detail::require_finite_lower(a,
"Cholesky decomposition");
2634 lower_ = std::move(a).elements();
2647 return matrix<T> {n_, n_, std::move(lower_)};
2658 if (b.
size() != n_) {
2659 throw dimension_error(
"solve: right-hand side size differs from the matrix");
2662 for (std::size_t i {0}; i < n_; ++i) {
2664 for (std::size_t k {0}; k < i; ++k) {
2665 sum -= lower_[(i * n_) + k] * y[k];
2667 y[i] = detail::over_real_diagonal(
sum, lower_[(i * n_) + i]);
2670 for (std::size_t i {n_}; i-- > 0;) {
2672 for (std::size_t k {i + 1}; k < n_; ++k) {
2673 sum -= detail::conj_of(lower_[(k * n_) + i]) * x[k];
2675 x[i] = detail::over_real_diagonal(
sum, lower_[(i * n_) + i]);
2690 if (b.
rows() != n_) {
2691 throw dimension_error(
"solve: right-hand side row count differs from the matrix");
2693 const std::size_t cols {b.
cols()};
2695 const std::size_t slices {std::max<std::size_t>(1, std::min(
max_threads(), cols / 8))};
2696 const std::size_t slice {(cols + slices - 1) / slices};
2697 detail::parallel_for(slices, n_ * n_ * slice, [&](std::size_t s) {
2698 const std::size_t c0 {s * slice};
2699 const std::size_t c1 {std::min(cols, c0 + slice)};
2700 for (std::size_t i {0}; i < n_; ++i) {
2701 T*
const row {x.data() + (i * cols)};
2702 for (std::size_t k {0}; k < i; ++k) {
2703 const T l {lower_[(i * n_) + k]};
2704 const T*
const above {x.data() + (k * cols)};
2705 for (std::size_t c {c0}; c < c1; ++c) {
2706 row[c] -= l * above[c];
2709 for (std::size_t c {c0}; c < c1; ++c) {
2710 row[c] = detail::over_real_diagonal(row[c], lower_[(i * n_) + i]);
2713 for (std::size_t i {n_}; i-- > 0;) {
2714 T*
const row {x.data() + (i * cols)};
2715 for (std::size_t k {i + 1}; k < n_; ++k) {
2716 const T l {detail::conj_of(lower_[(k * n_) + i])};
2717 const T*
const below {x.data() + (k * cols)};
2718 for (std::size_t c {c0}; c < c1; ++c) {
2719 row[c] -= l * below[c];
2722 for (std::size_t c {c0}; c < c1; ++c) {
2723 row[c] = detail::over_real_diagonal(row[c], lower_[(i * n_) + i]);
2727 return matrix<T> {n_, cols, std::move(x)};
2735 return detail::scaled_product(
static_cast<T
>(1), 2 * n_, [
this](std::size_t k) {
return lower_[((k / 2) * n_) + (k / 2)]; });
2747 return detail::cholesky_reciprocal_condition(lower_.data(), n_,
true, one_norm);
2760 for (std::size_t k0 {0}; k0 < n_; k0 += block_) {
2761 const std::size_t end {std::min(k0 + block_, n_)};
2763 for (; end - k0 >= detail::cholesky_together_width && i + detail::cholesky_diagonal_rows <= end; i += detail::cholesky_diagonal_rows) {
2764 factor_rows_together(i, k0);
2765 for (std::size_t r {0}; r < detail::cholesky_diagonal_rows; ++r) {
2766 factor_row(i + r, k0, i, i + r + 1);
2769 for (; i < end; ++i) {
2770 factor_row(i, k0, k0, i + 1);
2773 minus_adjoint.resize((end - k0) * (n_ - end));
2774 factor_rows_below(k0, end, minus_adjoint);
2775 update_trailing(k0, end, minus_adjoint, packing);
2778 T*
const rows {lower_.data()};
2779 const std::size_t n {n_};
2781 detail::parallel_for((n + detail::zeroed_rows - 1) / detail::zeroed_rows, detail::memory_element_weight * detail::zeroed_rows * n / 2, [rows, n](std::size_t band) {
2782 for (std::size_t i {band * detail::zeroed_rows}; i < std::min(n, (band + 1) * detail::zeroed_rows); ++i) {
2783 std::fill(rows + (i * n) + i + 1, rows + ((i + 1) * n), T {});
2798 std::array<T, detail::cholesky_diagonal_rows> sums {};
2799 for (std::size_t j {k0}; j < i; ++j) {
2800 const T*
const above {lower_.data() + (j * n_)};
2802 for (std::size_t r {0}; r < detail::cholesky_diagonal_rows; ++r) {
2803 sums[r] = lower_[((i + r) * n_) + j];
2805 for (std::size_t k {k0}; k < j; ++k) {
2806 const T other {detail::conj_of(above[k])};
2808 for (std::size_t r {0}; r < detail::cholesky_diagonal_rows; ++r) {
2809 sums[r] -= lower_[((i + r) * n_) + k] * other;
2813 for (std::size_t r {0}; r < detail::cholesky_diagonal_rows; ++r) {
2814 lower_[((i + r) * n_) + j] = detail::over_real_diagonal(sums[r], above[j]);
2829 for (std::size_t j {first}; j < last; ++j) {
2830 T
sum {lower_[(i * n_) + j]};
2831 for (std::size_t k {k0}; k < j; ++k) {
2832 sum -= lower_[(i * n_) + k] * detail::conj_of(lower_[(j * n_) + k]);
2839 lower_[(i * n_) + i] = detail::from_carried<T>(std::sqrt(
diagonal));
2842 lower_[(i * n_) + j] = detail::over_real_diagonal(
sum, lower_[(j * n_) + j]);
2863 const std::size_t width {end - k0};
2864 const std::size_t chunks {((n_ - end) + detail::cholesky_rows - 1) / detail::cholesky_rows};
2865 detail::parallel_for(chunks, detail::cholesky_rows * width * width / 2, [&](std::size_t chunk) {
2866 const std::size_t first {end + (chunk * detail::cholesky_rows)};
2867 const std::size_t height {std::min(detail::cholesky_rows, n_ - first)};
2869 for (std::size_t r {0}; r < height; ++r) {
2870 for (std::size_t j {0}; j < width; ++j) {
2871 panel[(j * height) + r] = lower_[((first + r) * n_) + k0 + j];
2874 constexpr std::size_t sub {16};
2876 for (std::size_t s0 {0}; s0 < width; s0 += sub) {
2877 const std::size_t s1 {std::min(s0 + sub, width)};
2879 minus_conj.resize((s1 - s0) * s0);
2880 for (std::size_t j {s0}; j < s1; ++j) {
2881 for (std::size_t k {0}; k < s0; ++k) {
2882 minus_conj[((j - s0) * s0) + k] = -detail::conj_of(lower_[((k0 + j) * n_) + k0 + k]);
2888 detail::gemm_rows(s1 - s0, height, s0, minus_conj.data(), s0, panel.data(), height, panel.data() + (s0 * height), height);
2890 for (std::size_t j {s0}; j < s1; ++j) {
2891 T*
const column {panel.data() + (j * height)};
2892 detail::subtract_panel_columns(column, panel.data() + (s0 * height), height, lower_.data() + ((k0 + j) * n_) + k0 + s0, j - s0);
2893 const T pivot {lower_[((k0 + j) * n_) + k0 + j]};
2894 for (std::size_t r {0}; r < height; ++r) {
2895 column[r] = detail::over_real_diagonal(column[r], pivot);
2899 const std::size_t below {n_ - end};
2900#ifdef NUMERICAL_X86_COMPILED
2904 for (std::size_t r {0}; r < height; ++r) {
2905 for (std::size_t j {0}; j < width; ++j) {
2906 lower_[((first + r) * n_) + k0 + j] = panel[(j * height) + r];
2909 for (std::size_t j {0}; j < width; ++j) {
2910 const T*
const from {panel.data() + (j * height)};
2911 T*
const to {minus_adjoint.data() + (j * below) + (first - end)};
2912 for (std::size_t r {0}; r < height; ++r) {
2913 to[r] = -detail::conj_of(from[r]);
2917 for (std::size_t r {0}; r < height; ++r) {
2918 for (std::size_t j {0}; j < width; ++j) {
2919 const T value {panel[(j * height) + r]};
2920 lower_[((first + r) * n_) + k0 + j] = value;
2921 minus_adjoint[(j * below) + (first - end + r)] = -detail::conj_of(value);
2944 const std::size_t rows {n_ - end};
2945 const std::size_t depth {end - k0};
2946#ifdef NUMERICAL_X86_COMPILED
2953 if constexpr (std::is_same_v<T, double> || std::is_same_v<T, float>) {
2954 if (depth >= detail::gemm_min_depth && rows * rows >= ((detail::gemm_packed_threshold + depth) - 1) / depth) {
2955 detail::gemm_triangle<detail::a_rows, detail::b_rows>(rows, depth, lower_.data() + (end * n_) + k0, n_, minus_adjoint.data(), rows,
2956 lower_.data() + (end * n_) + end, n_,
true);
2961 const std::size_t step {std::max(block_, detail::cholesky_update_columns)};
2964 const bool shared {rows > 2 * detail::cholesky_update_rows};
2965 const T*
const l21 {lower_.data() + (end * n_) + k0};
2967 : detail::read_in_place(rows, depth, l21, n_)};
2968 const std::size_t granule {std::max<std::size_t>(1, left.granule)};
2969 const std::size_t height {std::max(granule, detail::cholesky_update_rows / granule * granule)};
2970 std::vector<std::pair<std::size_t, std::size_t>> tiles;
2971 for (std::size_t jb {0}; jb < rows; jb += step) {
2972 for (std::size_t r0 {jb / granule * granule}; r0 < rows; r0 += height) {
2973 tiles.emplace_back(jb, r0);
2976 detail::parallel_for(tiles.size(), height * step * depth / detail::gemm_kernel_speedup, [&](std::size_t t) {
2977 const auto [jb, r0] {tiles[t]};
2978 detail::gemm_with(detail::left_rows(left, r0, std::min(height, rows - r0)), std::min(step, rows - jb),
2979 minus_adjoint.data() + jb, rows, lower_.data() + ((end + r0) * n_) + end + jb, n_);
2984 std::size_t block_ {detail::cholesky_block_for(n_)};
2999 template <
typename T>
3020 template <
typename T>
3028 constexpr std::size_t width {64};
3029 const std::size_t span {cols - from};
3030 parallel_for((span + width - 1) / width, 2 * v.size() * width, [&](std::size_t chunk) {
3031 const std::size_t start {from + (chunk * width)};
3032 const std::size_t count {std::min(width, cols - start)};
3033 buffer<T> w(count, T {});
3034 for (std::size_t i {0}; i < v.size(); ++i) {
3035 const T weight {
conj_of(v[i])};
3036 const T* row {a.data() + ((first + i) * cols) + start};
3039 for (std::size_t i {0}; i < v.size(); ++i) {
3040 const T scale {s * v[i]};
3041 T* row {a.data() + ((first + i) * cols) + start};
3048 template <
typename T>
3063 template <
typename T>
3068 const std::vector<T>* taus =
nullptr)
3071 const std::size_t b {block.width};
3072 block.v.assign(block.height * b, T {});
3073 block.t.assign(b * b, T {});
3074 for (std::size_t j {0}; j < b; ++j) {
3075 const buffer<T>& v {reflectors[k0 + j]};
3076 for (std::size_t r {0}; r < v.size(); ++r) {
3077 block.v[((j + r) * b) + j] = v[r];
3081 buffer<T> v_adjoint(b * block.height, T {});
3082 for (std::size_t r {0}; r < block.height; ++r) {
3083 for (std::size_t j {0}; j < b; ++j) {
3084 v_adjoint[(j * block.height) + r] =
conj_of(block.v[(r * b) + j]);
3088 gemm(b, b, block.height, v_adjoint.data(), block.height, block.v.data(), b, gram.data(), b);
3089 for (std::size_t j {0}; j < b; ++j) {
3090 if (reflectors[k0 + j].empty()) {
3093 const T tau {taus ==
nullptr ?
static_cast<T
>(2) : (*taus)[k0 + j]};
3094 for (std::size_t i {0}; i < j; ++i) {
3096 for (std::size_t p {i}; p < j; ++p) {
3097 sum += block.t[(i * b) + p] * gram[(p * b) + j];
3099 block.t[(i * b) + j] = -tau *
sum;
3101 block.t[(j * b) + j] = tau;
3111 template <
typename T>
3119 const std::size_t b {block.
width};
3120 const std::size_t h {block.
height};
3121 const std::size_t w {to - from};
3124 for (std::size_t r {0}; r < h; ++r) {
3125 for (std::size_t j {0}; j < b; ++j) {
3126 v_adjoint[(j * h) + r] =
conj_of(block.
v[(r * b) + j]);
3127 minus_v[(r * b) + j] = -block.
v[(r * b) + j];
3130 T* top {a.data() + (block.
first * cols) + from};
3132 gemm(b, w, h, v_adjoint.data(), h, top, cols, projection.data(), w);
3134 for (std::size_t i {0}; i < b; ++i) {
3135 for (std::size_t p {0}; p < b; ++p) {
3136 const T factor {
adjoint ?
conj_of(block.
t[(p * b) + i]) : block.
t[(i * b) + p]};
3137 if (factor == T {}) {
3143 gemm(h, w, b, minus_v.data(), b,
scaled.data(), w, top, cols);
3154 template <
typename T>
3160 bool adjoint =
false)
3162 const std::size_t b {block.
width};
3163 const std::size_t h {block.
height};
3164 const std::size_t r {to - from};
3165 const auto v_conjugate {std::make_unique_for_overwrite<T[]>(h * b)};
3166 const auto minus_v_t {std::make_unique_for_overwrite<T[]>(b * h)};
3167 const auto t_transposed {std::make_unique_for_overwrite<T[]>(b * b)};
3168 for (std::size_t row {0}; row < h; ++row) {
3169 for (std::size_t j {0}; j < b; ++j) {
3170 v_conjugate[(row * b) + j] =
conj_of(block.
v[(row * b) + j]);
3171 minus_v_t[(j * h) + row] = -block.
v[(row * b) + j];
3174 for (std::size_t i {0}; i < b; ++i) {
3175 for (std::size_t p {0}; p < b; ++p) {
3176 t_transposed[(p * b) + i] =
adjoint ?
conj_of(block.
t[(p * b) + i]) : block.
t[(i * b) + p];
3179 T* left {at.data() + (from * cols) + block.
first};
3181 gemm(r, b, h, left, cols, v_conjugate.get(), b, projection.data(), b);
3183 gemm(r, b, b, projection.data(), b, t_transposed.get(), b,
scaled.data(), b);
3184 gemm(r, h, b,
scaled.data(), b, minus_v_t.get(), h, left, cols);
3188 template <
typename T>
3189 requires std::is_floating_point_v<T>
3198 template <
typename T>
3213 template <
typename T>
3217 const T alpha {w[0]};
3219 const T tau {(detail::from_carried<T>(beta) - alpha) / detail::from_carried<T>(beta)};
3220 const T scale {T {1} / (alpha - detail::from_carried<T>(beta))};
3222 for (std::size_t r {1}; r < w.size(); ++r) {
3225 return {detail::from_carried<T>(beta / factor), tau};
3233 template <
typename T>
3242 for (std::size_t j {from}; j < to; ++j) {
3243 T*
const column {panel + (j * height) + first};
3265 template <
typename T>
3270 std::vector<T>& taus,
3274 for (std::size_t k {k0}; k < k1; ++k) {
3275 const std::size_t c {k - k0};
3276 T*
const x {panel + (c * ld) + (k - top)};
3278 const T alpha {w[0]};
3279 if (
scaled_norm(w.data() + 1, w.size() - 1) == 0 && alpha == detail::from_carried<T>(detail::real_part(alpha))) {
3285 std::copy(w.begin() + 1, w.end(), x + 1);
3286 reflectors[k] = std::move(w);
3292 template <
typename T>
3322 template <
typename T>
3326 bool reflectors =
true)
3328 const std::size_t depth {std::min(rows, cols)};
3329 std::vector<buffer<T>> reflections(depth);
3330 std::vector<T> taus(depth, T {});
3331 std::vector<reflector_block<T>> blocks;
3336 if (reflectors || std::min(
qr_block, depth) < cols) {
3339 for (std::size_t k1 {std::min(
qr_block, depth)}; k1 < cols;) {
3344 const std::size_t n1 {std::min(k1 +
qr_block, depth)};
3348 factor_qr_panel(columns.data() + (k1 * rows), rows, 0, reflections, taus, k1, n1);
3349 if (reflectors || n1 < cols) {
3357 const std::size_t rest {cols - n1};
3358 const std::size_t slice {std::max(
qr_update_slice, (rest + threads - 2) / (threads - 1))};
3359 const std::size_t slices {(rest + slice - 1) / slice};
3365 factor_qr_panel(columns.data() + (k1 * rows), rows, 0, reflections, taus, k1, n1);
3366 if (reflectors || n1 < cols) {
3371 const std::size_t from {n1 + ((task - 1) * slice)};
3374 if (reflectors || n1 < cols) {
3375 blocks.push_back(std::move(next));
3388 template <
typename T>
3399 to[(j * rows) + i] = from[(i * cols) + j];
3411 template <
typename T>
3416 std::vector<T>& taus,
3420 const std::size_t height {rows - k0};
3421 const std::size_t width {k1 - k0};
3423 for (std::size_t i {0}; i < height; ++i) {
3424 for (std::size_t j {0}; j < width; ++j) {
3425 panel[(j * height) + i] = a[((k0 + i) * cols) + k0 + j];
3429 for (std::size_t i {0}; i < height; ++i) {
3430 for (std::size_t j {0}; j < width; ++j) {
3431 a[((k0 + i) * cols) + k0 + j] = panel[(j * height) + i];
3445 template <
typename T>
3450 bool reflectors =
true)
3452 const std::size_t depth {std::min(rows, cols)};
3453 std::vector<buffer<T>> reflections(depth);
3454 std::vector<T> taus(depth, T {});
3458 std::vector<reflector_block<T>> blocks;
3461 if (reflectors || std::min(
qr_block, depth) < cols) {
3465 for (std::size_t k1 {std::min(
qr_block, depth)}; depth > 0 && k1 < cols;) {
3470 const std::size_t n1 {std::min(k1 +
qr_block, depth)};
3475 if (reflectors || n1 < cols) {
3481 const std::size_t rest {cols - n1};
3482 const std::size_t slice {std::max(
qr_update_slice, (rest + threads - 2) / (threads - 1))};
3483 const std::size_t slices {(rest + slice - 1) / slice};
3490 if (reflectors || n1 < cols) {
3495 const std::size_t from {n1 + ((task - 1) * slice)};
3498 if (reflectors || n1 < cols) {
3499 blocks.push_back(std::move(next));
3503 for (std::size_t i {0}; r !=
nullptr && i < depth; ++i) {
3504 for (std::size_t j {i}; j < cols; ++j) {
3505 (*r)[(i * cols) + j] = a[(i * cols) + j];
3520 template <
typename T>
3524 bool reflectors =
true)
3526#ifdef NUMERICAL_X86_COMPILED
3527 const std::size_t depth {std::min(rows, cols)};
3535 out.r[(i * cols) + j] = i <= j ? columns[(j * rows) + i] : T {};
3555 template <
typename T>
3563#ifdef NUMERICAL_X86_COMPILED
3565 buffer<T>& qt {transposed ? out : formed};
3567 for (std::size_t c {0}; c < count; ++c) {
3568 qt[(c * rows) + first + c] = T {1};
3570 for (std::size_t b {blocks.size()}; b-- > 0;) {
3574 out.resize(rows * count);
3579 buffer<T>& q {transposed ? formed : out};
3581 for (std::size_t c {0}; c < count; ++c) {
3582 q[((first + c) * count) + c] = T {1};
3584 for (std::size_t b {blocks.size()}; b-- > 0;) {
3588 out.resize(count * rows);
3600 template <
typename T>
3603 [[maybe_unused]] std::size_t rows,
3606#ifdef NUMERICAL_X86_COMPILED
3609 for (std::size_t b {blocks.size()}; b-- > 0;) {
3614 for (std::size_t b {blocks.size()}; b-- > 0;) {
3637 template <
typename T>
3641 bool complete =
false)
3643 const std::size_t depth {std::min(rows, cols)};
3644 const std::size_t width {
complete ? rows : depth};
3649 const auto formed {[&](std::size_t first, std::size_t count) {
3651 form_q_into(columns, factors.blocks, rows, first, count,
false);
3654 thin_qr<T> out {.
q = formed(0, depth), .r = std::move(factors.r)};
3655 if (width > depth) {
3656 const buffer<T> rest {formed(depth, width - depth)};
3658 for (std::size_t i {0}; i < rows; ++i) {
3659 std::copy_n(out.q.data() + (i * depth), depth, whole.data() + (i * width));
3660 std::copy_n(rest.data() + (i * (width - depth)), width - depth, whole.data() + (i * width) + depth);
3662 out.q = std::move(whole);
3664 for (std::size_t k {0}; k < depth; ++k) {
3665 const T phase {
phase_of(out.r[(k * cols) + k])};
3666 for (std::size_t j {k}; j < cols; ++j) {
3667 out.r[(k * cols) + j] *=
conj_of(phase);
3669 for (std::size_t i {0}; i < rows; ++i) {
3670 out.q[(i * width) + k] *= phase;
3685 template <
typename T>
3690 const std::size_t depth {std::min(rows, cols)};
3692 for (std::size_t k {0}; k < depth; ++k) {
3693 const T phase {
phase_of(r[(k * cols) + k])};
3694 for (std::size_t j {k}; j < cols; ++j) {
3695 r[(k * cols) + j] *=
conj_of(phase);
3707 return largest * std::numeric_limits<double>::epsilon() *
static_cast<double>(std::max(rows, cols));
3745 std::size_t cols)
const noexcept
3750 return value_ < 0.0 ? detail::rank_tolerance(largest, rows, cols) : largest * value_;
3756 return absolute_ ?
rank_cutoff {std::ldexp(value_, -exponent),
true} : *
this;
3762 bool absolute) noexcept
3763 : value_(value), absolute_(absolute)
3768 if (!(value >= 0.0)) {
3769 throw argument_error(
"rank cutoff: a tolerance is non-negative");
3774 double value_ {-1.0};
3775 bool absolute_ {
false};
3808 qr_mode mode = qr_mode::reduced)
3820 qr_mode mode = qr_mode::reduced)
3821 : rows_(a.rows()), cols_(a.cols()), depth_(std::
min(rows_, cols_)),
3824 detail::require_finite(a,
"QR decomposition");
3825 detail::thin_qr<T> factors {detail::householder_qr(std::move(a).elements(), rows_, cols_, mode == qr_mode::complete)};
3826 q_ = std::move(factors.q);
3827 r_ = std::move(factors.r);
3828 r_.resize(width_ * cols_, T {});
3840 return matrix<T> {rows_, width_, std::move(q_)};
3852 return matrix<T> {width_, cols_, std::move(r_)};
3866 if (b.
size() != rows_) {
3867 throw dimension_error(
"solve: right-hand side size differs from the matrix");
3869 if (rows_ < cols_) {
3870 throw dimension_error(
"QR solve: the system is underdetermined (lstsq gives its minimum-norm solution)");
3872 double largest {0.0};
3873 for (std::size_t i {0}; i < cols_; ++i) {
3874 largest = std::max(largest,
static_cast<double>(detail::real_part(r_[(i * cols_) + i])));
3876 const double tolerance {detail::rank_tolerance(largest, rows_, cols_)};
3878 for (std::size_t i {0}; i < cols_; ++i) {
3879 if (detail::real_part(r_[(i * cols_) + i]) <= tolerance) {
3880 throw singular_matrix_error(
"QR solve: the matrix is rank-deficient (lstsq gives its minimum-norm solution)");
3883 for (std::size_t k {0}; k < rows_; ++k) {
3884 sum += detail::conj_of(q_[(k * width_) + i]) * b[k];
3889 for (std::size_t i {cols_}; i-- > 0;) {
3891 for (std::size_t j {i + 1}; j < cols_; ++j) {
3892 sum -= r_[(i * cols_) + j] * x[j];
3894 x[i] =
sum / r_[(i * cols_) + i];
3910 if (b.
rows() != rows_) {
3911 throw dimension_error(
"solve: right-hand side row count differs from the matrix");
3913 if (rows_ < cols_) {
3914 throw dimension_error(
"QR solve: the system is underdetermined (lstsq gives its minimum-norm solution)");
3916 double largest {0.0};
3917 for (std::size_t i {0}; i < cols_; ++i) {
3918 largest = std::max(largest,
static_cast<double>(detail::real_part(r_[(i * cols_) + i])));
3920 const double tolerance {detail::rank_tolerance(largest, rows_, cols_)};
3921 for (std::size_t i {0}; i < cols_; ++i) {
3922 if (detail::real_part(r_[(i * cols_) + i]) <= tolerance) {
3923 throw singular_matrix_error(
"QR solve: the matrix is rank-deficient (lstsq gives its minimum-norm solution)");
3926 const std::size_t sides {b.
cols()};
3928 for (std::size_t k {0}; k < rows_; ++k) {
3929 for (std::size_t i {0}; i < cols_; ++i) {
3930 q_adjoint[(i * rows_) + k] = detail::conj_of(q_[(k * width_) + i]);
3934 gemm(cols_, sides, rows_, q_adjoint.data(), rows_, std::to_address(b.
begin()), sides, x.data(), sides, detail::c_start::zero);
3935 for (std::size_t i {cols_}; i-- > 0;) {
3936 T*
const row {x.data() + (i * sides)};
3937 for (std::size_t j {i + 1}; j < cols_; ++j) {
3938 const T r {r_[(i * cols_) + j]};
3939 const T*
const below {x.data() + (j * sides)};
3940 for (std::size_t c {0}; c < sides; ++c) {
3941 row[c] -= r * below[c];
3944 for (std::size_t c {0}; c < sides; ++c) {
3945 row[c] /= r_[(i * cols_) + i];
3948 return matrix<T> {cols_, sides, std::move(x)};
3962 template <
typename T>
3979 [[nodiscard]]
inline std::complex<double>
adjoint_dot(
const std::complex<double>* x,
3980 const std::complex<double>* y,
3987 template <
typename T>
3991 double largest {0.0};
3992 for (std::size_t i {0}; i < count; ++i) {
3993 largest = std::max(largest, std::abs(x[i]));
3995 if (largest == 0.0) {
3999 for (std::size_t i {0}; i < count; ++i) {
4000 const double scaled {std::abs(x[i]) / largest};
4003 return largest * std::sqrt(
sum);
4015 template <
double_field T>
4026 qr_mode mode = qr_mode::reduced)
4028 const std::size_t m {a.
rows()};
4029 const std::size_t n {a.
cols()};
4030 const std::size_t k {std::min(m, n)};
4031 detail::require_finite(a,
"pivoted QR");
4033 for (std::size_t i {0}; i < m; ++i) {
4034 for (std::size_t j {0}; j < n; ++j) {
4035 w[(j * m) + i] = a(i, j);
4040 permutation_.resize(n);
4041 for (std::size_t j {0}; j < n; ++j) {
4042 permutation_[j] = j;
4043 current[j] = detail::contiguous_norm(w.data() + (j * m), m);
4044 reference[j] = current[j];
4046 const double tolerance {std::sqrt(std::numeric_limits<double>::epsilon())};
4047 std::vector<buffer<T>> reflectors(k);
4048 std::vector<T> taus(k);
4049 const std::size_t top {k > pivoted_qr_crossover ? k - pivoted_qr_crossover : 0};
4050 std::size_t start {0};
4051 while (start < top) {
4052 start += factor_block(w, m, n, start, std::min(pivoted_qr_block, top - start), current, reference, reflectors, taus);
4054 for (std::size_t step {start}; step < k; ++step) {
4055 const std::size_t pivot {
static_cast<std::size_t
>(std::max_element(current.begin() +
static_cast<std::ptrdiff_t
>(step), current.end()) - current.begin())};
4056 T*
const head {w.data() + (step * m)};
4057 if (pivot != step) {
4058 std::swap_ranges(head, head + m, w.data() + (pivot * m));
4059 std::swap(permutation_[step], permutation_[pivot]);
4060 std::swap(current[step], current[pivot]);
4061 std::swap(reference[step], reference[pivot]);
4066 const T alpha {v[0]};
4067 const bool identity {detail::scaled_norm(v.data() + 1, v.size() - 1) == 0 && alpha == detail::from_carried<T>(detail::real_part(alpha))};
4070 std::fill(v.begin(), v.end(), T {});
4074 const auto [beta, factor] {detail::larfg_in_place(v)};
4077 std::fill(head + step + 1, head + m, T {});
4079 for (std::size_t j {step + 1}; j < n; ++j) {
4080 T*
const column {w.data() + (j * m)};
4081 const T dot {detail::adjoint_dot(v.data(), column + step, m - step)};
4082 detail::subtract_product(column + step, detail::conj_of(tau) * dot, v.data(), m - step);
4083 if (current[j] != 0.0) {
4084 const double ratio {std::abs(column[step]) / current[j]};
4085 const double left {std::max(0.0, (1.0 + ratio) * (1.0 - ratio))};
4086 const double drift {left * (current[j] / reference[j]) * (current[j] / reference[j])};
4087 if (drift <= tolerance) {
4088 current[j] = detail::contiguous_norm(column + step + 1, m - step - 1);
4089 reference[j] = current[j];
4092 current[j] *= std::sqrt(left);
4096 reflectors[step] = std::move(v);
4099 const std::size_t rows {mode == qr_mode::complete ? m : k};
4101 for (std::size_t i {0}; i < rows; ++i) {
4102 for (std::size_t j {0}; j < n; ++j) {
4103 r[(i * n) + j] = w[(j * m) + i];
4106 std::vector<detail::reflector_block<T>> blocks;
4107 for (std::size_t k0 {0}; k0 < k; k0 += pivoted_qr_block) {
4108 blocks.push_back(detail::gather_reflectors(reflectors, k0, std::min(k0 + pivoted_qr_block, k), m, &taus));
4111 detail::form_q_into(q, blocks, m, 0, rows,
false);
4112 for (std::size_t i {0}; i < k; ++i) {
4113 const double modulus {std::abs(r[(i * n) + i])};
4114 if (modulus == 0.0) {
4117 const T phase {r[(i * n) + i] / T {modulus}};
4118 for (std::size_t j {i}; j < n; ++j) {
4119 r[(i * n) + j] *= detail::conj_of(phase);
4121 r[(i * n) + i] = T {modulus};
4122 for (std::size_t row {0}; row < m; ++row) {
4123 q[(row * rows) + i] *= phase;
4143 [[nodiscard]]
const std::vector<std::size_t>&
permutation() const noexcept
4145 return permutation_;
4150 static constexpr std::size_t pivoted_qr_block {32};
4151 static constexpr std::size_t pivoted_qr_crossover {128};
4152 static constexpr std::size_t pivoted_qr_band {16};
4169 std::vector<T>& taus)
4171 const double tolerance {std::sqrt(std::numeric_limits<double>::epsilon())};
4172 const std::size_t cols {n - start};
4173 buffer<T> f(cols * pivoted_qr_block, T {});
4174 buffer<T> coefficients(pivoted_qr_block);
4175 std::vector<std::size_t> deferred;
4176 std::size_t done {0};
4177 const auto row_of_f = [&f](std::size_t j) {
return f.data() + (j * pivoted_qr_block); };
4178 while (done < width && deferred.empty()) {
4179 const std::size_t kk {done};
4180 const std::size_t step {start + kk};
4181 const std::size_t pivot {
static_cast<std::size_t
>(std::max_element(current.begin() +
static_cast<std::ptrdiff_t
>(step), current.end()) - current.begin())};
4182 T*
const head {w.data() + (step * m)};
4183 if (pivot != step) {
4184 std::swap_ranges(head, head + m, w.data() + (pivot * m));
4185 std::swap_ranges(row_of_f(kk), row_of_f(kk) + kk, row_of_f(pivot - start));
4186 std::swap(permutation_[step], permutation_[pivot]);
4187 std::swap(current[step], current[pivot]);
4188 std::swap(reference[step], reference[pivot]);
4191 for (std::size_t t {0}; t < kk; ++t) {
4192 coefficients[t] = detail::conj_of(row_of_f(kk)[t]);
4194 detail::subtract_products(head + step, coefficients.data(), w.data() + (start * m) + step, m, kk, m - step);
4197 const T alpha {v[0]};
4198 const bool identity {detail::scaled_norm(v.data() + 1, v.size() - 1) == 0 && alpha == detail::from_carried<T>(detail::real_part(alpha))};
4202 std::fill(v.begin(), v.end(), T {});
4206 const auto [beta, factor] {detail::larfg_in_place(v)};
4210 std::copy(v.begin(), v.end(), head + step);
4211 const auto conjugate_dot = [&v, m, step](
const T* column) {
4212 return detail::adjoint_dot(column + step, v.data(), m - step);
4215 const std::size_t later {cols - (kk + 1)};
4216 detail::parallel_for((later + pivoted_qr_band - 1) / pivoted_qr_band, (m - step) * pivoted_qr_band, [&](std::size_t band) {
4217 const std::size_t first {kk + 1 + (band * pivoted_qr_band)};
4218 const std::size_t last {std::min(cols, first + pivoted_qr_band)};
4219 for (std::size_t j {first}; j < last; ++j) {
4220 row_of_f(j)[kk] = tau * conjugate_dot(w.data() + ((start + j) * m));
4223 for (std::size_t j {0}; j <= kk; ++j) {
4224 row_of_f(j)[kk] = T {};
4227 for (std::size_t t {0}; t < kk; ++t) {
4228 coefficients[t] = -tau * conjugate_dot(w.data() + ((start + t) * m));
4230 for (std::size_t j {0}; j < cols; ++j) {
4232 for (std::size_t t {0}; t < kk; ++t) {
4233 sum += row_of_f(j)[t] * coefficients[t];
4235 row_of_f(j)[kk] +=
sum;
4238 for (std::size_t j {kk + 1}; j < cols; ++j) {
4240 for (std::size_t t {0}; t <= kk; ++t) {
4241 sum += w[((start + t) * m) + step] * detail::conj_of(row_of_f(j)[t]);
4243 w[((start + j) * m) + step] -=
sum;
4245 for (std::size_t j {step + 1}; j < n; ++j) {
4246 if (current[j] != 0.0) {
4247 const double ratio {std::abs(w[(j * m) + step]) / current[j]};
4248 const double left {std::max(0.0, (1.0 + ratio) * (1.0 - ratio))};
4249 const double drift {left * (current[j] / reference[j]) * (current[j] / reference[j])};
4250 if (drift <= tolerance) {
4251 deferred.push_back(j);
4254 current[j] *= std::sqrt(left);
4259 reflectors[step] = std::move(v);
4263 const std::size_t below {start + done};
4264 const std::size_t right {cols - done};
4265 detail::parallel_for((right + pivoted_qr_band - 1) / pivoted_qr_band, (m - below) * done * pivoted_qr_band, [&](std::size_t band) {
4266 std::array<T, pivoted_qr_block> terms {};
4267 const std::size_t first {done + (band * pivoted_qr_band)};
4268 const std::size_t last {std::min(cols, first + pivoted_qr_band)};
4269 for (std::size_t j {first}; j < last; ++j) {
4270 for (std::size_t t {0}; t < done; ++t) {
4271 terms[t] = detail::conj_of(row_of_f(j)[t]);
4273 detail::subtract_products(w.data() + ((start + j) * m) + below, terms.data(), w.data() + (start * m) + below, m, done, m - below);
4276 for (std::size_t t {0}; t < done; ++t) {
4277 T*
const column {w.data() + ((start + t) * m)};
4278 std::fill(column + start + t + 1, column + m, T {});
4280 for (
const std::size_t j : deferred) {
4281 current[j] = detail::contiguous_norm(w.data() + (j * m) + below, m - below);
4282 reference[j] = current[j];
4299 template <
typename T>
4302 detail::require_finite(a,
"QR decomposition");
4303 const std::size_t rows {a.
rows()};
4304 const std::size_t cols {a.
cols()};
4305 return matrix<T> {std::min(rows, cols), cols, detail::householder_r(std::move(a).elements(), rows, cols)};
4326 template <
typename T>
4327 requires std::is_floating_point_v<T>
4342 template <
typename T>
4348 using R =
typename T::value_type;
4349 const R c {f.real()};
4350 const R d {f.imag()};
4351 for (std::size_t i {0}; i < count; ++i) {
4352 const R a {x[i].real()};
4353 const R b {-x[i].imag()};
4358 const R re {ac - bd};
4359 const R im {ad + bc};
4360 y[i] = T {y[i].real() + re, y[i].imag() + im};
4369 double*, std::size_t);
4375 template <
typename T>
4386#ifdef NUMERICAL_NEON_COMPILED
4393 inline std::complex<double> neon_hermitian_row(
const double* row,
4398 std::size_t count)
noexcept
4400 const float64x2_t real {vr, -vr};
4401 const float64x2_t imag {vi, vi};
4402 float64x2_t same[2] {vdupq_n_f64(0.0), vdupq_n_f64(0.0)};
4403 float64x2_t across[2] {vdupq_n_f64(0.0), vdupq_n_f64(0.0)};
4405 for (; j + 2 <= count; j += 2) {
4406 for (std::size_t l {0}; l < 2; ++l) {
4407 const float64x2_t r {vld1q_f64(row + (2 * (j + l)))};
4408 const float64x2_t x {vld1q_f64(v + (2 * (j + l)))};
4409 const float64x2_t s {vextq_f64(r, r, 1)};
4410 float64x2_t o {vld1q_f64(out + (2 * (j + l)))};
4411 o = vfmaq_f64(o, real, r);
4412 o = vfmaq_f64(o, imag, s);
4413 same[l] = vfmaq_f64(same[l], r, x);
4414 across[l] = vfmaq_f64(across[l], s, x);
4415 vst1q_f64(out + (2 * (j + l)), o);
4418 const float64x2_t sum_same {vaddq_f64(same[0], same[1])};
4419 const float64x2_t sum_across {vaddq_f64(across[0], across[1])};
4420 double re {vgetq_lane_f64(sum_same, 0) - vgetq_lane_f64(sum_same, 1)};
4421 double im {vgetq_lane_f64(sum_across, 0) + vgetq_lane_f64(sum_across, 1)};
4422 for (; j < count; ++j) {
4423 const double rr {row[2 * j]};
4424 const double ri {row[(2 * j) + 1]};
4425 out[2 * j] = std::fma(vi, ri, std::fma(vr, rr, out[2 * j]));
4426 out[(2 * j) + 1] = std::fma(vi, rr, std::fma(-vr, ri, out[(2 * j) + 1]));
4427 re = std::fma(-ri, v[(2 * j) + 1], std::fma(rr, v[2 * j], re));
4428 im = std::fma(rr, v[(2 * j) + 1], std::fma(ri, v[2 * j], im));
4430 return std::complex<double> {re, im};
4440 const std::complex<double>* row,
4441 const std::complex<double>* v,
4442 std::complex<double>* out,
4445#ifdef NUMERICAL_X86_COMPILED
4448 if (path == gemm_path::avx512 || path == gemm_path::avx2) {
4449 const auto*
const values {
reinterpret_cast<const double*
>(v)};
4450 const auto*
const parts {
reinterpret_cast<const double*
>(row)};
4451 auto*
const into {
reinterpret_cast<double*
>(out)};
4452 const std::complex<double> lower {path == gemm_path::avx512
4453 ? avx512_hermitian_row(parts, values, v[i].real(), v[i].imag(), into, i)
4454 : avx2_hermitian_row(parts, values, v[i].real(), v[i].imag(), into, i)};
4455 return lower + (row[i] * v[i]);
4458#ifdef NUMERICAL_NEON_COMPILED
4460 const auto*
const values {
reinterpret_cast<const double*
>(v)};
4461 const auto*
const parts {
reinterpret_cast<const double*
>(row)};
4462 auto*
const into {
reinterpret_cast<double*
>(out)};
4463 const std::complex<double> lower {neon_hermitian_row(parts, values, v[i].real(), v[i].imag(), into, i)};
4464 return lower + (row[i] * v[i]);
4467 return hermitian_row<std::complex<double>>(kernel, row, v, out, i);
4477 return kernel(row, v, v[i], out, i) + (row[i] * v[i]);
4486 template <
typename T>
4489#ifdef NUMERICAL_X86_COMPILED
4490 if constexpr (std::is_same_v<T, double>) {
4514 template <
typename T>
4522 constexpr std::size_t rows_per_task {32};
4523 const std::size_t tasks {(m + rows_per_task - 1) / rows_per_task};
4524 if (scratch.size() < tasks * m) {
4525 scratch.resize(tasks * m, T {});
4527 symmetric_row_kernel kernel {[](
const double* row,
const double* x,
double f,
double* out, std::size_t count) {
4530 symmetric_rows_kernel group {[](
const double* rows, std::size_t ld,
const double* x,
double* out, std::size_t i) {
4533#ifdef NUMERICAL_X86_COMPILED
4534 if constexpr (std::is_same_v<T, double>) {
4536 if (path == gemm_path::avx512) {
4537 kernel = &avx512_symmetric_row;
4538 group = &avx512_symmetric_rows;
4540 else if (path == gemm_path::avx2) {
4541 kernel = &avx2_symmetric_row;
4542 group = &avx2_symmetric_rows;
4548 parallel_for(tasks, rows_per_task * m * symmetric_row_speedup<T>(), [&](std::size_t index) {
4549 const std::size_t task {tasks - 1 - index};
4550 const std::size_t first {task * rows_per_task};
4551 const std::size_t last {std::min(first + rows_per_task, m)};
4552 T* own {scratch.data() + (task * m)};
4553 std::fill(own, own + last, T {});
4554 std::size_t i {first};
4555 if constexpr (std::is_same_v<T, double>) {
4557 const std::array<double, symmetric_row_group> sums {group(block + (i * n), n, v, own, i)};
4559 own[i + r] += sums[r];
4563 for (; i < last; ++i) {
4564 own[i] +=
hermitian_row(kernel, block + (i * n), v, own, i);
4567 std::fill(w, w + m, T {});
4568 for (std::size_t task {0}; task < tasks; ++task) {
4569 add_product(w, T {1}, scratch.data() + (task * m), std::min((task + 1) * rows_per_task, m));
4576#ifdef NUMERICAL_X86_COMPILED
4577 inline constexpr std::size_t corrected_product_least {256};
4583 template <
typename T>
4584 requires std::is_floating_point_v<T>
4602 template <split_complex T>
4610#ifdef NUMERICAL_X86_COMPILED
4611 if constexpr (std::is_same_v<T, std::complex<double>>) {
4618 using R =
typename T::value_type;
4619 for (std::size_t t {0}; t < terms; ++t) {
4620 const R c {f[t].real()};
4621 const R d {f[t].imag()};
4622 const T*
const row {x + (t * ldx)};
4623 for (std::size_t i {0}; i < count; ++i) {
4624 const R a {row[i].real()};
4625 const R b {row[i].imag()};
4630 const R re {ac - bd};
4631 const R im {ad + bc};
4632 y[i] = T {y[i].real() - re, y[i].imag() - im};
4656 template <
typename T>
4663 const T* corrections,
4668 const T* next_factors =
nullptr)
4670 constexpr std::size_t rows_per_task {32};
4671 const std::size_t tasks {(m + rows_per_task - 1) / rows_per_task};
4672 if (scratch.size() < tasks * m) {
4673 scratch.resize(tasks * m, T {});
4675 symmetric_row_kernel kernel {[](
const double* row,
const double* x,
double f,
double* out, std::size_t count) {
4678 symmetric_rows_kernel group {[](
const double* rows, std::size_t ld,
const double* x,
double* out, std::size_t i) {
4681#ifdef NUMERICAL_X86_COMPILED
4682 if constexpr (std::is_same_v<T, double>) {
4684 if (path == gemm_path::avx512) {
4685 kernel = &avx512_symmetric_row;
4686 group = &avx512_symmetric_rows;
4688 else if (path == gemm_path::avx2) {
4689 kernel = &avx2_symmetric_row;
4690 group = &avx2_symmetric_rows;
4697 const std::size_t pairs {terms / 2};
4698 const auto coefficients = [&](std::size_t p) {
4699 factors[2 * p] =
conjugate_dot(corrections + (((2 * p) + 1) * ldc), v, m);
4700 factors[(2 * p) + 1] =
conjugate_dot(corrections + ((2 * p) * ldc), v, m);
4702 parallel_for(tasks + (share ? pairs : 0), rows_per_task * m * symmetric_row_speedup<T>(), [&](std::size_t index) {
4703 if (index >= tasks) {
4704 coefficients(index - tasks);
4707 const std::size_t task {tasks - 1 - index};
4708 const std::size_t first {task * rows_per_task};
4709 const std::size_t last {std::min(first + rows_per_task, m)};
4710 T* own {scratch.data() + (task * m)};
4711 std::fill(own, own + last, T {});
4712 std::size_t i {first};
4713 if constexpr (std::is_same_v<T, double>) {
4715 const std::array<double, symmetric_row_group> sums {group(block + (i * n), n, v, own, i)};
4717 own[i + r] += sums[r];
4721 for (; i < last; ++i) {
4722 own[i] +=
hermitian_row(kernel, block + (i * n), v, own, i);
4725 for (std::size_t p {0}; !share && p < pairs; ++p) {
4728 constexpr std::size_t band {256};
4729 const auto bands = [&](std::size_t b) {
4730 const std::size_t first {b * band};
4731 const std::size_t count {std::min(band, m - first)};
4732 std::fill(w + first, w + first + count, T {});
4733 for (std::size_t task {0}; task < tasks; ++task) {
4734 const std::size_t reach {std::min((task + 1) * rows_per_task, m)};
4735 if (reach > first) {
4736 add_product(w + first, T {1}, scratch.data() + (task * m) + first, std::min(count, reach - first));
4740 if (next !=
nullptr) {
4745 parallel_for((m + band - 1) / band, band * (tasks + terms) * 8, bands);
4748 for (std::size_t b {0}; b < (m + band - 1) / band; ++b) {
4784 std::complex<double> delta,
4785 std::complex<double>& next)
4787 next = delta * std::conj(
phase_of(t));
4792 template <
typename T>
4813 template <
typename T>
4819 std::vector<buffer<T>> reflectors(n);
4823 const auto left {std::make_unique_for_overwrite<T[]>(n * 2 *
tridiagonal_block)};
4824 const auto right {std::make_unique_for_overwrite<T[]>(2 *
tridiagonal_block * n)};
4831 bool column_ahead {
false};
4837 const std::size_t width {k1 - k0};
4838 std::fill_n(by_row.data(), 2 * width * n, T {});
4839 for (std::size_t i {k0}; i < n; ++i) {
4840 for (std::size_t k {k0}; k < std::min(k1, i + 1); ++k) {
4841 columns[((k - k0) * n) + i] = a[(i * n) + k];
4844 for (std::size_t k {k0}; k < k1; ++k) {
4845 const std::size_t j {k - k0};
4846 const std::size_t m {n - k - 1};
4847 T*
const column {columns.data() + (j * n) + k};
4849 const std::size_t from {column_ahead ? j - 1 : 0};
4850 for (std::size_t p {from}; p < j; ++p) {
4851 factors[2 * (p - from)] =
conj_of(by_row[(((2 * p) + 1) * n) + k]);
4852 factors[(2 * (p - from)) + 1] =
conj_of(by_row[((2 * p) * n) + k]);
4854 subtract_corrections(column, factors.data(), by_row.data() + ((2 * from) * n) + k, n, 2 * (j - from), m + 1);
4855 column_ahead =
false;
4856 a[(k * n) + k] = column[0];
4857 buffer<T> v(column + 1, column + m + 1);
4865 sub[k] = alpha / up;
4868 for (T& element : v) {
4871 const T* block {a.data() + ((k + 1) * n) + k + 1};
4875 T*
const next {k + 1 < k1 && j > 0 ? columns.data() + ((j + 1) * n) + k + 1 :
nullptr};
4876 for (std::size_t p {0}; next !=
nullptr && p < j; ++p) {
4877 next_factors[2 * p] =
conj_of(by_row[(((2 * p) + 1) * n) + k + 1]);
4878 next_factors[(2 * p) + 1] =
conj_of(by_row[((2 * p) * n) + k + 1]);
4880 corrected_hermitian_product(block, n, m, v.data(), w.data(), symv_scratch, by_row.data() + k + 1, n, 2 * j, factors.data(),
4881 next, next_factors.data());
4882 column_ahead = next !=
nullptr;
4884 for (std::size_t i {0}; i < m; ++i) {
4885 w[i] = (
static_cast<T
>(2) * w[i]) - (
static_cast<T
>(2) * c * v[i]);
4886 by_row[((2 * j) * n) + k + 1 + i] = v[i];
4887 by_row[(((2 * j) + 1) * n) + k + 1 + i] = w[i];
4889 reflectors[k + 1] = std::move(v);
4896 const std::size_t rest {n - k1};
4897 const std::size_t depth {2 * width};
4898 for (std::size_t i {0}; i < rest; ++i) {
4899 for (std::size_t p {0}; p < width; ++p) {
4900 left[(i * depth) + p] = -by_row[((2 * p) * n) + k1 + i];
4901 left[(i * depth) + width + p] = -by_row[(((2 * p) + 1) * n) + k1 + i];
4904 for (std::size_t p {0}; p < width; ++p) {
4905 for (std::size_t i {0}; i < rest; ++i) {
4906 right[(p * rest) + i] =
conj_of(by_row[(((2 * p) + 1) * n) + k1 + i]);
4907 right[((width + p) * rest) + i] =
conj_of(by_row[((2 * p) * n) + k1 + i]);
4910 T* trailing {a.data() + (k1 * n) + k1};
4911 if constexpr (std::is_same_v<T, double>) {
4913 gemm_triangle<a_rows, b_rows>(rest, depth, left.get(), depth, right.get(), rest, trailing, n,
true);
4919 gemm(rows, r0 + rows, depth, left.get() + (r0 * depth), depth, right.get(), rest, trailing + (r0 * n), n);
4922 for (std::size_t i {0}; i < n; ++i) {
4928 for (std::size_t k {0}; k + 1 < n; ++k) {
4931 return {.reflectors = std::move(reflectors), .delta = std::move(delta)};
4939 template <
typename T>
4944 for (std::size_t i {0}; i < n; ++i) {
4945 mt[(i * n) + i] = T {1};
4947 for (std::size_t k1 {n}; k1 > 1;) {
4948 const std::size_t k0 {k1 - std::min(k1 - 1,
qr_block)};
4952 for (std::size_t j {0}; j < n; ++j) {
4954 for (std::size_t i {0}; i < n; ++i) {
4955 mt[(j * n) + i] *= factor;
4967 template <
typename T>
4973 if constexpr (!std::is_floating_point_v<T>) {
4975 for (std::size_t j {0}; j < n; ++j) {
4980 for (std::size_t k1 {n}; k1 > 1;) {
4981 const std::size_t k0 {k1 - std::min(k1 - 1,
qr_block)};
4988 template <
typename T>
5024 [[nodiscard]]
inline std::vector<rotation_run>
rotation_runs(
const std::vector<row_operation>& operations)
5026 std::vector<rotation_run> runs;
5027 for (std::size_t t {0}; t < operations.size();) {
5029 std::size_t count {1};
5031 if (op.what == row_operation::kind::rotate && t + 1 < operations.size()
5032 && operations[t + 1].what == row_operation::kind::rotate) {
5033 down = operations[t + 1].
j == op.i;
5034 for (; t + count < operations.size(); ++count) {
5037 const bool chained {down ? next.
j == previous.i : next.i == previous.j};
5038 if (next.what != row_operation::kind::rotate || !chained) {
5043 runs.push_back({.first = t, .count = count, .down = down});
5058 template <
typename T>
5061 const std::vector<row_operation>& operations)
5063 constexpr std::size_t width {64};
5064 const std::vector<rotation_run> runs {
rotation_runs(operations)};
5065 parallel_for((n + width - 1) / width, operations.size() * width, [&](std::size_t chunk) {
5066 const std::size_t first {chunk * width};
5067 const std::size_t count {std::min(first + width, n) - first};
5068 std::array<T, width> carry {};
5071 if (run.count > 1) {
5073 const T* source {m.data() + ((run.down ? start.j : start.i) * n) + first};
5074 std::copy(source, source + count, carry.begin());
5075 for (std::size_t u {run.first}; u < run.first + run.count; ++u) {
5077 const T c {detail::from_carried<T>(op.c)};
5078 const T s {detail::from_carried<T>(op.s)};
5080 const T* row {m.data() + (op.i * n) + first};
5081 T* other {m.data() + (op.j * n) + first};
5082 for (std::size_t k {0}; k < count; ++k) {
5084 const T b {carry[k]};
5085 other[k] = (c * b) - (s * a);
5086 carry[k] = (c * a) + (s * b);
5090 T* row {m.data() + (op.i * n) + first};
5091 const T* other {m.data() + (op.j * n) + first};
5092 for (std::size_t k {0}; k < count; ++k) {
5093 const T a {carry[k]};
5094 const T b {other[k]};
5095 row[k] = (c * a) + (s * b);
5096 carry[k] = (c * b) - (s * a);
5100 const row_operation& end {operations[run.first + run.count - 1]};
5101 T* target {m.data() + ((run.down ? end.i : end.j) * n) + first};
5102 std::copy(carry.begin(), carry.begin() +
static_cast<std::ptrdiff_t
>(count), target);
5105 T* row {m.data() + (start.i * n) + first};
5106 T* other {m.data() + (start.j * n) + first};
5108 if (start.what == row_operation::kind::rotate) {
5109 const T c {detail::from_carried<T>(start.c)};
5110 const T s {detail::from_carried<T>(start.s)};
5111 for (std::size_t k {0}; k < count; ++k) {
5113 const T b {other[k]};
5114 row[k] = (c * a) + (s * b);
5115 other[k] = (c * b) - (s * a);
5118 else if (start.what == row_operation::kind::negate) {
5119 for (std::size_t k {0}; k < count; ++k) {
5124 std::swap_ranges(row, row + count, other);
5144 return {1.0, 0.0, f};
5147 const double r {std::copysign(length, f)};
5148 return {std::abs(f) / length, g / r, r};
5169 const double sum {a + c};
5170 const double difference {a - c};
5171 const double spread {std::abs(difference)};
5172 const double twice_b {b + b};
5173 const double coupling {std::abs(twice_b)};
5174 const double larger_part {std::abs(a) > std::abs(c) ? a : c};
5175 const double other_part {std::abs(a) > std::abs(c) ? c : a};
5176 double root {coupling * std::sqrt(2.0)};
5177 if (spread > coupling) {
5178 root = spread * std::sqrt(1.0 + ((coupling / spread) * (coupling / spread)));
5180 else if (spread < coupling) {
5181 root = coupling * std::sqrt(1.0 + ((spread / coupling) * (spread / coupling)));
5183 double larger {0.5 *
root};
5184 double smaller {-0.5 *
root};
5185 int sign_of_sum {1};
5188 sign_of_sum =
sum < 0.0 ? -1 : 1;
5189 smaller = ((larger_part / larger) * other_part) - ((b / larger) * b);
5191 const int sign_of_difference {difference >= 0.0 ? 1 : -1};
5192 const double towards {difference >= 0.0 ? difference +
root : difference -
root};
5195 if (std::abs(towards) > coupling) {
5196 const double t {-twice_b / towards};
5197 sn = 1.0 / std::sqrt(1.0 + (t * t));
5200 else if (coupling != 0.0) {
5201 const double t {-towards / twice_b};
5202 cs = 1.0 / std::sqrt(1.0 + (t * t));
5205 if (sign_of_sum == sign_of_difference) {
5210 return {larger, smaller, cs, sn};
5229 std::size_t max_steps)
5231 constexpr double eps {std::numeric_limits<double>::epsilon() / 2.0};
5232 constexpr double eps2 {eps * eps};
5233 constexpr double safe_least {std::numeric_limits<double>::min()};
5234 const double scaled_most {std::sqrt(1.0 / safe_least) / 3.0};
5235 const double scaled_least {std::sqrt(safe_least) / eps2};
5236 std::size_t steps {0};
5237 std::size_t first {0};
5239 std::size_t last {first};
5240 while (last + 1 < n && std::abs(e[last]) > (std::sqrt(std::abs(d[last])) * std::sqrt(std::abs(d[last + 1]))) * eps) {
5246 const std::size_t block_first {first};
5248 if (last == block_first) {
5251 double largest {0.0};
5252 for (std::size_t i {block_first}; i <= last; ++i) {
5253 largest = std::max({largest, std::abs(d[i]), i < last ? std::abs(e[i]) : 0.0});
5255 const bool scaled {largest > scaled_most || largest < scaled_least};
5256 const double scale {largest > scaled_most ? scaled_most : scaled_least};
5257 for (std::size_t i {block_first}; i <= last; ++i) {
5258 d[i] =
scaled ? (d[i] / largest) * scale : d[i];
5260 const double entry {
scaled ? (e[i] / largest) * scale : e[i]};
5261 e[i] = entry * entry;
5265 const auto shift = [](
double p,
double next,
double square) {
5267 const double sigma {(next - p) / (2.0 *
root)};
5270 if (std::abs(d[last]) >= std::abs(d[block_first])) {
5271 std::size_t l {block_first};
5274 while (m < last && std::abs(e[m]) > eps2 * std::abs(d[m] * d[m + 1])) {
5287 d[l + 1] = pair.smaller;
5292 if (steps == max_steps) {
5293 throw convergence_error(
"symmetric eigenvalues: QL did not converge within its steps");
5296 const double sigma {shift(d[l], d[l + 1], e[l])};
5299 double gamma {d[m] - sigma};
5300 double p {gamma * gamma};
5301 for (std::size_t i {m}; i-- > l;) {
5302 const double bb {e[i]};
5303 const double r {p + bb};
5307 const double old_c {c};
5310 const double old_gamma {gamma};
5311 gamma = (c * (d[i] - sigma)) - (s * old_gamma);
5312 d[i + 1] = old_gamma + (d[i] - gamma);
5313 p = c != 0.0 ? (gamma * gamma) / c : old_c * bb;
5316 d[l] = sigma + gamma;
5320 std::size_t l {last};
5323 while (m > block_first && std::abs(e[m - 1]) > eps2 * std::abs(d[m] * d[m - 1])) {
5326 if (m > block_first) {
5330 if (l == block_first) {
5339 d[l - 1] = pair.smaller;
5341 if (l < block_first + 2) {
5347 if (steps == max_steps) {
5348 throw convergence_error(
"symmetric eigenvalues: QL did not converge within its steps");
5351 const double sigma {shift(d[l], d[l - 1], e[l - 1])};
5354 double gamma {d[m] - sigma};
5355 double p {gamma * gamma};
5356 for (std::size_t i {m}; i < l; ++i) {
5357 const double bb {e[i]};
5358 const double r {p + bb};
5362 const double old_c {c};
5365 const double old_gamma {gamma};
5366 gamma = (c * (d[i + 1] - sigma)) - (s * old_gamma);
5367 d[i] = old_gamma + (d[i + 1] - gamma);
5368 p = c != 0.0 ? (gamma * gamma) / c : old_c * bb;
5371 d[l] = sigma + gamma;
5374 for (std::size_t i {block_first};
scaled && i <= last; ++i) {
5375 d[i] = (d[i] / scale) * largest;
5397 template <
typename T>
5402 std::size_t max_steps)
5404 constexpr double eps {std::numeric_limits<double>::epsilon() / 2.0};
5405 constexpr double eps2 {eps * eps};
5406 constexpr double safe_least {std::numeric_limits<double>::min()};
5407 const double scaled_most {std::sqrt(1.0 / safe_least) / 3.0};
5408 const double scaled_least {std::sqrt(safe_least) / eps2};
5415 std::vector<row_operation> on_zt;
5416 std::size_t steps {0};
5417 const auto negligible = [&](std::size_t i) {
5418 return e[i] * e[i] <= ((eps2 * std::abs(d[i])) * std::abs(d[i + 1])) + safe_least;
5420 std::size_t first {0};
5423 std::size_t last {first};
5424 while (last + 1 < n && std::abs(e[last]) > (std::sqrt(std::abs(d[last])) * std::sqrt(std::abs(d[last + 1]))) * eps) {
5430 const std::size_t block_first {first};
5432 if (last == block_first) {
5435 double largest {0.0};
5436 for (std::size_t i {block_first}; i <= last; ++i) {
5437 largest = std::max({largest, std::abs(d[i]), i < last ? std::abs(e[i]) : 0.0});
5440 const bool scaled {largest > scaled_most || largest < scaled_least};
5441 const double scale {largest > scaled_most ? scaled_most : scaled_least};
5442 for (std::size_t i {block_first};
scaled && i <= last; ++i) {
5443 d[i] = (d[i] / largest) * scale;
5444 e[i] = i < last ? (e[i] / largest) * scale : e[i];
5446 if (std::abs(d[last]) >= std::abs(d[block_first])) {
5447 std::size_t l {block_first};
5450 while (m < last && !negligible(m)) {
5462 on_zt.push_back({row_operation::kind::rotate, l, l + 1, pair.c, pair.s});
5464 d[l + 1] = pair.smaller;
5469 if (steps == max_steps) {
5470 throw convergence_error(
"symmetric eigendecomposition: QL did not converge within its steps");
5473 double g {(d[l + 1] - d[l]) / (2.0 * e[l])};
5475 g = d[m] - d[l] + (e[l] / (g + std::copysign(r, g)));
5479 for (std::size_t i {m}; i-- > l;) {
5480 const double f {s * e[i]};
5481 const double b {c * e[i]};
5489 r = ((d[i] - g) * s) + (2.0 * c * b);
5493 on_zt.push_back({row_operation::kind::rotate, i, i + 1, c, -s});
5500 std::size_t l {last};
5503 while (m > block_first && !negligible(m - 1)) {
5506 if (m > block_first) {
5510 if (l == block_first) {
5518 on_zt.push_back({row_operation::kind::rotate, l - 1, l, pair.c, pair.s});
5520 d[l] = pair.smaller;
5522 if (l < block_first + 2) {
5528 if (steps == max_steps) {
5529 throw convergence_error(
"symmetric eigendecomposition: QL did not converge within its steps");
5532 double g {(d[l - 1] - d[l]) / (2.0 * e[l - 1])};
5534 g = d[m] - d[l] + (e[l - 1] / (g + std::copysign(r, g)));
5538 for (std::size_t i {m}; i < l; ++i) {
5539 const double f {s * e[i]};
5540 const double b {c * e[i]};
5548 r = ((d[i + 1] - g) * s) + (2.0 * c * b);
5552 on_zt.push_back({row_operation::kind::rotate, i, i + 1, c, s});
5558 for (std::size_t i {block_first};
scaled && i <= last; ++i) {
5559 d[i] = (d[i] / scale) * largest;
5560 e[i] = i < last ? (e[i] / scale) * largest : e[i];
5592 const double root {std::sqrt(std::abs((a * a) - (4.0 * b * c)))};
5593 return a <= 0.0 ? (a -
root) / (2.0 * c) : (2.0 * b) / (a +
root);
5614 template <
typename Offset>
5618 std::size_t max_iterations,
5620 const Offset& offset)
5622 const std::size_t k {z.size()};
5623 const double rhoinv {1.0 / rho};
5624 const bool last {i + 1 == k};
5625 double weight {0.0};
5626 for (
const double element : z) {
5627 weight += element * element;
5629 std::size_t origin {i};
5631 double upper {2.0 * rho * weight};
5633 const double gap {offset(i, i + 1)};
5635 for (std::size_t j {0}; j < k; ++j) {
5636 f += z[j] * z[j] / (offset(i, j) - (gap / 2.0));
5645 double tau {(lower + upper) / 2.0};
5646 for (std::size_t iteration {0}; iteration < max_iterations; ++iteration) {
5653 for (std::size_t j {0}; j <= i; ++j) {
5654 delta[j] = offset(origin, j) - tau;
5655 const double t {z[j] / delta[j]};
5659 for (std::size_t j {i + 1}; j < k; ++j) {
5660 delta[j] = offset(origin, j) - tau;
5661 const double t {z[j] / delta[j]};
5665 const double w {rhoinv + psi + phi};
5666 if (std::abs(w) <= std::numeric_limits<double>::epsilon()
5667 * ((8.0 * (phi - psi + rhoinv)) + (3.0 * std::abs(tau) * (dpsi + dphi)))) {
5668 return {.
origin = origin, .offset = tau};
5670 (w < 0.0 ? lower : upper) = tau;
5673 const double a1 {delta[i]};
5674 const double a2 {last ? 0.0 : delta[i + 1]};
5675 const double c {w - (a1 * dpsi) - (a2 * dphi)};
5676 const double a {last ? (a1 * c) + (a1 * a1 * dpsi) : ((a1 + a2) * w) - (a1 * a2 * (dpsi + dphi))};
5677 const double b {last ? 0.0 : a1 * a2 * w};
5678 const double next {tau + (last ? a / c :
quadratic_step(a, b, c))};
5681 tau = next > lower && next < upper ? next : (lower + upper) / 2.0;
5701 std::size_t max_iterations,
5705 [&d](std::size_t o, std::size_t j) {
return d[j] - d[o]; })};
5706 return d[
root.origin] +
root.offset;
5742 if (
buffer.size < size) {
5743 buffer.data = std::make_unique_for_overwrite<double[]>(size);
5745 double*
const elements {
buffer.data.get()};
5748 std::fill(elements + first, elements + std::min(first +
first_touch_chunk, size), 0.0);
5751 return buffer.data.get();
5803 std::vector<unsigned> reach(n);
5804 for (std::size_t j {0}; j < n; ++j) {
5805 reach[j] = j <
split ? 1U : 2U;
5807 for (
double& element : z) {
5808 element /= std::numbers::sqrt2;
5811 std::vector<std::size_t> order(n);
5812 for (std::size_t j {0}; j < n; ++j) {
5815 std::sort(order.begin(), order.end(), [&d](std::size_t x, std::size_t y) { return d[x] < d[y]; });
5816 double largest_d {0.0};
5817 double largest_z {0.0};
5818 for (std::size_t j {0}; j < n; ++j) {
5819 largest_d = std::max(largest_d, std::abs(d[j]));
5820 largest_z = std::max(largest_z, std::abs(z[j]));
5822 const double tolerance {8.0 * std::numeric_limits<double>::epsilon() * std::max(largest_d, largest_z)};
5823 std::vector<std::size_t>
kept;
5824 std::vector<std::size_t> deflated;
5825 std::size_t pending {n};
5826 for (
const std::size_t j : order) {
5827 if (rho * std::abs(z[j]) <= tolerance) {
5828 deflated.push_back(j);
5835 const double length {std::hypot(z[j], z[pending])};
5836 const double c {z[j] / length};
5837 const double s {-z[pending] / length};
5838 if (std::abs((d[j] - d[pending]) * c * s) <= tolerance) {
5842 for (std::size_t r {0}; r < n; ++r) {
5843 const double x {q[(r * ldq) + pending]};
5844 const double y {q[(r * ldq) + j]};
5845 q[(r * ldq) + pending] = (c * x) + (s * y);
5846 q[(r * ldq) + j] = (c * y) - (s * x);
5848 reach[j] = reach[pending] = reach[j] | reach[pending];
5849 const double rotated {(d[pending] * c * c) + (d[j] * s * s)};
5850 d[j] = (d[pending] * s * s) + (d[j] * c * c);
5851 d[pending] = rotated;
5852 deflated.push_back(pending);
5855 kept.push_back(pending);
5860 kept.push_back(pending);
5862 const std::size_t k {
kept.size()};
5866 for (std::size_t i {0}; i < k; ++i) {
5867 poles[i] = d[
kept[i]];
5868 weights[i] = z[
kept[i]];
5869 norm += weights[i] * weights[i];
5871 norm = std::sqrt(norm);
5872 for (
double& weight : weights) {
5875 const double scaled_rho {rho * norm * norm};
5888 const std::size_t last {std::min(first +
lowner_block, k)};
5889 std::array<double, lowner_block> product {};
5890 for (std::size_t j {first}; j < last; ++j) {
5891 product[j - first] = gaps[(j * k) + j];
5893 for (std::size_t i {0}; i < k; ++i) {
5894 for (std::size_t j {first}; j < last; ++j) {
5896 product[j - first] *= gaps[(i * k) + j] / (poles[j] - poles[i]);
5900 for (std::size_t j {first}; j < last; ++j) {
5901 signed_weights[j] = std::copysign(std::sqrt(-product[j - first]), weights[j]);
5906 double*
const u {gaps};
5909 const std::size_t ti {tile /
tiles};
5910 const std::size_t tj {tile %
tiles};
5915 for (std::size_t j {std::max(tj *
lowner_block, ti == tj ? i : 0)}; j < std::min((tj + 1) *
lowner_block, k); ++j) {
5916 const double above {gaps[(i * k) + j]};
5917 const double below {gaps[(j * k) + i]};
5918 u[(j * k) + i] = signed_weights[j] / above;
5919 u[(i * k) + j] = signed_weights[i] / below;
5924 for (std::size_t j {0}; j < k; ++j) {
5925 for (std::size_t i {0}; i < k; ++i) {
5926 length[i] += u[(j * k) + i] * u[(j * k) + i];
5929 for (
double& l : length) {
5933 for (std::size_t i {0}; i < k; ++i) {
5934 u[(j * k) + i] /= length[i];
5940 for (
const auto& [half, first, rows] : {std::tuple {1U, std::size_t {0},
split}, std::tuple {2U,
split, n -
split}}) {
5941 std::vector<std::size_t> reaching;
5942 for (std::size_t i {0}; i < k; ++i) {
5943 if ((reach[
kept[i]] & half) != 0U) {
5944 reaching.push_back(i);
5947 const std::size_t width {reaching.size()};
5951 for (std::size_t c {0}; c < width; ++c) {
5952 columns[(r * width) + c] = q[((first + r) * ldq) +
kept[reaching[c]]];
5954 std::fill_n(updated + ((first + r) * k), k, 0.0);
5956 parallel_for(width, k, [&](std::size_t c) { std::copy_n(u + (reaching[c] * k), k, factor + (c * k)); });
5957 gemm(rows, k, width, columns, width, factor, k, updated + (first * k), k);
5962 for (std::size_t i {0}; i < k; ++i) {
5963 values[i] = roots[i];
5965 for (std::size_t i {0}; i < deflated.size(); ++i) {
5966 values[k + i] = d[deflated[i]];
5968 for (std::size_t j {0}; j < n; ++j) {
5971 std::sort(order.begin(), order.end(), [&values](std::size_t x, std::size_t y) { return values[x] < values[y]; });
5972 for (std::size_t j {0}; j < n; ++j) {
5973 d[j] = values[order[j]];
5977 for (std::size_t j {0}; j < n; ++j) {
5978 const std::size_t source {order[j]};
5979 q[(r * ldq) + j] = source < k ? updated[(r * k) + source] : before[deflated[source - k]];
5993 const double* work_e {};
6002 std::size_t depth {};
6003 std::size_t first {};
6004 std::size_t second {};
6023 double largest {0.0};
6024 for (std::size_t i {0}; i < n; ++i) {
6025 largest = std::max({largest, std::abs(d[i]), i + 1 < n ? std::abs(e[i]) : 0.0});
6027 divide_node node {.
d = d, .work_d = d, .work_e = e, .n = n, .q = q, .ldq = ldq, .depth = depth};
6028 (void)std::frexp(largest, &node.exponent);
6029 if (node.exponent != 0) {
6030 node.scaled_d.assign(n,
double {});
6031 node.scaled_e.assign(n, 0.0);
6032 for (std::size_t i {0}; i < n; ++i) {
6033 node.scaled_d[i] = std::ldexp(d[i], -node.exponent);
6034 node.scaled_e[i] = i + 1 < n ? std::ldexp(e[i], -node.exponent) : 0.0;
6036 node.work_d = node.scaled_d.data();
6037 node.work_e = node.scaled_e.data();
6040 nodes.push_back(std::move(node));
6044 node.beta = node.work_e[node.n1 - 1];
6045 node.work_d[node.n1 - 1] -= std::abs(node.beta);
6046 node.work_d[node.n1] -= std::abs(node.beta);
6047 double*
const work_d {node.work_d};
6048 const double*
const work_e {node.work_e};
6049 const std::size_t n1 {node.n1};
6050 const std::size_t index {nodes.size()};
6051 nodes.push_back(std::move(node));
6052 nodes[index].first = nodes.size();
6053 plan_divide(nodes, work_d, work_e, n1, q, ldq, depth + 1);
6054 nodes[index].second = nodes.size();
6055 plan_divide(nodes, work_d + n1, work_e + n1, n - n1, q + (n1 * ldq) + n1, ldq, depth + 1);
6062 const std::size_t n {node.
n};
6065 std::copy(node.
work_e, node.
work_e + (n - 1), sub.begin());
6067 for (std::size_t i {0}; i < n; ++i) {
6068 zt[(i * n) + i] = 1.0;
6071 std::vector<std::size_t> order(n);
6072 for (std::size_t i {0}; i < n; ++i) {
6075 std::sort(order.begin(), order.end(), [&
diagonal](std::size_t x, std::size_t y) { return diagonal[x] < diagonal[y]; });
6076 for (std::size_t j {0}; j < n; ++j) {
6078 for (std::size_t r {0}; r < n; ++r) {
6079 node.
q[(r * node.
ldq) + j] = zt[(order[j] * n) + r];
6088 const std::size_t n {node.
n};
6089 const std::size_t n1 {node.
n1};
6090 const std::size_t n2 {n - n1};
6091 double*
const q {node.
q};
6093 for (std::size_t i {0}; i < n1; ++i) {
6094 z[i] = q[((n1 - 1) * node.
ldq) + i];
6096 for (std::size_t i {0}; i < n2; ++i) {
6097 z[n1 + i] = std::copysign(1.0, node.
beta) * q[(n1 * node.
ldq) + n1 + i];
6101 std::copy(values.begin(), values.end(), node.
work_d);
6108 for (std::size_t i {0}; i < node.
n; ++i) {
6152 q.assign(n * n, 0.0);
6153 std::vector<divide_node> nodes;
6155 const auto cut {
static_cast<std::size_t
>(std::bit_width(
max_threads() - 1))};
6156 std::vector<std::size_t> tasks;
6157 for (std::size_t i {0}; i < nodes.size(); ++i) {
6158 if (nodes[i].depth == cut || (nodes[i].depth < cut && nodes[i].n1 == 0)) {
6162 const std::size_t task_order {nodes[tasks[0]].n};
6163 parallel_for(tasks.size(), tasks.size() > 1 ? task_order * task_order * task_order : 0, [&](std::size_t t) {
6167 for (std::size_t level {cut}; level-- > 0;) {
6168 std::vector<std::size_t> joins;
6169 for (std::size_t i {0}; i < nodes.size(); ++i) {
6170 if (nodes[i].n1 != 0 && nodes[i].depth == level) {
6174 if (joins.empty()) {
6177 if (joins.size() == 1) {
6183 const std::size_t order {nodes[joins[0]].n};
6184 parallel_for(joins.size(), order * order * order / 4, [&](std::size_t j) {
6185 join_divide_node(nodes[joins[j]], thread_workspace());
6186 release_large_workspace(thread_workspace());
6187 unscale_divide_node(nodes[joins[j]]);
6193 template <
typename T>
6199 for (std::size_t i {0}; i < n * n; ++i) {
6200 converted[i] = from_carried<T>(left[i]);
6203 gemm(n, n, n,
converted.data(), n, zt.data(), n, product.data(), n);
6204 zt = std::move(product);
6213 gemm(n, n, n, left.data(), n, zt.data(), n, product.data(), n);
6214 zt = std::move(product);
6219 buffer<std::complex<double>>& zt,
6224 for (std::size_t i {0}; i < n * n; ++i) {
6225 re[i] = zt[i].real();
6226 im[i] = zt[i].imag();
6230 for (std::size_t i {0}; i < n * n; ++i) {
6231 zt[i] = {re[i], im[i]};
6241 template <
typename T>
6256 for (std::size_t r {0}; r < n; ++r) {
6257 at[(j * n) + r] = from_carried<T>(q[(r * n) + j]);
6272 const double apq {a[(p * n) + q]};
6273 const double app {a[(p * n) + p]};
6274 const double aqq {a[(q * n) + q]};
6275 const double theta {(aqq - app) / (2.0 * apq)};
6276 const double t {(theta >= 0.0 ? 1.0 : -1.0) / (std::abs(theta) + std::sqrt((theta * theta) + 1.0))};
6277 const double c {1.0 / std::sqrt((t * t) + 1.0)};
6278 const double s {t * c};
6279 a[(p * n) + p] = (c * c * app) - (2.0 * s * c * apq) + (s * s * aqq);
6280 a[(q * n) + q] = (s * s * app) + (2.0 * s * c * apq) + (c * c * aqq);
6281 a[(p * n) + q] = 0.0;
6282 a[(q * n) + p] = 0.0;
6283 for (std::size_t i {0}; i < n; ++i) {
6284 if (i != p && i != q) {
6285 const double aip {a[(i * n) + p]};
6286 const double aiq {a[(i * n) + q]};
6287 a[(i * n) + p] = (c * aip) - (s * aiq);
6288 a[(p * n) + i] = a[(i * n) + p];
6289 a[(i * n) + q] = (s * aip) + (c * aiq);
6290 a[(q * n) + i] = a[(i * n) + q];
6293 for (std::size_t i {0}; i < n; ++i) {
6294 const double vip {v[(i * n) + p]};
6295 const double viq {v[(i * n) + q]};
6296 v[(i * n) + p] = (c * vip) - (s * viq);
6297 v[(i * n) + q] = (s * vip) + (c * viq);
6313 std::size_t max_sweeps)
6318 for (std::size_t sweeps {0};; ++sweeps) {
6319 bool rotated {
false};
6320 for (std::size_t p {0}; p < n; ++p) {
6321 for (std::size_t q {p + 1}; q < n; ++q) {
6322 const double bound {std::numeric_limits<double>::epsilon() * std::sqrt(std::abs(a[(p * n) + p])) * std::sqrt(std::abs(a[(q * n) + q]))};
6323 if (std::abs(a[(p * n) + q]) > std::max(bound, std::numeric_limits<double>::min())) {
6324 if (sweeps == max_sweeps) {
6325 throw convergence_error(
"symmetric eigendecomposition: Jacobi did not converge within its sweeps");
6341 std::vector<std::size_t> order(
diagonal.size());
6342 for (std::size_t i {0}; i < order.size(); ++i) {
6345 std::sort(order.begin(), order.end(), [&
diagonal](std::size_t x, std::size_t y) { return diagonal[x] < diagonal[y]; });
6354 template <
typename T>
6356 const std::vector<std::size_t>& order,
6360 parallel_for((n + transpose_tile - 1) / transpose_tile, transpose_tile * n, [&](std::size_t block) {
6361 const std::size_t r0 {block * transpose_tile};
6362 const std::size_t r1 {std::min(r0 + transpose_tile, n)};
6363 for (std::size_t c0 {0}; c0 < n; c0 += transpose_tile) {
6364 for (std::size_t c {c0}; c < std::min(c0 + transpose_tile, n); ++c) {
6365 const T*
const source {zt.data() + (order[c] * n)};
6366 for (std::size_t r {r0}; r < r1; ++r) {
6367 out[(r * n) + c] = source[r];
6388 template <
typename T>
6397 for (std::size_t k {0}; k < n; ++k) {
6398 const auto bkk {
real_part(l[(k * ldl) + k])};
6399 const auto akk {
real_part(c[(k * ldc) + k]) / (bkk * bkk)};
6400 c[(k * ldc) + k] = T {akk};
6402 const T half_akk {
static_cast<carried_t<T>>(-0.5) * akk};
6403 for (std::size_t i {k + 1}; i < n; ++i) {
6404 c[(i * ldc) + k] = (c[(i * ldc) + k] * T {
inverse}) + (half_akk * l[(i * ldl) + k]);
6405 x[i] =
conj_of(c[(i * ldc) + k]);
6406 y[i] =
conj_of(l[(i * ldl) + k]);
6408 for (std::size_t i {k + 1}; i < n; ++i) {
6409 T*
const row {c + (i * ldc)};
6413 for (std::size_t i {k + 1}; i < n; ++i) {
6414 x[i] = c[(i * ldc) + k] + (half_akk * l[(i * ldl) + k]);
6415 x[i] = (x[i] -
dot_product(l + (i * ldl) + k + 1, x.data() + k + 1, i - k - 1)) / l[(i * ldl) + i];
6416 c[(i * ldc) + k] = x[i];
6427 template <
typename T>
6450 gemm_triangle<a_rows, b_rows>(m, depth, a, depth, b, m, c, ldc,
true);
6463 template <
typename T>
6475 const std::size_t k1 {k0 + kb};
6476 const std::size_t m {n - k1};
6481 T*
const c21 {c + (k1 * n) + k0};
6482 const T*
const l21 {l + (k1 * n) + k0};
6484 for (std::size_t i {0}; i < kb; ++i) {
6485 for (std::size_t j {0}; j <= i; ++j) {
6486 diagonal[(i * kb) + j] = l[((k0 + i) * n) + k0 + j];
6488 std::fill(
diagonal.begin() +
static_cast<std::ptrdiff_t
>((i * kb) + i + 1),
diagonal.begin() +
static_cast<std::ptrdiff_t
>((i + 1) * kb), T {});
6490 turned.resize(kb * m);
6491 for (std::size_t r {0}; r < m; ++r) {
6492 for (std::size_t q {0}; q < kb; ++q) {
6493 turned[(q * m) + r] =
conj_of(c21[(r * n) + q]);
6497 for (std::size_t r {0}; r < m; ++r) {
6498 for (std::size_t q {0}; q < kb; ++q) {
6499 c21[(r * n) + q] =
conj_of(turned[(q * m) + r]);
6503 for (std::size_t i {0}; i < kb; ++i) {
6504 for (std::size_t j {0}; j < i; ++j) {
6505 const T value {
static_cast<carried_t<T>>(-0.5) * c[((k0 + i) * n) + k0 + j]};
6506 half[(i * kb) + j] = value;
6507 half[(j * kb) + i] =
conj_of(value);
6511 gemm(m, kb, kb, l21, n, half.data(), kb, c21, n);
6513 const std::size_t depth {2 * kb};
6514 left.resize(m * depth);
6515 right.resize(depth * m);
6516 for (std::size_t r {0}; r < m; ++r) {
6517 for (std::size_t q {0}; q < kb; ++q) {
6518 left[(r * depth) + q] = -c21[(r * n) + q];
6519 left[(r * depth) + kb + q] = -l21[(r * n) + q];
6520 right[(q * m) + r] =
conj_of(l21[(r * n) + q]);
6521 right[((kb + q) * m) + r] =
conj_of(c21[(r * n) + q]);
6524 T*
const c22 {c + (k1 * n) + k1};
6528 gemm(rows, r0 + rows, depth, left.data() + (r0 * depth), depth, right.data(), m, c22 + (r0 * n), n);
6530 gemm(m, kb, kb, l21, n, half.data(), kb, c21, n);
6534 const std::size_t below {(std::max(n, std::size_t {1}) - 1) /
pencil_block};
6538 const std::size_t m {n - k1};
6540 triangular_halves(l + (k1 * n) + k1, n,
true,
false,
false, c + (k1 * n) + k0, n,
pencil_block, 0, m, minus.data());
6553 template <
typename T>
6561 template <
typename T>
6569 for (std::size_t i {0}; i < n; ++i) {
6570 for (std::size_t j {0}; j < i; ++j) {
6571 y[(j * n) + i] =
conj_of(y[(i * n) + j]);
6576 for (std::size_t i {0}; i < n; ++i) {
6577 for (std::size_t j {0}; j < i; ++j) {
6578 y[(j * n) + i] =
conj_of(y[(i * n) + j]);
6583 for (std::size_t i {0}; i < n; ++i) {
6584 for (std::size_t j {0}; j < n; ++j) {
6585 c[(i * n) + j] =
conj_of(y[(j * n) + i]);
6599 template <
typename T>
6609 : factor(checked_factor(a, b)),
6610 reduced(standard_form(a, factor))
6616 const std::size_t n {factor.rows()};
6617 const std::size_t k {v.cols()};
6632 throw dimension_error(
"a definite pencil requires two square matrices of one order");
6641 const std::size_t n {a.
rows()};
6643 for (std::size_t i {0}; i < n; ++i) {
6644 for (std::size_t j {0}; j < i; ++j) {
6645 y[(i * n) + j] = a(i, j);
6647 y[(i * n) + i] = T {
real_part(a(i, i))};
6686 eigen_method method = eigen_method::divide_and_conquer)
6700 eigen_method method = eigen_method::divide_and_conquer)
6703 if (input.cols() != n_) {
6704 throw dimension_error(
"symmetric eigendecomposition requires a square matrix");
6706 detail::require_finite_lower(input,
"symmetric eigendecomposition");
6711 for (std::size_t i {0}; i < n_; ++i) {
6712 for (std::size_t j {0}; j <= i; ++j) {
6713 scale = std::max(scale, std::abs(input(i, j)));
6716 scale = detail::power_of_two_scale(scale);
6719 for (std::size_t i {0}; i < n_; ++i) {
6720 for (std::size_t j {0}; j <= i; ++j) {
6721 a[(i * n_) + j] /= scale;
6724 if (method == eigen_method::jacobi) {
6726 for (std::size_t i {0}; i < n_; ++i) {
6727 v[(i * n_) + i] = 1.0;
6728 for (std::size_t j {i + 1}; j < n_; ++j) {
6729 a[(i * n_) + j] = a[(j * n_) + i];
6732 detail::cyclic_jacobi(a, v, n_, detail::jacobi_sweeps);
6733 for (std::size_t i {0}; i < n_; ++i) {
6734 diagonal[i] = a[(i * n_) + i] * scale;
6739 for (std::size_t i {0}; i < n_; ++i) {
6740 std::fill(a.begin() +
static_cast<std::ptrdiff_t
>((i * n_) + i + 1), a.begin() +
static_cast<std::ptrdiff_t
>((i + 1) * n_), 0.0);
6746 if (method == eigen_method::tridiagonal_ql) {
6747 zt = detail::tridiagonal_basis(reduction, n_);
6748 detail::tridiagonal_ql(
diagonal, off, zt, n_, detail::ql_steps_per_value * n_);
6751 zt = detail::tridiagonal_divide_and_conquer(
diagonal, off, reduction, n_);
6754 const std::vector<std::size_t> order {detail::ascending_order(
diagonal)};
6756 for (std::size_t c {0}; c < n_; ++c) {
6757 values[c] =
diagonal[order[c]] * scale;
6760 vectors_ =
matrix<double> {n_, n_, detail::columns_by_value(zt, order, n_)};
6777 eigen_method method = eigen_method::divide_and_conquer)
6797 return std::move(vectors_);
6808 vectors_ = pencil.
vectors_of(std::move(vectors_));
6815 std::vector<std::size_t> order(n_);
6816 for (std::size_t i {0}; i < n_; ++i) {
6819 std::sort(order.begin(), order.end(),
6820 [&
diagonal](std::size_t x, std::size_t y) {
6821 return diagonal[x] < diagonal[y];
6825 for (std::size_t col {0}; col < n_; ++col) {
6826 values[col] =
diagonal[order[col]];
6827 for (std::size_t row {0}; row < n_; ++row) {
6828 vectors[(row * n_) + col] = v[(row * n_) + order[col]];
6866 eigen_method method = eigen_method::divide_and_conquer)
6869 if (method == eigen_method::jacobi) {
6870 throw argument_error(
"Hermitian eigendecomposition: the Jacobi method is for real symmetric matrices");
6872 if (input.cols() != n_) {
6873 throw dimension_error(
"Hermitian eigendecomposition requires a square matrix");
6875 detail::require_finite_lower(input,
"Hermitian eigendecomposition");
6880 for (std::size_t i {0}; i < n_; ++i) {
6881 for (std::size_t j {0}; j < i; ++j) {
6882 scale = std::max(scale, std::abs(input(i, j)));
6884 scale = std::max(scale, std::abs(input(i, i).real()));
6886 scale = detail::power_of_two_scale(scale);
6888 for (std::size_t i {0}; i < n_; ++i) {
6889 for (std::size_t j {0}; j <= i; ++j) {
6890 a[(i * n_) + j] = (i == j ? std::complex<double> {input(i, j).real(), 0.0} : input(i, j)) / scale;
6898 if (method == eigen_method::tridiagonal_ql) {
6899 zt = detail::tridiagonal_basis(reduction, n_);
6900 detail::tridiagonal_ql(
diagonal, off, zt, n_, detail::ql_steps_per_value * n_);
6903 zt = detail::tridiagonal_divide_and_conquer(
diagonal, off, reduction, n_);
6906 const std::vector<std::size_t> order {detail::ascending_order(
diagonal)};
6908 for (std::size_t c {0}; c < n_; ++c) {
6909 values[c] =
diagonal[order[c]] * scale;
6929 const matrix<std::complex<double>>& b,
6930 eigen_method method = eigen_method::divide_and_conquer)
6931 :
hermitian_eigen(detail::definite_pencil<std::complex<double>> {a, b},
6950 return std::move(vectors_);
6961 vectors_ = pencil.vectors_of(std::move(vectors_));
#define NUMERICAL_OUT_OF_LINE
Thrown when an argument is outside what an operation takes (a tolerance below 0, an FFT type past 4).
A Cholesky factorisation A = L Lᴴ of a Hermitian positive-definite matrix.
matrix< T > solve(const matrix< T > &b) const
Solves A X = B for every column of b at once: L Y = B, then Lᴴ X = Y, row by row, each row of the sol...
cholesky_decomposition(matrix< T > &&a)
Factorises a in its own storage, an expiring matrix's elements taken over: no copy of them.
vector< T > solve(const vector< T > &b) const
Solves A x = b via L y = b then Lᴴ x = y.
std::size_t n_
The matrix order.
cholesky_decomposition(const matrix< T > &a)
Factorises a.
double reciprocal_condition(double one_norm) const
The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of the factorised matrix, as LAPACK's pocon: ‖A⁻¹‖₁...
matrix< T > lower() &&
The lower-triangular factor L, moved out of an expiring decomposition.
void factor_rows_together(std::size_t i, std::size_t k0)
The columns [k0, i) of the detail::cholesky_diagonal_rows rows from i, together: each element depends...
void factor_row(std::size_t i, std::size_t k0, std::size_t first, std::size_t last)
Row i of L in the columns [first, last), the terms of the columns before k0 already subtracted: the u...
T determinant() const
The determinant — the product of the squared diagonal of L (real, positive), its partial products kep...
void factor_rows_below(std::size_t k0, std::size_t end, buffer< T > &minus_adjoint)
The rows below the panel [k0, end), L₂₁ = A₂₁ L₁₁⁻ᴴ: chunks of detail::cholesky_rows rows in parallel...
matrix< T > lower() const &
The lower-triangular factor L (with L Lᴴ == A).
void update_trailing(std::size_t k0, std::size_t end, const buffer< T > &minus_adjoint, buffer< T > &packing)
A22 += L21 (−L21ᴴ), by tiles of detail::cholesky_update_columns columns and detail::cholesky_update_r...
buffer< T > lower_
The lower-triangular factor L, row-major (upper triangle zero).
Thrown when an iterative algorithm has not converged within its bound of sweeps.
convergence_error(const std::string &message)
Builds the error.
A standard exception Std that numerical::error tags too, its one what answering for both bases.
Thrown when an operation's operands have incompatible shapes.
The eigenvalues and eigenvectors of a complex Hermitian matrix.
hermitian_eigen(const detail::definite_pencil< std::complex< double > > &pencil, eigen_method method)
The pencil's eigenpairs: its standard form's, the vectors carried back.
matrix< std::complex< double > > vectors_
Eigenvectors as columns.
hermitian_eigen(const matrix< std::complex< double > > &input, eigen_method method=eigen_method::divide_and_conquer)
Diagonalises input.
const matrix< std::complex< double > > & vectors() const &noexcept
The eigenvectors as columns, ordered to match values.
hermitian_eigen(const matrix< std::complex< double > > &a, const matrix< std::complex< double > > &b, eigen_method method=eigen_method::divide_and_conquer)
Diagonalises the pencil A − λ B, A x = λ B x, as scipy.linalg.eigh(a, b): B = L Lᴴ and the Hermitian ...
std::size_t n_
The matrix order.
matrix< std::complex< double > > vectors() &&
The eigenvectors, moved out of an expiring decomposition.
vector< double > values_
Eigenvalues, ascending.
const vector< double > & values() const noexcept
The eigenvalues, ascending.
An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of ...
T determinant() const
The determinant (the pivot sign times the product of U's diagonal; 0 if singular).
void swap_rows_outside(std::size_t a, std::size_t b, std::size_t k0, std::size_t end)
Swaps rows a and b of the factor outside the panel's columns [k0, end): right of the panel up to swap...
std::vector< std::pair< std::size_t, std::size_t > > deferred_swaps_
Swaps left for the columns past it.
matrix< T > factors() const &
L and U in one matrix, as LAPACK's dgetrf leaves them: U on and above the diagonal,...
void update_columns(const detail::packed_left< T > &left, std::size_t k0, std::size_t c0, std::size_t c1)
A₂₂ −= L₂₁ U₁₂ on the trailing columns [c0, c1), as A₂₂ += (−L₂₁) U₁₂ through the matrix product kern...
void solve_rows(buffer< T > &y, std::size_t cols, bool lower=false) const
Performs the pivoted elimination, filling lu_ and pivots_.
std::size_t column_slices(std::size_t cols) const
The column slices solve_rows splits cols right-hand sides into, one a thread, each of detail::slice_c...
const std::vector< std::size_t > & pivots() const noexcept
The row permutation: row i of P A = L U is row pivots()[i] of A.
void factorize_columns(buffer< T > &panel, std::size_t rows, std::size_t first, std::size_t last, std::size_t k0, std::size_t end)
Factorises the columns [first, last) of the panel (column-major, rows rows), every row from first dow...
lu_decomposition(const matrix< T > &a)
Factorises a (in place, into combined L\U with a row permutation).
std::size_t panel_of(std::size_t i) const noexcept
The first row of the panel that holds row i.
vector< T > solve(const vector< T > &b) const
Solves A x = b using the stored factors.
matrix< T > factors() &&
factors, moved out of an expiring decomposition: no copy.
double reciprocal_condition(double one_norm) const
The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of the factorised matrix, as LAPACK's gecon: ‖A⁻¹‖₁...
matrix< T > solve(matrix< T > &&b) const
solve on an expiring b, in its own storage: its rows permuted in place (cycle by cycle of the pivots,...
buffer< T > lu_
Combined L (below diag, unit) and U (on/above), row-major.
void solve_columns(std::size_t k0, std::size_t end, std::size_t first, std::size_t last)
The rows [k0, end) of U₁₂ on the columns [first, last), against the panel's unit-lower L: each column...
void negated_block_into(buffer< T > &out, std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1) const
negated_block into out, resized to it.
std::size_t lower_slice_start(std::size_t s, std::size_t slices, std::size_t cols) const
The first column of slice s of slices (slices itself: cols) where the forward pass is lower: column c...
matrix< T > pivoted_inverse(buffer< T > storage) const
(P A)⁻¹ = U⁻¹ L⁻¹, the inverse of the rows in their pivoted order, in storage (its elements discarded...
void transpose_panel(buffer< T > &panel, std::size_t rows, std::size_t k0, std::size_t end, bool in)
Copies the columns [k0, end) of the factor, every row from k0, into panel (column-major,...
std::vector< std::size_t > pivots_
Row permutation: row now at i came from pivots_[i].
void solve_panel_rows(std::size_t k0, std::size_t end)
U₁₂ = L₁₁⁻¹ A₁₂: the panel's rows right of it, by forward substitution with its unit-lower L....
void swap_left_columns()
Applies left_swaps_ to the columns left of each swap's panel: a panel's columns take,...
void subtract_block(buffer< T > &y, std::size_t cols, std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1, std::size_t first, std::size_t last) const
Y[r0, r1) −= F[r0, r1) × [c0, c1) · Y[c0, c1), F the factor, through the matrix product kernel (nothi...
std::size_t block_
The panel width.
matrix< T > inverse(buffer< T > storage) const
inverse in storage, its elements discarded: no fresh n × n mapped and faulted in where it holds that ...
int sign_
Permutation sign, for the determinant.
void solve_columns(buffer< T > &y, std::size_t cols, std::size_t c0, std::size_t c1, bool lower) const
solve_rows on the columns [c0, c1) of y (n × cols, row-major): the blocked passes,...
bool singular() const noexcept
Whether a pivot was zero: U is singular, and solve and inverse throw.
void factorize_panel(buffer< T > &panel, std::size_t k0, std::size_t end)
Unblocked LU with partial pivoting of the columns [k0, end), every row below k0.
std::pair< T, double > log_determinant() const
The determinant as its unit-modulus sign and the natural logarithm of its magnitude,...
std::size_t n_
The matrix order.
bool singular_
Set if a zero pivot was met.
std::size_t swap_limit_
The columns a panel's row swaps reach now.
void factorize_trailing(buffer< T > &panel, std::size_t first_end)
The panels after the first (whose columns end at first_end), each with its trailing update....
matrix< T > solve(const matrix< T > &b) const
Solves A X = B for every column of b at once.
std::vector< std::pair< std::size_t, std::size_t > > left_swaps_
Swaps left for the columns before their panel.
matrix< T > inverse() const
The inverse, U⁻¹ L⁻¹ P, by blocks of rows through the matrix product kernel: L⁻¹ from the identity,...
lu_decomposition(matrix< T > &&a)
Factorises a in its own storage, an expiring matrix's elements taken over: no copy of them.
void solve_narrow(buffer< T > &y, std::size_t cols) const
solve_rows for a few right-hand sides: row by row, each one's terms in the order the blocked passes g...
buffer< T > negated_block(std::size_t r0, std::size_t r1, std::size_t c0, std::size_t c1) const
The rows [r0, r1) and columns [c0, c1) of the factor, negated, row-major and contiguous.
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...
non_finite_error(const std::string &message)
Builds the error.
Thrown when a Cholesky factorisation finds the matrix not positive-definite.
std::size_t order() const noexcept
The order of the first leading minor found not positive definite (LAPACK's info), 0 where unknown.
std::size_t order_
The order of the failing leading minor, or 0.
not_positive_definite_error(const std::string &message, std::size_t order=0)
Builds the error.
A QR factorisation with column pivoting A P = Q R of an m × n matrix, as scipy.linalg....
pivoted_qr_decomposition(const matrix< T > &a, qr_mode mode=qr_mode::reduced)
Factorises a: Q m × k and R k × n (k = min(m, n)), or Q m × m and R m × n (mode complete).
std::vector< std::size_t > permutation_
P, by its columns' origins.
const matrix< T > & r() const noexcept
R, upper trapezoidal, its diagonal real, non-negative and not increasing: k × n, or m × n.
const matrix< T > & q() const noexcept
Q, orthonormal columns: m × k, or m × m complete.
std::size_t factor_block(buffer< T > &w, std::size_t m, std::size_t n, std::size_t start, std::size_t width, buffer< double > ¤t, buffer< double > &reference, std::vector< buffer< T > > &reflectors, std::vector< T > &taus)
Up to width steps from column start of the column-major m × n w, as LAPACK's laqps: the reflections k...
const std::vector< std::size_t > & permutation() const noexcept
The column permutation: column j of A P is column permutation()[j] of A, as SciPy's P.
A QR factorisation A = Q R of an m × n matrix, as NumPy's qr, reduced by default.
vector< T > solve(const vector< T > &b) const
The least-squares solution of A x ≈ b (x = R⁻¹ Qᴴ b) for a full-rank A.
std::size_t depth_
min(m, n).
qr_decomposition(matrix< T > &&a, qr_mode mode=qr_mode::reduced)
Factorises a in its own storage, an expiring matrix's elements taken over: no copy of them.
std::size_t cols_
The number of columns (n).
qr_decomposition(const matrix< T > &a, qr_mode mode=qr_mode::reduced)
Factorises a.
std::size_t width_
Q's columns and R's rows: k, or m complete.
std::size_t rows_
The number of rows (m).
matrix< T > q() &&
Q, moved out of an expiring decomposition (r stays).
matrix< T > q() const &
The factor Q (orthonormal columns): m × k, k = min(m, n), or m × m complete.
buffer< T > q_
The factor Q, row-major, m × width_.
buffer< T > r_
The upper-trapezoidal factor R, row-major, width_ × n.
matrix< T > r() &&
R, moved out of an expiring decomposition (q stays).
matrix< T > solve(const matrix< T > &b) const
The least-squares solutions of A X ≈ B (X = R⁻¹ Qᴴ B) for a full-rank A, every column of b at once: Q...
matrix< T > r() const &
The upper-trapezoidal factor R: k × n, k = min(m, n), or m × n complete.
The magnitude at or under which a singular value counts as zero, in a rank (matrix_rank),...
constexpr rank_cutoff() noexcept=default
NumPy's default: the largest singular value times the machine epsilon times the larger dimension.
static rank_cutoff absolute(double magnitude)
magnitude itself, whatever the largest singular value.
static double checked(double value)
constexpr rank_cutoff(double value, bool absolute) noexcept
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.
Thrown when a matrix has no unique solution (it is singular).
singular_matrix_error(const std::string &message)
Builds the error.
The eigenvalues and eigenvectors of a real symmetric matrix.
matrix< double > vectors_
Eigenvectors as columns.
const matrix< double > & vectors() const &noexcept
The eigenvectors as columns, ordered to match values.
matrix< double > vectors() &&
The eigenvectors, moved out of an expiring decomposition.
void extract_sorted(const buffer< double > &diagonal, const buffer< double > &v)
Sorts the eigenvalues diagonal ascending and reorders v's columns to match.
symmetric_eigen(detail::definite_pencil< double > pencil, eigen_method method)
The pencil's eigenpairs: its standard form's, the vectors carried back.
symmetric_eigen(matrix< double > &&input, eigen_method method=eigen_method::divide_and_conquer)
Diagonalises input in its own storage, an expiring matrix's elements taken over: its scaled copy is m...
symmetric_eigen(const matrix< double > &input, eigen_method method=eigen_method::divide_and_conquer)
Diagonalises input.
vector< double > values_
Eigenvalues, ascending.
std::size_t n_
The matrix order.
symmetric_eigen(const matrix< double > &a, const matrix< double > &b, eigen_method method=eigen_method::divide_and_conquer)
Diagonalises the pencil A − λ B, A x = λ B x, as scipy.linalg.eigh(a, b): B = L Lᴴ and the symmetric ...
const vector< double > & values() const noexcept
The eigenvalues, ascending.
A dense vector of T with value semantics.
buffer< T >::const_iterator end() const noexcept
Const iterator past the last element.
std::size_t size() const noexcept
The number of elements.
buffer< T >::const_iterator begin() const noexcept
Const iterator to the first element.
The scalar types NumericAL's factorisations and solvers take: a field of floating-point numbers,...
#define NUMERICAL_UNROLL_BLOCK
A dense, row-major, value-semantic matrix over a scalar type.
constexpr std::size_t gemm_packed_threshold
Below this many multiply-adds the plain loop (gemm_rows, by blocks of rows held in registers) runs in...
T symmetric_row(const T *row, const T *v, const T &f, T *out, std::size_t count)
Σ row[i] · v[i] and out[i] += row[i] · f, in order, for a type no native vector holds.
constexpr std::size_t lu_tall_ratio
The ratio of rows to columns up to which lu_factors factorises a tall matrix as the square of it besi...
constexpr std::size_t lu_lookahead_columns
The trailing columns at most past which the LU factorises its next panel beside the update of the res...
constexpr std::size_t qr_transpose_tile
The side of the tiles in which the QR transposes (transpose_into): a tile's rows and columns both sta...
constexpr std::size_t qr_update_slice
The fewest columns a task of reflect_in_columns' look-ahead updates: each task repacks the block,...
constexpr carried_t< T > rescue_below
The magnitude under which rescue_factor scales a T up: about the square root of the smallest normal n...
constexpr std::size_t lu_block_for(std::size_t n) noexcept
The panel width of the LU of order n: a power of two, so a row's panel is a mask away,...
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
double reciprocal_condition(std::size_t n, double one_norm, const std::function< void(T *, bool)> &apply)
The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of A from one_norm, ‖A‖₁, and an estimate of ‖A⁻¹‖₁...
void factor_qr_panel(T *panel, std::size_t ld, std::size_t top, std::vector< buffer< T > > &reflectors, std::vector< T > &taus, std::size_t k0, std::size_t k1)
Householder reflections of the columns k0…k1-1 of a column-major matrix, rows from k0,...
constexpr std::size_t cholesky_update_rows
The rows of one tile of a Cholesky update: the tiles of a panel's update, each one product on one thr...
double contiguous_norm(const T *x, std::size_t count)
The 2-norm of the count entries at x, scaled by the largest so no square overflows or underflows.
T scaled_product(T start, std::size_t count, const Factor &factor)
The product of count factors, factor(i) for each i, times start, as a determinant multiplies its pivo...
R part_size(R x)
The magnitude of a real x, x's exponent read from it.
bool all_finite_shared(const double *x, std::size_t count)
all_finite on the threads by chunks of finite_chunk, past two of them: a pass bound by the memory,...
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...
constexpr std::size_t cholesky_block
The columns of one panel of the blocked Cholesky factorisation (as lu_block).
void parallel_for_beside(std::size_t count, std::size_t work_per_index, const Body &body, const Side &side)
Runs side on the caller while the pool's workers run body(i) for every i in [0, count),...
bool same_sign(R x, int sign) noexcept
Whether a real entry's sign is sign (sign_entry's), as dlacn2 finds a sign vector repeated.
bool triangle_is_finite(const T *a, std::size_t n, bool lower)
Whether the triangle of the row-major n × n a a solve reads (the diagonal with it) is finite,...
R sign_entry(R x, int &sign) noexcept
A real entry's sign for one_norm_estimate's sign vectors, dlacn2's: 1 from zero up,...
bool lower_is_finite(const matrix< T > &a)
Whether the lower triangle of the square a, and its diagonal's real part, are finite: entry by entry,...
void tridiagonal_root_free_ql(buffer< double > &d, buffer< double > &e, std::size_t n, std::size_t max_steps)
The eigenvalues of the symmetric tridiagonal (d, e), no vector, as LAPACK's dsterf: the Pal–Walker–Ka...
void form_q_into(buffer< T > &out, const std::vector< reflector_block< T > > &blocks, std::size_t rows, std::size_t first, std::size_t count, bool transposed)
The columns [first, first + count) of Q = H₀ H₁ …, the blocks applied (the last first) to those of th...
constexpr std::size_t lu_update_speedup
The multiply-adds of an LU's trailing update one of the tile's dependent ones stands for,...
void subtract_corrections(T *y, const T *f, const T *x, std::size_t ldx, std::size_t terms, std::size_t count)
subtract_products of a real T, where the reduction's corrections are those of its type.
void apply_q(buffer< T > &p, const std::vector< reflector_block< T > > &blocks, std::size_t rows, std::size_t count)
P ← Q P for the rows × count row-major p, Q = H₀ H₁ … the product of the blocks' reflectors,...
void add_conjugate_product(T *y, const T *x, const T &f, std::size_t count)
y[i] += conj(x[i]) · f for a real T, where the conjugate is the value: add_product.
void subtract_rows(double *y, std::size_t ldy, const double *f, std::size_t ldf, const double *x, std::size_t ldx, std::size_t terms, std::size_t count)
subtract_rows for double, the units chosen as subtract_products chooses them: each element the value ...
@ plain
gemm_rows, or a scalar whose products are not shared: A is read in place.
T conjugate_dot_product(const T *x, const T *y, std::size_t count)
Σ conj(x[i]) · y[i], in order, where no native vector holds the parts.
std::optional< matrix< double > > mixed_precision_solve(const matrix< double > &a, const matrix< double > &b, double *reciprocal_condition=nullptr)
X of A X = B (A square, B of its rows) as LAPACK's dsgesv: A factorised in single precision,...
constexpr std::size_t cholesky_together_width
The narrowest Cholesky diagonal block whose rows go together: in a block of 8, the groups' loops cost...
void reduce_pencil(T *c, const T *l, std::size_t n)
The lower triangle of the Hermitian n × n c (row-major) taken to L⁻¹ C L⁻ᴴ for the lower-triangular l...
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.
constexpr double plain_squares_low
The smallest plain sum of squares plain_or_at_scale keeps: a term that underflowed is below 2⁻¹⁰²²,...
constexpr std::size_t gemm_kernel_speedup
The multiply-adds the register tile does in the time of one in work_per_thread's dependent chain (abo...
constexpr std::size_t symmetric_row_group
The rows of a lower triangle symmetric_rows takes at once.
symmetric_two_by_two symmetric_eigen_2x2(double a, double b, double c) noexcept
The eigensystem of [a b; b c] as LAPACK's dlaev2 computes it: the larger eigenvalue in magnitude from...
std::size_t parallel_threads(std::size_t count, std::size_t work_per_index)
The threads parallel_for shares count indices of work_per_index out to (threads_for): the hardware's,...
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.
constexpr std::size_t divide_leaf
The order up to which tridiagonal_divide_and_conquer diagonalises by implicit QL.
carried_t< T > real_part(const T &x)
The real part of a real (or general) scalar, in carried_t.
void gemm_at(std::size_t m, std::size_t n, std::size_t k, const T *at, std::size_t ldat, const T *b, std::size_t ldb, T *c, std::size_t ldc, c_start start=c_start::kept)
gemm_layouts with A given as Aᵀ (at, k × m, ldat apart).
std::pair< matrix< T >, matrix< T > > split_lu(const T *lu, std::size_t rows, std::size_t cols, std::size_t k)
The rows of lu (rows × cols row-major, L below its diagonal, U on and above) as L,...
T square(const T &x)
x · x, by the type's own product (a complex one's C Annex G, as the library's *).
T operator_times(const T &a, const T &b)
a · b, as std::operator* computes it, in line. libc++'s complex product (the four products and their ...
constexpr std::size_t vector_speedup
The multiply-adds a vectorised inner loop does in the time of one in work_per_thread's dependent chai...
void merge_rank_one(buffer< double > &d, buffer< double > z, double rho, double *q, std::size_t ldq, std::size_t n, std::size_t split, merge_workspace &work)
The eigenvalues of diag(d) + ρ z zᵀ, ascending, into d, and its eigenvectors times q (the row-major n...
void require_finite_triangle(const T *a, std::size_t n, bool lower, const T *x, std::size_t count)
Refuses an infinite or NaN entry of the triangle of a a triangular solve reads, or of its right-hand ...
constexpr std::size_t slice_columns
The fewest columns an LU solve gives a thread of its own: a narrower slice starves the product kernel...
constexpr std::size_t cholesky_update_columns
The fewest columns of the trailing block one Cholesky update's product takes: each product packs ever...
void add_product(double *y, const double &f, const double *x, std::size_t count)
y[i] += f · x[i] for double, as subtract_product.
constexpr std::size_t jacobi_sweeps
The sweeps a Jacobi method may take: it converges quadratically, in under 15 on every matrix measured...
R times_power_of_two(R x, int e)
x times 2ᵉ, rounded once (a power of 2 scales a normal number exactly).
std::array< double, symmetric_row_group >(*)(const double *, std::size_t, const double *, double *, std::size_t) symmetric_rows_kernel
A kernel of symmetric_rows' form: symmetric_rows itself, or an x86-64 one.
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 require_finite(const matrix< T > &a, const char *what)
The one non-finite policy, checked where every decomposition starts.
T hermitian_row(symmetric_row_kernel, const T *row, const T *v, T *out, std::size_t i)
Row i's terms of a Hermitian product from the lower triangle: out[j] += conj(row[j]) v[i] for j < i,...
constexpr std::size_t tridiagonal_block
The reflections of one panel of the blocked tridiagonal reduction.
void tridiagonal_ql(buffer< double > &d, buffer< double > &e, buffer< T > &zt, std::size_t n, std::size_t max_steps)
The eigenvalues of the symmetric tridiagonal (d, e) by implicit QL or QR as LAPACK's dsteqr,...
carried_t< T > rescue_factor(carried_t< T > largest)
The exact power of two that brings a magnitude below about the square root of the smallest normal num...
constexpr std::size_t work_per_thread
The work one thread must have to pay for starting it: about 60 µs of multiply-adds,...
double secular_root(const buffer< double > &d, const buffer< double > &z, double rho, std::size_t i, std::size_t max_iterations, double *delta)
Root i of 1/ρ + Σⱼ zⱼ²/(dⱼ − λ) = 0 (d strictly ascending, ‖z‖ = 1), the i-th eigenvalue of diag(d) +...
void parallel_copy(const T *in, std::size_t count, T *out)
Copies the count elements at in to out, split across the threads the work pays for,...
buffer< T > tridiagonal_basis(const tridiagonal_reduction< T > &reduction, std::size_t n)
Mᵀ of a reduction, row-major (its rows are the columns of M): Qᵀ by blocks of reflectors from the las...
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...
constexpr std::size_t ql_steps_per_value
The implicit QL steps the tridiagonal eigensolver may take per eigenvalue, as LAPACK's dsteqr bounds ...
void gemm_with(const packed_left< T > &left, std::size_t n, const T *b, std::size_t ldb, T *c, std::size_t ldc)
C += A·B for the packed left (pack_left) and the k × n b, as gemm computes it, A read in place here,...
T conj_of(const T &x)
The conjugate of a real (or general) scalar — the value itself.
std::vector< rotation_run > rotation_runs(const std::vector< row_operation > &operations)
The operations split into runs of chained rotations, every other operation a run of one.
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 ...
constexpr std::size_t cholesky_block_for(std::size_t n) noexcept
The panel width of the Cholesky factorisation of order n: narrower up to order 256,...
double cholesky_reciprocal_condition(const T *factor, std::size_t n, bool lower, double one_norm)
reciprocal_condition of A = L Lᴴ or Uᴴ U from its Cholesky factor, L in the lower triangle of the n ×...
buffer< T > pencil_standard_form(buffer< T > y, const T *lower, std::size_t n, bool blocks)
C = L⁻¹ A L⁻ᴴ whole, y holding A's lower triangle (n × n, row-major, the diagonal real) and lower L: ...
void factor_row_major_panel(buffer< T > &a, std::size_t rows, std::size_t cols, std::vector< buffer< T > > &reflectors, std::vector< T > &taus, std::size_t k0, std::size_t k1)
factor_qr_panel on the columns k0…k1-1 of the row-major a, rows from k0, in a column-major copy of th...
constexpr std::size_t lu_wide_block
The columns of one panel of the LU from lu_wide_order.
constexpr std::size_t tridiagonal_band
The rows of each band of the tridiagonal reduction's trailing update: a band reaches its diagonal,...
double triangular_reciprocal_condition(const T *a, std::size_t n, bool lower)
reciprocal_condition of the triangular A, the lower triangle of the n × n row-major a or its upper on...
void tall_lu_columns(T *panel, std::size_t m, std::size_t n, std::size_t first, std::size_t last, std::vector< std::size_t > &rows)
Factorises the columns [first, last) of the m × n column-major panel (m ≥ n; column j at panel[j m]) ...
constexpr std::size_t narrow_solve
The most right-hand sides an LU solve takes row by row rather than by blocks through the product kern...
constexpr std::size_t lu_small_order
The order up to which the LU takes panels of lu_small_block columns: there the panels,...
void transpose_into(const T *from, std::size_t rows, std::size_t cols, T *to)
The row-major rows × cols from into to as its transpose, cols × rows row-major, by tiles,...
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,...
@ tiles
The x86-64 complex tiles': each part's product from zero, re·re − im·im and re·im + im·re,...
@ 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,...
constexpr std::size_t pencil_block
The columns reduce_pencil reduces a block at a time, as LAPACK's sygst by its block size.
void subtract_product(double *y, const double &f, const double *x, std::size_t count)
y[i] −= f · x[i] for double on the widest x86-64 units the matrix product's kernel may use (gemm_path...
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...
void solve_divide_subtree(std::vector< divide_node > &nodes, std::size_t index, merge_workspace &work)
Solves the block index of nodes and everything below it, each block right after its halves.
packed_left< T > pack_left(std::size_t m, std::size_t, std::size_t k, const T *a, std::size_t lda, buffer< T > &)
The m × k a packed once for products with it of about n columns each (gemm_with), in storage (grown a...
std::pair< matrix< float >, int > scaled_to_float(const matrix< double > &m)
The finite m times 2⁻ᵉ in single precision, 2ᵉ the least power of two above its largest magnitude: ev...
magnitude_t< T > pivot_magnitude(const T &x)
The magnitude partial pivoting compares: |x| of a real x.
constexpr std::size_t finite_chunk
The elements all_finite_shared gives a thread at a time.
std::array< T, symmetric_row_group > symmetric_rows(const T *rows, std::size_t n, const T *v, T *out, std::size_t i)
symmetric_rows one column at a time, for a type no native vector holds.
double rank_tolerance(double largest, std::size_t rows, std::size_t cols)
The magnitude under which a diagonal entry of R or a singular value counts as zero,...
double quadratic_step(double a, double b, double c)
The smaller root η of C η² − A η + B = 0, in the form that does not cancel: a step of solve_secular's...
void triangular_halves(const T *a, std::size_t n, bool lower, bool transposed, bool unit, T *x, std::size_t ldx, std::size_t k, std::size_t first, std::size_t last, T *minus)
A X = B in place in x (n × k, row-major), for the n × n row-major triangle of a, its lower one or its...
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,...
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 subtract_term(T &sum, const T &a, const T &b)
sum −= a · b in one statement, which the compiler may fuse (as it fuses the matrix solve's).
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...
double plain_or_at_scale(double plain, const T *x, std::size_t count)
√plain, the plain sum of the squares of the count elements at x, where it neither overflowed nor unde...
buffer< T > columns_by_value(const buffer< T > &zt, const std::vector< std::size_t > &order, std::size_t n)
The n × n row-major matrix whose column c is row order[c] of zt (the eigenvectors as rows): by tiles,...
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).
constexpr std::size_t lu_fused_columns
The trailing columns at most past which each block of the update beside the panel solves its own rows...
bool climb_ends(R last, R largest) noexcept
Whether the climb's last column last is as large as the new largest entry largest,...
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...
void hermitian_product(const T *block, std::size_t n, std::size_t m, const T *v, T *w, buffer< T > &scratch)
w = B v for the Hermitian m × m block (row stride n) from its lower triangle alone,...
decltype(std::abs(std::declval< const T & >())) magnitude_t
The type std::abs gives for a T: the real type of a complex one, T itself otherwise.
constexpr std::size_t lu_wide_order
The order from which the LU takes panels of lu_wide_block columns: each trailing update rereads the w...
constexpr bool real_rows
Whether a solve of T goes by rows of real terms (lu_decomposition's solve_narrow): double and float.
T over_pivot(const T &x, const T &divisor)
x over the pivot whose pivot_divisor is divisor: the same quotient wherever the LU takes it.
gemm_path gemm_path_current() noexcept
The path the next double product takes: the most capable one under the cap that runs here (each path'...
std::vector< std::size_t > ascending_order(const buffer< double > &diagonal)
The indices of diagonal by ascending value.
void solve_divide_leaf(const divide_node &node)
Solves the leaf node by implicit QL: its eigenvalues ascending into its diagonal, their eigenvectors ...
void reduce_pencil_columns(T *c, std::size_t ldc, const T *l, std::size_t ldl, std::size_t n)
The lower triangle of the n × n c (row stride ldc) taken to L⁻¹ C L⁻ᴴ for the lower-triangular l (row...
void release_large_workspace(merge_workspace &work)
Releases the buffers of work longer than kept_workspace.
bool elements_finite(const T *x, std::size_t count)
Whether the count elements at x are finite, one at a time: a type no vectorised pass takes.
constexpr std::size_t qr_look_ahead_threads
The fewest threads for which reflect_in_columns looks ahead, a panel factorised while the threads upd...
plane_rotation_real plane_rotation_to_zero(double f, double g) noexcept
The rotation that takes (f, g) to (r, 0), as LAPACK's dlartg: r of f's sign, c 0 or more; none for g ...
constexpr std::size_t lu_small_block
The columns of one panel of the LU of an order up to lu_small_order.
double real_subdiagonal(double t, double, double &)
A real subdiagonal entry of the tridiagonal: kept with its sign (the rotations take any sign).
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 = β ...
void subtract_panel_columns(T *column, const T *columns, std::size_t height, const T *l, std::size_t terms)
column −= Σₜ x_t · conj(l[t]) over the terms columns columns (height elements each,...
constexpr std::size_t cholesky_one_panel
The order below which the Cholesky factorisation is one panel: no trailing product,...
carried_t< T > rescale_tiny(buffer< T > &x)
Scales x by rescue_factor of its largest magnitude, exactly, so that a Householder vector built from ...
bool is_finite_entry(const T &x)
Whether x is finite.
constexpr std::size_t first_touch_chunk
The elements a task of workspace_of touches first: 64 pages of 4 KiB, so a buffer of a few megabytes ...
tensor< To > converted(const tensor< From > &t)
A copy of t, each element converted to To (between a signed integer type and its unsigned one,...
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...
constexpr std::size_t solve_leaf
The columns of one leaf of the recursive LU panel.
bool all_finite(const R *x, std::size_t count) noexcept
Whether the count values at x are all finite: a NaN or an infinity has every exponent bit set,...
void triangular_rows(const T *a, std::size_t n, bool lower, bool transposed, bool unit, T *x, std::size_t k)
M X = B in place in x (n × k, row-major) for M the n × n row-major a or, transposed,...
matrix< T > parallel_copy_of(const matrix< T > &a)
A copy of a whose pages the threads fault in (parallel_copy), a decomposition's own storage: the matr...
constexpr std::size_t qr_block
The reflectors of one panel of the blocked QR.
constexpr std::size_t lu_block
The columns of one panel of the blocked LU: the trailing update, a product of this depth,...
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ᴴ) ...
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...
constexpr std::size_t corrected_product_least
The rows from which corrected_hermitian_product shares its coefficients and bands with the threads: o...
void solve_triangular_in_place(const T *a, std::size_t n, bool lower, triangular_op op, bool unit_diagonal, T *x, std::size_t k)
numerical::solve_triangular on the n × n row-major a, in place in x (n × k, row-major): the triangle ...
void join_divide_node(const divide_node &node, merge_workspace &work)
Joins the two solved halves of node by merge_rank_one, in work.
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
bool lower_triangle_product(std::size_t, std::size_t, const T *, const T *, T *, std::size_t)
C += A·B on the lower triangle of the m × m c (row stride ldc), a m × depth and b depth × m row-major...
std::vector< reflector_block< T > > reflect_in_rows(buffer< T > &a, std::size_t rows, std::size_t cols, buffer< T > *r=nullptr, bool reflectors=true)
The blocks of reflectors of a Householder QR of the row-major a (rows × cols), factorised in place as...
constexpr std::size_t product_rows
The rows of y subtract_rows takes at once.
constexpr std::size_t svd_band
The rows of an SVD's input one thread scales and copies at a time.
T over_real_diagonal(const T &x, const T &diagonal)
x over a Cholesky factor's diagonal entry diagonal, real and positive whatever the scalar.
constexpr std::size_t inverse_band
The rows an LU inverse writes its identity into, and permutes the columns of, on one thread at a time...
void plan_divide(std::vector< divide_node > &nodes, double *d, const double *e, std::size_t n, double *q, std::size_t ldq, std::size_t depth)
Appends the block (d, e, n) and, before it is solved, everything below it to nodes,...
constexpr std::size_t gemm_min_depth
Below this depth the plain loop runs too: each panel reads and writes its tiles of C once,...
constexpr std::size_t pencil_reduction_least
The order from which a pencil's standard form is reduced by blocks (reduce_pencil): half the operatio...
matrix< T > adjoint(const matrix< T > &a)
The conjugate transpose of a, as numerical::transpose copies (by blocks, on the threads).
carried_t< T > norm_at_scale(const T *x, std::size_t count)
The Euclidean norm of the count elements at x, summed at the scale of their largest magnitude: a plai...
void unscale_divide_node(const divide_node &node)
The eigenvalues of a solved node, scaled back, where its parent reads them.
double adjoint_dot(const double *x, const double *y, std::size_t count)
Σ x[i] y[i], vectorised (dot_product): xᴴ y for real numbers.
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 double plain_squares_high
The largest plain sum of squares plain_or_at_scale keeps: no term of it overflowed.
double lu_reciprocal_condition(const T *lu, std::size_t n, double one_norm)
reciprocal_condition of A = P⁻¹ L U from the n × n row-major lu (L below the diagonal,...
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,...
double one_norm_estimate(std::size_t n, const std::function< void(T *, bool)> &apply)
An estimate of ‖B‖₁ for the n × n operator apply gives, as LAPACK's dlacn2 and zlacn2 (Hager's method...
void rotate(T *x, T *y, std::size_t count, std::size_t stride, double cs, double sn)
(x, y) ← (cs x + sn y, cs y − sn x) over count pairs stride apart: a plane rotation.
merge_workspace & thread_workspace()
The calling thread's merge_workspace, kept from one decomposition to the next: mapping its pages anew...
void jacobi_rotate(buffer< double > &a, buffer< double > &v, std::size_t n, std::size_t p, std::size_t q)
One Jacobi rotation of the n × n a zeroing a[p][q], accumulated into v.
buffer< T > householder_r(buffer< T > a, std::size_t rows, std::size_t cols)
householder_qr's R alone, k × cols, k = min(rows, cols): the same reflections and the same rotation o...
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...
T from_carried(carried_t< T > x)
x, a magnitude carried in carried_t, as the scalar T: converted to T's real type first,...
buffer< T > tridiagonal_divide_and_conquer(buffer< double > &d, buffer< double > &e, const tridiagonal_reduction< T > &reduction, std::size_t n)
The eigenvalues of the tridiagonal (d, e) of reduction into d, and the matrix's eigenvectors as the r...
void solve_finite_triangular_in_place(const T *a, std::size_t n, bool lower, triangular_op op, bool unit_diagonal, T *x, std::size_t k)
solve_triangular_in_place of a triangle and a right-hand side known finite (require_finite_triangle,...
std::vector< reflector_block< T > > reflect_in_columns(buffer< T > &columns, std::size_t rows, std::size_t cols, bool reflectors=true)
The blocks of reflectors of a Householder QR of the column-major columns (rows per column,...
thin_qr< T > householder_qr(buffer< T > a, std::size_t rows, std::size_t cols, bool complete=false)
Factorises the rows × cols row-major a by Householder reflections, A = Q R with k = min(rows,...
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.
T pivot_divisor(const T &pivot)
The divisor over_pivot takes for the pivot pivot. A complex pivot's reciprocal, once,...
constexpr std::size_t zeroed_rows
The rows of a Cholesky factor whose upper part one thread zeroes at a time.
constexpr std::size_t triangular_block
The rows triangular_halves solves one by one; past them, by halves of a multiple of them.
constexpr std::size_t cholesky_rows
The rows of one chunk of a Cholesky panel's rows below it, solved together along each column.
double residual_ratio(const matrix< double > &x, const matrix< double > &r)
The largest of ‖r‖∞ / ‖x‖∞ over the columns of the residual r and the solution x (LAPACK's dsgesv com...
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,...
double(*)(const double *, const double *, double, double *, std::size_t) symmetric_row_kernel
A kernel of symmetric_row's form: symmetric_row itself, or an x86-64 one.
constexpr std::size_t cholesky_diagonal_rows
The rows of a Cholesky diagonal block factorised together, one chain of sums each (one x86-64 AVX2 co...
void gemm_rows(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 by the plain i-k-j loop (gemm_rows_rounded), each element rounded as the tile of the path in...
T conjugate_dot(const T *x, const T *y, std::size_t count)
Σ conj(x[i]) · y[i] for a real T, where the conjugate is the value: dot_product.
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,...
void corrected_hermitian_product(const T *block, std::size_t n, std::size_t m, const T *v, T *w, buffer< T > &scratch, const T *corrections, std::size_t ldc, std::size_t terms, T *factors, T *next=nullptr, const T *next_factors=nullptr)
hermitian_product corrected by a panel's earlier steps: w = B v − Σₜ fₜ cₜ, the coefficients f[2p] = ...
constexpr std::size_t triangular_slice
The columns of the right-hand sides a thread takes in triangular_halves' rows one by one.
std::size_t symmetric_row_speedup()
The weight of a symmetric row's multiply-adds in hermitian_product: on the x86-64 units,...
std::size_t largest_magnitude_vectors(const T *, std::size_t, Magnitude &, std::size_t &)
Only x[0], the one best and at come in with, for a type no native vector holds.
void cyclic_jacobi(buffer< double > &a, buffer< double > &v, std::size_t n, std::size_t max_sweeps)
Cyclic Jacobi on the full symmetric a, the rotations accumulated into v.
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).
cholesky_decomposition< T > cholesky(matrix< T > a)
Cholesky-factorises a Hermitian positive-definite matrix.
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.
T determinant(matrix< T > a)
The determinant of a square matrix.
rectangular_lu< T > lu_factors(const matrix< T > &a)
The pivoted LU factorisation A = P L U of an m × n matrix, as scipy.linalg.lu: L m × k lower trapezoi...
matrix< T > transpose(const matrix< T > &m)
The transpose, by blocks of transpose_tile (walked by detail::transpose_piece's pieces),...
gemm_path
The kernels a double matrix product can run on (a float one too on arm64), from the most portable....
@ portable
The compiler's vectors (16 bytes on x86-64 wheels), as the compiler rounds c + a·b (see gemm).
@ amx
The Apple AMX coprocessor, fused multiply-adds; the products it does not suit on the NEON path's tile...
qr_mode
The factors a numerical::qr_decomposition keeps, as numpy.linalg.qr's modes name them.
@ reduced
Q is m × k, R k × n, k = min(m, n): NumPy's default.
@ complete
Q is m × m, its columns past k a basis of the complement of A's column space; R is m × n.
constexpr fft_norm swapped(fft_norm norm) noexcept
norm with its forward and backward exchanged, as NumPy's hfft and ihfft take it.
triangular_op
How solve_triangular reads its matrix: as it lies, transposed, or conjugate-transposed (SciPy's trans...
matrix< T > solve_triangular(const matrix< T > &a, matrix< T > b, bool lower, triangular_op op=triangular_op::none, bool unit_diagonal=false)
Solves A X = B, Aᵀ X = B or Aᴴ X = B (op) for a triangular A, as scipy.linalg.solve_triangular: its l...
eigen_method
How numerical::symmetric_eigen diagonalises.
@ 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...
qr_decomposition< T > qr(const matrix< T > &a)
QR-factorises an m × n matrix.
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...
matrix< T > inverse(matrix< T > a)
The inverse of a square matrix.
matrix< T > qr_r(matrix< T > a)
The factor R of the QR decomposition of an m × n matrix, k × n, k = min(m, n): qr_decomposition's R t...
A minimal std::thread parallel-for for the hot kernels.
The native vector of float and double the kernels hold their lanes in (GNU vector extensions,...
A complex pivot as over_pivot takes it: its reciprocal, or, where that would overflow (a subnormal pi...
std::complex< R > reciprocal
1 / pivot.
std::complex< R > pivot
The pivot.
bool divides
Whether over_pivot divides by the pivot: its parts under the smallest normal.
The pencil A − λ B of a Hermitian A and a Hermitian positive-definite B (each read in its lower trian...
matrix< T > vectors_of(matrix< T > &&v) const
The pencil's eigenvectors from v, columns of C's (all or some): L⁻ᴴ V.
matrix< T > reduced
C = L⁻¹ A L⁻ᴴ, whole.
matrix< T > factor
L, lower-triangular, B = L Lᴴ.
static matrix< T > standard_form(const matrix< T > &a, const matrix< T > &l)
definite_pencil(const matrix< T > &a, const matrix< T > &b)
static matrix< T > checked_factor(const matrix< T > &a, const matrix< T > &b)
One block of divide_and_conquer's tree: its rows [0, n) of the diagonal d its parent reads,...
double * d
The diagonal its parent reads, the eigenvalues once solved.
const double * work_e
The subdiagonal it is solved on.
std::size_t ldq
The distance between the rows of q.
double * q
Its diagonal block of the eigenvectors.
double * work_d
The diagonal it is solved on.
std::size_t n1
The order of its first half; 0 for a leaf.
int exponent
The power of two it is scaled down by.
double beta
The coupling of its halves.
The buffers of merge_rank_one, kept from one join to the next: a fresh buffer per join is mapped anew...
workspace_buffer updated
The kept columns of q times u.
workspace_buffer factor
The rows of u for those columns.
workspace_buffer gaps
poles[j] − roots[i], row by root, then the eigenvectors in its place.
workspace_buffer columns
One half's rows of the kept columns that reach it.
A left operand packed once for several products by it (an LU's −L₂₁ against blocks of its U₁₂): the t...
A plane rotation [c s; −s c] and what it leaves of its first argument, as LAPACK's dlartg makes it.
double r
c f + s g, of f's sign.
double c
The cosine, 0 or more.
The reflections of a Householder QR, Q left as its blocks of reflectors.
buffer< T > r
R, k × cols upper trapezoidal, its diagonal as it comes.
std::vector< reflector_block< T > > blocks
Q = H₀ H₁ …, block by block of qr_block reflectors.
The reflectors of one panel of the blocked QR, I − V T Vᴴ as LAPACK's dlarft forms it.
std::size_t height
The rows it acts on, first…first+height-1.
buffer< T > v
V, height × width row-major, reflector j from row j (zeros above).
buffer< T > t
T, width × width upper triangular.
std::size_t width
Its reflector count.
std::size_t first
The first row the block acts on.
A run of recorded rotations in which each shares a row with the next, as a sweep of the QL or QR iter...
std::size_t first
Its first operation.
bool down
Whether each next rotation's second row is this one's first.
std::size_t count
Its operations (one for an operation outside any run).
One operation of tridiagonal_ql or bidiagonal_qr on the rows of a vector matrix, recorded to be appli...
std::size_t j
The second row (unused by negate).
std::size_t i
The first row.
double c
The cosine of a rotation.
double s
The sine of a rotation.
A root of a secular equation: the pole it was sought from, and its offset from that pole.
std::size_t origin
The pole.
double offset
The root minus the pole.
The eigenvalues and the rotation of a symmetric 2 × 2 [a b; b c], as LAPACK's dlaev2.
double c
[c s; −s c] takes the matrix to diag(larger, smaller).
double s
The rotation's sine.
double larger
The eigenvalue of the larger magnitude.
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.
std::vector< buffer< T > > reflectors
Q = H₁ H₂ …: reflectors[k + 1] zeroes column k, from row k + 1.
buffer< T > delta
D = diag(δ), the unit phases that make T real.
One buffer of merge_workspace: its storage and how many elements it holds.
std::size_t size
Their number.
std::unique_ptr< double[]> data
The elements.
The pivoted LU factorisation of an m × n matrix (lu_factors): A = P L U.
matrix< T > l
m × k (k = min(m, n)), lower trapezoidal with a unit diagonal.
matrix< T > u
k × n, upper trapezoidal.
std::vector< std::size_t > rows
Row i of P⁻¹ A = L U is row rows[i] of A.
A dense, value-semantic vector over a scalar type.