NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
Classes | Namespaces | Typedefs | Enumerations | Functions | Variables
factorizations.hpp File Reference

The LU, Cholesky and QR factorisations and the symmetric and Hermitian eigen-decompositions. More...

#include <algorithm>
#include <array>
#include <atomic>
#include <bit>
#include <cmath>
#include <concepts>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <functional>
#include <limits>
#include <memory>
#include <numbers>
#include <numeric>
#include <optional>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
#include "concepts.hpp"
#include "matrix.hpp"
#include "simd.hpp"
#include "parallel.hpp"
#include "vector.hpp"
Include dependency graph for factorizations.hpp:

Go to the source code of this file.

Classes

struct  numerical::detail::complex_divisor< R >
 A complex pivot as over_pivot takes it: its reciprocal, or, where that would overflow (a subnormal pivot), the pivot itself, divided by. More...
 
class  numerical::singular_matrix_error
 Thrown when a matrix has no unique solution (it is singular). More...
 
class  numerical::non_finite_error
 Thrown when a decomposition's input holds an infinite or NaN entry: no factorisation of it means anything, and the iterative ones (eigh, SVD) would stop at once and return plausible values. More...
 
class  numerical::lu_decomposition< T >
 An LU factorisation with partial pivoting of a square matrix: each column's pivot the first entry of the largest detail::pivot_magnitude below the diagonal, |Re| + |Im| of a complex one, as LAPACK's. More...
 
struct  numerical::rectangular_lu< T >
 The pivoted LU factorisation of an m × n matrix (lu_factors): A = P L U. More...
 
class  numerical::not_positive_definite_error
 Thrown when a Cholesky factorisation finds the matrix not positive-definite. More...
 
class  numerical::cholesky_decomposition< T >
 A Cholesky factorisation A = L Lᴴ of a Hermitian positive-definite matrix. More...
 
struct  numerical::detail::thin_qr< T >
 A thin QR factorisation, row-major: q is rows × cols with orthonormal columns, r is cols × cols upper triangular with a real, non-negative diagonal. More...
 
struct  numerical::detail::reflector_block< T >
 The reflectors of one panel of the blocked QR, I − V T Vᴴ as LAPACK's dlarft forms it. More...
 
struct  numerical::detail::qr_reflections< T >
 The reflections of a Householder QR, Q left as its blocks of reflectors. More...
 
class  numerical::rank_cutoff
 The magnitude at or under which a singular value counts as zero, in a rank (matrix_rank), a pseudo-inverse (pinv) or a least-squares solution (lstsq): by default NumPy's, the largest singular value times the machine epsilon times the larger dimension; relative to the largest, as NumPy's rcond and rtol; or absolute, as matrix_rank's tol. More...
 
class  numerical::qr_decomposition< T >
 A QR factorisation A = Q R of an m × n matrix, as NumPy's qr, reduced by default. More...
 
class  numerical::pivoted_qr_decomposition< T >
 A QR factorisation with column pivoting A P = Q R of an m × n matrix, as scipy.linalg.qr(a, pivoting=True) (LAPACK's geqp3): at each step the column of largest remaining norm moved first, so R's diagonal does not grow in modulus down the diagonal and reveals A's numerical rank; the norms downdated as LAPACK's laqp2 downdates them, recomputed where the downdate has lost too much (√ε). Householder reflectors as larfg forms them; R's diagonal then made real and non-negative, as qr_decomposition's (Q's columns taking the phases), where LAPACK's may be negative. More...
 
class  numerical::convergence_error
 Thrown when an iterative algorithm has not converged within its bound of sweeps. More...
 
struct  numerical::detail::tridiagonal_reduction< T >
 The unitary M = Q Dᴴ of a reduction to real tridiagonal form, A = M T Mᴴ, kept as its factors. More...
 
struct  numerical::detail::row_operation
 One operation of tridiagonal_ql or bidiagonal_qr on the rows of a vector matrix, recorded to be applied later. More...
 
struct  numerical::detail::rotation_run
 A run of recorded rotations in which each shares a row with the next, as a sweep of the QL or QR iteration gives them: rows (i, i+1) for i going down (down), or going up. More...
 
struct  numerical::detail::plane_rotation_real
 A plane rotation [c s; −s c] and what it leaves of its first argument, as LAPACK's dlartg makes it. More...
 
struct  numerical::detail::symmetric_two_by_two
 The eigenvalues and the rotation of a symmetric 2 × 2 [a b; b c], as LAPACK's dlaev2. More...
 
struct  numerical::detail::secular_solution
 A root of a secular equation: the pole it was sought from, and its offset from that pole. More...
 
struct  numerical::detail::workspace_buffer
 One buffer of merge_workspace: its storage and how many elements it holds. More...
 
struct  numerical::detail::merge_workspace
 The buffers of merge_rank_one, kept from one join to the next: a fresh buffer per join is mapped anew, page by page. Each is written before it is read (updated zeroed row by row by the gathers). More...
 
struct  numerical::detail::divide_node
 One block of divide_and_conquer's tree: its rows [0, n) of the diagonal d its parent reads, the diagonal and subdiagonal it is solved on (its own copies scaled by a power of two, or d and the parent's), and its diagonal block of the eigenvector matrix, q, rows ldq apart. More...
 
struct  numerical::detail::definite_pencil< T >
 The pencil A − λ B of a Hermitian A and a Hermitian positive-definite B (each read in its lower triangle, of the diagonal its real part) in standard form: B = L Lᴴ and C = L⁻¹ A L⁻ᴴ, Hermitian, as LAPACK's sygst (type 1) forms it from pencil_reduction_least, by two triangular solves below (pencil_standard_form). C's eigenpairs (λ, y) are the pencil's (λ, L⁻ᴴ y), those vectors B-orthonormal (Xᴴ B X = I), as scipy.linalg.eigh(a, b)'s. More...
 
class  numerical::symmetric_eigen
 The eigenvalues and eigenvectors of a real symmetric matrix. More...
 
class  numerical::hermitian_eigen
 The eigenvalues and eigenvectors of a complex Hermitian matrix. More...
 

Namespaces

namespace  numerical
 The NumericAL public API.
 
namespace  numerical::detail
 

Typedefs

template<typename T >
using numerical::detail::magnitude_t = decltype(std::abs(std::declval< const T & >()))
 The type std::abs gives for a T: the real type of a complex one, T itself otherwise.
 
template<typename T >
using numerical::detail::carried_t = std::conditional_t< std::is_same_v< magnitude_t< T >, long double >, long double, double >
 The real type a T's norms, reflector lengths and pivot magnitudes are carried in: long double for a long double scalar, real or complex, whose precision a double would cut to its own; double otherwise.
 
template<typename T >
using numerical::detail::value_range_t = std::conditional_t< std::is_same_v< T, float >||std::is_same_v< T, std::complex< float > >, float, carried_t< T > >
 The real type whose range a T's values take: float for a single-precision scalar, real or complex; carried_t otherwise.
 
using numerical::detail::symmetric_row_kernel = double(*)(const double *, const double *, double, double *, std::size_t)
 A kernel of symmetric_row's form: symmetric_row itself, or an x86-64 one.
 
using numerical::detail::symmetric_rows_kernel = std::array< double, symmetric_row_group >(*)(const double *, std::size_t, const double *, double *, std::size_t)
 A kernel of symmetric_rows' form: symmetric_rows itself, or an x86-64 one.
 

Enumerations

enum class  numerical::triangular_op : unsigned char { numerical::none , numerical::transpose , numerical::adjoint }
 How solve_triangular reads its matrix: as it lies, transposed, or conjugate-transposed (SciPy's trans 0, 1 and 2). More...
 
enum class  numerical::qr_mode { numerical::reduced , numerical::complete }
 The factors a numerical::qr_decomposition keeps, as numpy.linalg.qr's modes name them. More...
 
enum class  numerical::eigen_method { numerical::tridiagonal_ql , numerical::jacobi , numerical::divide_and_conquer }
 How numerical::symmetric_eigen diagonalises. More...
 

Functions

template<typename T >
T numerical::detail::pivot_divisor (const T &pivot)
 The divisor over_pivot takes for the pivot pivot. A complex pivot's reciprocal, once, as LAPACK's zgetf2 takes it (a complex division calls the C library's robust one, a quarter of a complex LU of order 48 when it ran for every element); a real pivot itself, each element divided.
 
template<typename R >
complex_divisor< R > numerical::detail::pivot_divisor (const std::complex< R > &pivot)
 pivot_divisor of a complex pivot: its reciprocal, as zgetf2 takes one at least the smallest normal number in modulus (sfmin), and one under it divided by, whose reciprocal would overflow. (A zero pivot never comes here: the factorisation leaves its column, and the solves refuse a singular factor.)
 
template<typename T >
T numerical::detail::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.
 
template<typename R >
std::complex< R > numerical::detail::over_pivot (const std::complex< R > &x, const complex_divisor< R > &divisor)
 over_pivot of a complex x: times the pivot's reciprocal, the product in line; over a subnormal pivot itself.
 
template<typename T >
T numerical::detail::over_real_diagonal (const T &x, const T &diagonal)
 x over a Cholesky factor's diagonal entry diagonal, real and positive whatever the scalar.
 
template<typename R >
std::complex< R > numerical::detail::over_real_diagonal (const std::complex< R > &x, const std::complex< R > &diagonal)
 over_real_diagonal of a complex x: each part over the diagonal's real part, one rounding each, where a complex division took the C library's scaled one (several roundings, and other bits under another library).
 
template<typename T >
void numerical::detail::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).
 
template<typename R >
void numerical::detail::subtract_term (std::complex< R > &sum, const std::complex< R > &a, const std::complex< R > &b)
 subtract_term of complex numbers: the product in line (operator_times, the operator's rounding).
 
constexpr std::size_t numerical::detail::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, not a division.
 
double numerical::detail::power_of_two_scale (double largest) noexcept
 The power of two a decomposition divides a matrix by whose largest magnitude is largest: its leading bit's, the largest entry then in [1, 2); 1 where largest is 0. Dividing and multiplying back by it are exact, where a division by the largest itself rounded every entry.
 
constexpr std::size_t numerical::detail::cholesky_block_for (std::size_t n) noexcept
 The panel width of the Cholesky factorisation of order n: narrower up to order 256, where the panels, row by row on one thread, are most of the time; a power of two, which the product kernels' tiles divide (widths of 24, 40 or 56 left the AMX's 32 × 16 tiles part empty: order 320, 20 % longer).
 
template<typename T >
T numerical::detail::conj_of (const T &x)
 The conjugate of a real (or general) scalar — the value itself.
 
template<typename U >
std::complex< U > numerical::detail::conj_of (const std::complex< U > &x)
 The conjugate of a complex scalar.
 
template<typename T >
magnitude_t< T > numerical::detail::pivot_magnitude (const T &x)
 The magnitude partial pivoting compares: |x| of a real x.
 
template<typename U >
U numerical::detail::pivot_magnitude (const std::complex< U > &x)
 The magnitude partial pivoting compares of a complex x: |Re x| + |Im x|, LAPACK's (izamax, cabs1), so the same pivots as its zgetrf, with no square root.
 
template<typename T >
T numerical::detail::from_carried (carried_t< T > x)
 x, a magnitude carried in carried_t, as the scalar T: converted to T's real type first, so a std::complex<float> is built from a float (a double argument narrows inside its constructor).
 
template<typename T >
carried_t< T > numerical::detail::real_part (const T &x)
 The real part of a real (or general) scalar, in carried_t.
 
template<typename U >
carried_t< U > numerical::detail::real_part (const std::complex< U > &x)
 The real part of a complex scalar.
 
template<typename T >
carried_t< T > numerical::detail::rescue_factor (carried_t< T > largest)
 The exact power of two that brings a magnitude below about the square root of the smallest normal number of T's range (2⁻⁵⁰⁰ in double, 2⁻⁶⁰ in float) up among normal numbers, as LAPACK's dlarfg rescales; 1 for any larger magnitude. It is a T itself: a zero takes the factor of the smallest normal number, which a double's range holds and a float's does not.
 
template<std::floating_point R>
R numerical::detail::times_power_of_two (R x, int e)
 x times 2ᵉ, rounded once (a power of 2 scales a normal number exactly).
 
template<std::floating_point R>
R numerical::detail::part_size (R x)
 The magnitude of a real x, x's exponent read from it.
 
template<std::floating_point U>
U numerical::detail::part_size (const std::complex< U > &x)
 The larger magnitude of a complex x's parts: no sum of them, which overflows near the largest double.
 
template<std::floating_point U>
std::complex< U > numerical::detail::times_power_of_two (const std::complex< U > &x, int e)
 times_power_of_two of each part of a complex x.
 
template<typename T , typename Factor >
T numerical::detail::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 pivots: each factor, and the running product after it, brought near 1 by a power of 2 (exactly) and the powers kept apart, then applied once at the end. The same bits as the plain product wherever that stays normal; where a partial product would overflow or underflow (pivots of 10¹⁵⁰ and 10⁻¹⁵⁰), the representable answer.
 
template<typename T >
T numerical::detail::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 scaled up first, exactly: its modulus would round to the coarse subnormal grid, and x / |x| miss unit modulus by as much.
 
template<typename T >
carried_t< T > numerical::detail::rescale_tiny (buffer< T > &x)
 Scales x by rescue_factor of its largest magnitude, exactly, so that a Householder vector built from it is computed among normal numbers: a subnormal norm rounds to the coarse subnormal grid, and the reflector is then not orthogonal.
 
template<typename T >
carried_t< T > numerical::detail::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 plain sum of squares overflows near 1e155 and underflows to 0 near 1e-155.
 
template<typename T >
double numerical::detail::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 underflowed (between plain_squares_low and plain_squares_high); else norm_at_scale.
 
template<typename T >
carried_t< T > numerical::detail::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.
 
double numerical::detail::scaled_norm (const double *x, std::size_t count)
 The same for double: the plain sum of squares in one pass of dot_product where it holds.
 
double numerical::detail::scaled_norm (const std::complex< double > *x, std::size_t count)
 The same for std::complex<double>: dot_product over the parts, which an array of them holds in order ([complex.numbers]).
 
template<typename T >
carried_t< T > numerical::detail::scaled_norm (const buffer< T > &x)
 scaled_norm of a whole vector.
 
double numerical::detail::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 sum of squares where the larger magnitude lies within 2^±500, so its square neither overflows nor underflows and the smaller one's underflow is below its rounding; std::hypot, which scales every time, outside. A graded matrix reaches both ends though scaled to its largest entry: a QL shift's ratio (d₁ − d₀) / 2e came to 5e199 on [[1e-200, 1e-200], [1e-200, 1]].
 
template<typename T >
bool numerical::detail::is_finite_entry (const T &x)
 Whether x is finite.
 
template<typename U >
bool numerical::detail::is_finite_entry (const std::complex< U > &x)
 Whether x is finite: both of its parts.
 
template<typename T >
void numerical::detail::require_finite (const matrix< T > &a, const char *what)
 The one non-finite policy, checked where every decomposition starts.
 
template<typename T >
matrix< T > numerical::detail::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 matrix's copy faulted every one in on the calling thread (order 1000 on one arm64 core 0.64 ms, an eighth of the Cholesky factorisation; on eight cores 0.28 ms).
 
bool numerical::detail::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, an element read weighed as half one copied (six x86-64 AVX2 cores, a Cholesky factorisation of order 500 with its other passes on the threads too: 1.12 → 0.91 ms).
 
void numerical::detail::require_finite (const matrix< double > &a, const char *what)
 require_finite for double, its elements contiguous: all_finite.
 
void numerical::detail::require_finite (const matrix< std::complex< double > > &a, const char *what)
 The same for std::complex<double>, whose array holds its parts in order ([complex.numbers]).
 
template<typename T >
bool numerical::detail::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, kept out of line: the rare road of require_finite_lower where the whole matrix is not finite.
 
template<typename T >
void numerical::detail::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 part (as numpy.linalg.eigh reads them, whatever the rest holds).
 
void numerical::detail::require_finite_lower (const matrix< double > &a, const char *what)
 require_finite_lower for double: all_finite over the whole matrix, the one vectorised pass require_finite takes, and the triangle entry by entry only where it finds a NaN or an infinity. Out of line, so that a decomposition's constructor stays small enough to be inlined: in it, the check kept GCC from inlining the Cholesky's (order 8, 0.204 → 0.220 µs), as an entry-by-entry check (6 % at order 64 on arm64) or a row-by-row one (21 % at order 8 under GCC) cost in time.
 
void numerical::detail::require_finite_lower (const matrix< std::complex< double > > &a, const char *what)
 The same for std::complex<double>, whose array holds its parts in order ([complex.numbers]).
 
template<typename T >
void numerical::detail::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, one after another), term by term in ascending order: an elimination step of a Cholesky panel's rows below (an overload per scalar, as conj_of). Each term subtract_product, the column read and written again for every one.
 
void numerical::detail::subtract_panel_columns (double *column, const double *columns, std::size_t height, const double *l, std::size_t terms)
 subtract_panel_columns for double: subtract_products, which holds the column in registers through the terms, the same multiply-adds in the same order, so the same values (a complex one keeps the term-by-term calls, whose x · f the other would round as f · x).
 
std::pair< matrix< float >, int > numerical::detail::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: every entry below 1 in magnitude, so none overflows float, and the scaling exact.
 
double numerical::detail::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 compares each with ‖A‖∞ ε √n); NaN, which no bound meets, where an entry of r is not finite.
 
std::optional< matrix< double > > numerical::detail::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, its solution corrected in double precision by the residual R = B − A X (each correction a single-precision solve of A D = R) until every column meets ‖R‖∞ ≤ ‖X‖∞ ‖A‖∞ ε √n (ε double's unit roundoff). Each operand goes to single precision scaled by a power of two (scaled_to_float): none overflows, where dsgesv falls back. A correction must divide the largest ‖R‖∞ / ‖X‖∞ by 8 at least, which bounds their count (about a dozen from single precision to the bound) where dsgesv allows 30: an A too ill-conditioned for single precision converges slowly or not at all, and the double factorisation is then the faster. The single factorisation costs half the double one's; each correction a product and a solve of n² k.
 
template<field T>
vector< T > numerical::solve (matrix< T > a, const vector< T > &b)
 Solves the linear system A x = b for a square A.
 
template<field T>
matrix< T > numerical::solve (matrix< T > a, const matrix< T > &b)
 Solves A X = B for a square A and every column of B at once, as numpy.linalg.solve with a matrix right-hand side: one factorisation of A, then one substitution per column.
 
template<field T>
T numerical::determinant (matrix< T > a)
 The determinant of a square matrix.
 
template<field T>
matrix< T > numerical::inverse (matrix< T > a)
 The inverse of a square matrix.
 
template<typename T >
void numerical::detail::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 upper one (the other never read), its diagonal taken as ones where unit: by halves (triangular_halves), each half's terms out of the other by one matrix product as deep as it, as a recursive trsm; one column by a dot product of each row with the unknowns solved.
 
template<typename T >
void numerical::detail::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, its transpose, read in place; lower whether a (not M) is lower-triangular, the other triangle never read, its diagonal taken as ones where unit. By halves (triangular_halves), as a recursive trsm, the columns by blocks of triangular_slice on the threads; one column of M = a by a dot product of each row with the unknowns solved, of M = aᵀ by a sweep, each unknown solved taken from the others by its row of a.
 
template<typename T >
bool numerical::detail::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.
 
bool numerical::detail::elements_finite (const double *x, std::size_t count)
 elements_finite of double: all_finite_shared, vectorised.
 
bool numerical::detail::elements_finite (const std::complex< double > *x, std::size_t count)
 The same for std::complex<double>, whose array holds its parts in order ([complex.numbers]).
 
template<typename T >
bool numerical::detail::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, entry by entry: the rare road of require_finite_triangle, where the whole matrix is not.
 
template<typename T >
void numerical::detail::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 side x (count elements): one vectorised pass over the whole matrix, then the triangle entry by entry only where that pass finds one (the other triangle may hold anything); the right-hand side in one pass.
 
template<typename T >
void numerical::detail::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, or a check that covered them): a zero on the diagonal still refused.
 
template<typename T >
void numerical::detail::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 checked, then read where it lies, transposed in place; the adjoint by the transpose on the conjugates (Aᴴ X = B is Aᵀ conj X = conj B).
 
template<std::floating_point R>
R numerical::detail::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, else −1; sign set to it.
 
template<std::floating_point R>
std::complex< R > numerical::detail::sign_entry (std::complex< R > x, int &sign) noexcept
 A complex entry's unit-modulus sign, zlacn2's: x / |x|, 1 where |x| is not past the least normal number; sign 0, a complex climb having no sign vector to repeat.
 
template<std::floating_point R>
bool numerical::detail::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.
 
template<std::floating_point R>
bool numerical::detail::same_sign (std::complex< R >, int) noexcept
 A complex entry's sign never repeats (zlacn2 has no such test).
 
template<std::floating_point R>
bool numerical::detail::climb_ends (R last, R largest) noexcept
 Whether the climb's last column last is as large as the new largest entry largest, so it stops: dlacn2 compares the real entry itself with the largest modulus.
 
template<std::floating_point R>
bool numerical::detail::climb_ends (std::complex< R > last, std::complex< R > largest) noexcept
 climb_ends of complex entries, as zlacn2: their moduli.
 
template<typename T >
double numerical::detail::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, Higham's refinements): apply(x, false) overwrites the n entries at x with B x, apply(x, true) with Bᴴ x. Products on sign vectors (unit-modulus ones for complex T) climb to a column of large norm, at most five each way; one more on (−1)ⁱ (1 + i / (n − 1)) guards against the operators that fool the climb. A lower bound, rarely short of ‖B‖₁ by more than a factor of 3 (Higham, Accuracy and Stability of Numerical Algorithms, 2002, §15.3); infinity where a product overflows.
 
template<typename T >
double numerical::detail::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⁻¹‖₁ by one_norm_estimate over apply, as LAPACK's *con routines end: 1 for an empty matrix, 0 for a zero one, and 0 where the estimate overflows.
 
template<typename T >
double numerical::detail::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, its unit diagonal not stored, U on and above it) and one_norm, ‖A‖₁, as LAPACK's gecon: A⁻¹'s products U⁻¹ L⁻¹ and L⁻ᴴ U⁻ᴴ (the permutation leaves 1-norms alone). 0 where U has a zero on its diagonal.
 
template<typename T >
double numerical::detail::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 × n row-major factor or U in its upper one, and one_norm, ‖A‖₁, as LAPACK's pocon: A⁻¹ its own adjoint, the two products one.
 
template<typename T >
double numerical::detail::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 one, as LAPACK's trcon (1-norm): ‖A‖₁ the triangle's largest column sum of moduli, A⁻¹'s products by substitution. 0 where the diagonal holds a zero.
 
template<field T>
double numerical::triangular_reciprocal_condition (const matrix< T > &a, bool lower)
 The reciprocal condition number 1 / (‖A‖₁ ‖A⁻¹‖₁) of a triangular matrix, as LAPACK's trcon (1-norm): its lower triangle or its upper one read, the other never; ‖A⁻¹‖₁ estimated by substitutions (Hager's method), so within a small factor of the exact.
 
template<field T>
matrix< T > numerical::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 lower triangle or its upper one is read, the other never, and its diagonal as ones where unit_diagonal. By substitution, a block's rows by rows of terms and the rows past it through the matrix product kernel: n² k multiply-adds, where solve factorises A first.
 
template<field T>
vector< T > numerical::solve_triangular (const matrix< T > &a, const vector< T > &b, bool lower, triangular_op op=triangular_op::none, bool unit_diagonal=false)
 solve_triangular of one right-hand side.
 
template<typename T >
std::pair< matrix< T >, matrix< T > > numerical::detail::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, its first k columns (unit diagonal), and U, its first k rows.
 
template<typename T >
void numerical::detail::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]) by partial pivoting, in place, as LAPACK's dgetrf2: the left half factorised, the top of the right half solved against its unit-lower L, the bottom updated by one product, then the right half; a leaf of solve_leaf columns, or a panel too short for its products to pay, unblocked. Each pivot's row swap reaches every column and rows (row i of the factors is row rows[i] of the input); a zero pivot column is left as it is.
 
template<typename T >
requires std::same_as<T, double> || std::same_as<T, std::complex<double>>
rectangular_lu< T > numerical::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 trapezoidal with a unit diagonal, U k × n upper trapezoidal, k = min(m, n), rows chosen by partial pivoting. A wide matrix's square part by lu_decomposition and U's other columns by L⁻¹ P A (a triangular solve); a tall one by lu_decomposition of it beside zero columns (its first n columns factorised alike) up to detail::lu_tall_ratio times as tall as wide, by dgetrf2's recursion over its columns (detail::tall_lu_columns) past. A zero pivot leaves its column of L zero, as LAPACK's.
 
template<field T>
cholesky_decomposition< T > numerical::cholesky (matrix< T > a)
 Cholesky-factorises a Hermitian positive-definite matrix.
 
template<typename T >
void numerical::detail::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 array, on its columns from…cols-1.
 
template<typename T >
reflector_block< T > numerical::detail::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 empty one the identity) into I − V T Vᴴ = H_{k0} H_{k0+1} … H_{k1-1}, T as LAPACK's dlarft forms it.
 
template<typename T >
void numerical::detail::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 array, on its columns from…to-1: W = Vᴴ A, then W ← T W or Tᴴ W, then A −= V W, the two outer products through the matrix product kernel.
 
template<typename T >
void numerical::detail::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ᴴ) A on A's rows first… and columns from…to-1 is Aᵀ ← Aᵀ (I − conj(V) Tᵀ Vᵀ) on Aᵀ's columns first… and rows from…to-1 (with the adjoint (I − V Tᴴ Vᴴ) A, conj(T) for Tᵀ). Its three products have to − from rows, which the matrix product kernel runs well and on every core; apply_reflector_block's first has the block's few (a reflector block's 32 rows by 1000 deep: 54 GFLOP/s on twenty x86-64 threads).
 
template<typename T >
requires std::is_floating_point_v<T>
T numerical::detail::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.
 
template<typename T >
T numerical::detail::conjugate_dot (const T *x, const T *y, std::size_t count)
 Σ conj(x[i]) · y[i] of complex numbers (conjugate_dot_product).
 
template<typename T >
std::pair< T, T > numerical::detail::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 = β e₁, β real, of the sign opposite to Re x₀. Exact inputs stay exact where LAPACK's do (e₂ reflected onto e₁: w = (1, 1), τ = 1, where a unit v holds 1/√2, rounded). For an x with something below x₀, or x₀ complex (the identity otherwise, which the caller keeps).
 
template<typename T >
void numerical::detail::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 panel (height rows per column), on its rows first…first+|v|-1: each column a dot product with v, then v scaled out of it, both along the column at unit stride.
 
template<typename T >
void numerical::detail::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, one by one, in place, into reflectors[k0…k1-1] and taus: panel holds column k0, ld elements per column from row top (0 in the whole matrix, k0 in a copy of the panel). A reflector meets each column at unit stride. Recursive halves, the left's reflectors applied to the right at once, took longer at these widths (32 columns).
 
template<typename T >
std::vector< reflector_block< T > > numerical::detail::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, cols columns), factorised in place as LAPACK's dgeqrf leaves it: R on and above the diagonal, each reflector's w₁… below it. The columns right of a panel take its block as (I − V T Vᴴ)ᴴ, held transposed (apply_transposed_reflector_block): the products then have as many rows as there are columns to update, where the row-major form's first product has the block's 32 (one x86-64 core: 39 ms against 46 for the updates of order 1000). From qr_look_ahead_threads threads, the next panel is updated and factorised by one task while the others update the columns past it, a slice each. Where reflectors is false (R alone asked), a block no update reads is not gathered.
 
template<typename T >
void numerical::detail::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, bands of them on the threads (a pass bound by the memory, its bounds captured by value).
 
template<typename T >
void numerical::detail::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 the panel, copied back. A function of its own: written into reflect_in_rows' loop, the same instructions took 5 % more cycles at order 128 (clang, arm64).
 
template<typename T >
std::vector< reflector_block< T > > numerical::detail::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 reflect_in_columns leaves the column-major one (R on and above the diagonal, each reflector's w₁… below it): each panel in a column-major copy, the columns right of it updated by apply_reflector_block, whose projection reads A as the product's right operand. The AMX tile reads that in place, and NEON's packs it faster than the column-major form's left one (arm64, order 512: 6.3 ms against 7.2 under clang, 16.4 against 17.9 under GCC). Where r is given, it is R (min(rows, cols) × cols row-major, zeros below the diagonal).
 
template<typename T >
qr_reflections< T > numerical::detail::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' reflectors applied to the first k = min(rows, cols) columns of the identity, R's diagonal not yet made real (a product with Qᴴ, or with Q of a block padded with zeros, applies the blocks instead). a is row-major. On the x86-64 units it is transposed in by tiles and factorised column-major (reflect_in_columns, whose updates' products run faster there: one AVX2 core, order 1000, 39 ms against 46), elsewhere in place (reflect_in_rows). Where reflectors is false, R alone is asked: a block no update reads is not gathered, and the blocks are not all there.
 
template<typename T >
void numerical::detail::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 the identity, into out: rows × count row-major, or where transposed Qᵀ row-major (Q column-major). Formed as householder_reflect factorises, so that a Q is the same to the bit in either layout: as the rows of Qᵀ on the x86-64 units (apply_transposed_reflector_block), row-major elsewhere (apply_reflector_block), then transposed where the other layout is asked. The columns of the identity left of a block's rows are left as they are.
 
template<typename T >
void numerical::detail::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, the last applied first: a basis taken through Q without forming Q, as LAPACK's dormqr applies it where dorgqr forms it. As form_q_into applies the blocks: on the x86-64 units to the rows of Pᵀ (apply_transposed_reflector_block), transposed in and out, elsewhere in place (apply_reflector_block).
 
template<typename T >
thin_qr< T > numerical::detail::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, cols): Q is rows × k with orthonormal columns and R k × cols upper trapezoidal. Each column below the diagonal is reflected onto it, so Q is orthonormal to rounding whatever the conditioning of A, and a column dependent on the earlier ones leaves a zero on R's diagonal.
 
template<typename T >
buffer< T > numerical::detail::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 of each row by its diagonal's phase, so the same bits, Q never formed (numpy.linalg.qr's mode="r"; forming Q is about as much work again).
 
double numerical::detail::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, as NumPy draws it: the largest times the machine epsilon times the larger dimension.
 
template<typename T >
qr_decomposition< T > numerical::qr (const matrix< T > &a)
 QR-factorises an m × n matrix.
 
double numerical::detail::adjoint_dot (const double *x, const double *y, std::size_t count)
 Σ x[i] y[i], vectorised (dot_product): xᴴ y for real numbers.
 
std::complex< double > numerical::detail::adjoint_dot (const std::complex< double > *x, const std::complex< double > *y, std::size_t count)
 Σ conj(x[i]) y[i], vectorised (conjugate_dot_product): xᴴ y.
 
template<typename T >
double numerical::detail::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.
 
template<typename T >
matrix< T > numerical::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 to the bit, Q never formed.
 
template<typename T >
requires std::is_floating_point_v<T>
void numerical::detail::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.
 
template<typename T >
void numerical::detail::add_conjugate_product (T *y, const T *x, const T &f, std::size_t count)
 y[i] += conj(x[i]) · f, each product's statements spelled out as the complex operator's (four part products rounded apart, ac − bd and ad + bc, then their sums with y): the same bits for finite parts whose products stay finite, where the operator's rescue of a product whose parts are both NaN never acts, and a loop the compiler vectorises (the reduction's rows, scaled by their largest magnitude, are such).
 
template<typename T >
T numerical::detail::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, and the return Σⱼ≤ᵢ row[j] v[j], for a complex T.
 
std::complex< double > numerical::detail::hermitian_row (symmetric_row_kernel kernel, const std::complex< double > *row, const std::complex< double > *v, std::complex< double > *out, std::size_t i)
 The same for a std::complex<double> row: in one pass on AVX-512 or AVX2 with FMA where the matrix product's kernel runs there (avx512_hermitian_row), else as the template.
 
double numerical::detail::hermitian_row (symmetric_row_kernel kernel, const double *row, const double *v, double *out, std::size_t i)
 The same for a real row, in one pass through kernel.
 
template<typename T >
std::size_t numerical::detail::symmetric_row_speedup ()
 The weight of a symmetric row's multiply-adds in hermitian_product: on the x86-64 units, where its rows are paced by one core's loads, vector_speedup, as more threads pay than their multiply-adds alone would pay for (an i9-9900K's reduction of order 512 took 17 % less, an i9-10900X's 7 %); 1 elsewhere (arm64's, weighed so, took as long or longer).
 
template<typename T >
void numerical::detail::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, as LAPACK's dsymv: each row's lower part is read once and serves twice, w[i] += Σⱼ≤ᵢ B[i][j] v[j] and w[j] += conj(B[i][j]) v[i] for j < i, so a reduction step reads half the block it would read whole. Rows go by tasks of fixed size, each into its own partial w, summed in a fixed order: the result does not depend on the number of threads. A real row is read once for both (symmetric_row), on the widest x86-64 units the matrix product's kernel may use (gemm_path_current).
 
template<typename T >
requires std::is_floating_point_v<T>
void numerical::detail::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.
 
template<split_complex T>
void numerical::detail::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 complex numbers, each term y[i] −= f · x[i] spelled out as the complex operator's statements (four part products rounded apart, ac − bd and ad + bc, then their differences with y): the same bits for finite parts whose products stay finite, where the operator's rescue of a product whose parts are both NaN never acts, and loops the compiler vectorises (the reduction's rows, scaled by their largest magnitude, are such). Complex double on the x86-64 units keeps its fused kernel.
 
template<typename T >
void numerical::detail::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] = (c[2p+1] · v) and f[2p+1] = (c[2p] · v) (conjugated) computed beside the product, among its tasks, and the partials summed and the corrections taken by bands of rows: each element the operations, in the order, hermitian_product, conjugate_dot and subtract_products give it apart.
 
double numerical::detail::real_subdiagonal (double t, double, double &)
 A real subdiagonal entry of the tridiagonal: kept with its sign (the rotations take any sign).
 
double numerical::detail::real_subdiagonal (std::complex< double > t, std::complex< double > delta, std::complex< double > &next)
 A complex subdiagonal entry made real by the next row's unit phase: next = delta · conj(phase(t)).
 
template<typename T >
tridiagonal_reduction< T > numerical::detail::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, to a real symmetric tridiagonal by Householder reflections, A = M T Mᴴ with M unitary.
 
template<typename T >
buffer< T > numerical::detail::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 last back, as LAPACK's dorgtr forms Q, each block on the rows it reaches of the identity, then row j times conj(δⱼ).
 
template<typename T >
void numerical::detail::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, taken to the matrix's: at ← at Mᵀ = at Dᴴ Qᵀ, column j times conj(δⱼ), then the blocks of reflectors from the last back on every row, as LAPACK's dormtr: two thirds of the operations of forming M (tridiagonal_basis) and multiplying by it.
 
template<typename T >
void numerical::detail::to_matrix_basis (const tridiagonal_reduction< T > &reduction, buffer< T > &at, std::size_t n)
 to_matrix_basis of all n rows.
 
std::vector< rotation_run > numerical::detail::rotation_runs (const std::vector< row_operation > &operations)
 The operations split into runs of chained rotations, every other operation a run of one.
 
template<typename T >
void numerical::detail::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 independently of the others, so chunks of columns run in parallel, every element receiving the same operations in the same order as applying each in place would give it.
 
plane_rotation_real numerical::detail::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 0, a quarter turn for f 0. Its length by rotation_length.
 
symmetric_two_by_two numerical::detail::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 the sum and the root of the difference, the smaller from the determinant (no cancellation), and the rotation (c, s) whose first row is the larger's eigenvector.
 
void numerical::detail::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–Kahan variant of implicit QL or QR on the squares of the off-diagonal entries, no root in its inner loop, each block scaled into a safe range and iterated from its smaller end, an entry dropped against its neighbours (e² ≤ ε² |dᵢ dᵢ₊₁|). Faster than tridiagonal_ql's dsteqr without rotations (one core: order 500 4.4 → 3.4 ms, 2000 66 → 52) and more accurate on a graded matrix (the smallest of dᵢ = 0.01ⁱ, n = 10: 3e-16 against 4e-14).
 
template<typename T >
void numerical::detail::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, the rotations accumulated into the rows of zt. Each unreduced block, scaled into a safe range, is iterated from the end of its smaller diagonal entry (QL down a block graded downwards, QR up one graded upwards), an off-diagonal entry dropped against its neighbours' diagonal entries (e² ≤ ε² |dᵢ dᵢ₊₁|) rather than the matrix's norm, and no shift is subtracted from the whole diagonal: the small eigenvalues of a graded matrix keep their relative accuracy. EISPACK's tql2, here before, tested against the largest entry seen and moved every diagonal entry by the accumulated shift: on d = gⁱ, e near √(dᵢ dᵢ₊₁), the smallest eigenvalues lost every digit (g = 0.01, n = 10; NumPy's 3e-16).
 
double numerical::detail::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 fit (shared by its instantiations, whose data reach one form or the other).
 
template<typename Offset >
secular_solution numerical::detail::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, as LAPACK's dlaed4 and dlasd4 find it. The poles are given only as their offsets from one another, offset(o, j) = Pⱼ − P_o, which the caller computes accurately.
 
double numerical::detail::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) + ρ z zᵀ, by solve_secular.
 
double * numerical::detail::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, and its pages are touched by every thread, chunk by chunk: on Linux a page costs about a microsecond the first time it is written, and the join that first wrote it waited on them one thread at a time (an eigh of order 1024 mapped some 30 MB of these buffers on one x86-64 core).
 
merge_workspace & numerical::detail::thread_workspace ()
 The calling thread's merge_workspace, kept from one decomposition to the next: mapping its pages anew took 8–11 % of the eigenvectors' time (six AVX2 cores, an eigh of order 256 or 512). A join uses it whole on one thread, and nests no other join; release_large_workspace lets a large buffer go after.
 
void numerical::detail::release_large_workspace (merge_workspace &work)
 Releases the buffers of work longer than kept_workspace.
 
void numerical::detail::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 × n block of rows ldq apart whose columns span the halves) into q, as LAPACK's dlaed1.
 
void numerical::detail::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, parents before children: each scaled to work near unit size by a power of two (exactly), as the deflation tolerance is relative to the weights, which have unit norm, and so to the tridiagonal only at that size; each half has its own. A block past divide_leaf is split into two halves plus a rank-one coupling, as LAPACK's dlaed0: T = diag(T₁ − ρ e_a e_aᵀ, T₂ − ρ e_b e_bᵀ) + ρ u uᵀ, u = e_a + sign(β) e_b, ρ = |β|, β the coupling.
 
void numerical::detail::solve_divide_leaf (const divide_node &node)
 Solves the leaf node by implicit QL: its eigenvalues ascending into its diagonal, their eigenvectors as the columns of its block of q.
 
void numerical::detail::join_divide_node (const divide_node &node, merge_workspace &work)
 Joins the two solved halves of node by merge_rank_one, in work.
 
void numerical::detail::unscale_divide_node (const divide_node &node)
 The eigenvalues of a solved node, scaled back, where its parent reads them.
 
void numerical::detail::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.
 
void numerical::detail::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-2] into d, and its eigenvectors as the columns of the row-major q (n × n), by Cuppen's divide and conquer: the tridiagonal is two halves plus a rank-one coupling, each half is diagonalised the same way (by implicit QL up to divide_leaf), and merge_rank_one joins them, each half into its own diagonal block of q, so the joins copy no half and leave the blocks off the diagonal as they found them until the join of their two halves fills them.
 
template<typename T >
void numerical::detail::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.
 
void numerical::detail::multiply_real_left (const buffer< double > &left, buffer< double > &zt, std::size_t n)
 zt ← left · zt, n × n, row-major, for a real left factor.
 
void numerical::detail::multiply_real_left (const buffer< double > &left, buffer< std::complex< double > > &zt, std::size_t n)
 zt ← left · zt for a complex zt: the real and imaginary parts by a real product each.
 
template<typename T >
buffer< T > numerical::detail::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 rows of the result, by divide and conquer (LAPACK's dstedc, then dormtr): most of the work in matrix products. Up to divide_leaf, tridiagonal_ql on Mᵀ itself.
 
void numerical::detail::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.
 
void numerical::detail::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.
 
std::vector< std::size_t > numerical::detail::ascending_order (const buffer< double > &diagonal)
 The indices of diagonal by ascending value.
 
template<typename T >
buffer< T > numerical::detail::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, the rows of each on its own core. Element by element, each write was a row apart, and the copy of order 1024 took a tenth of an eigh on six x86-64 cores.
 
template<typename T >
void numerical::detail::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 stride ldl), one column after another, as LAPACK's sygs2 (type 1): each diagonal element divided by L's squared, the column below it scaled, corrected by half of it twice around the rank-2 update of the rest, then solved against the rest of L. c's other triangle is neither read nor written.
 
template<typename T >
bool numerical::detail::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, depth two blocks of pencil_block (past gemm_min_depth), where the matrix product kernel packs a product of that size: on the triangle's tiles alone (gemm_triangle).
 
bool numerical::detail::lower_triangle_product (std::size_t m, std::size_t depth, const double *a, const double *b, double *c, std::size_t ldc)
 lower_triangle_product for double.
 
template<typename T >
void numerical::detail::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 (n × n, row-major), as LAPACK's sygst (type 1, lower) by blocks of pencil_block columns: a block's diagonal by reduce_pencil_columns; the rows below it solved against its L₁₁ᴴ from the right, corrected by half of L₂₁ C₁₁ twice around the trailing rank-2k update C₂₂ −= C₂₁ L₂₁ᴴ + L₂₁ C₂₁ᴴ (its lower triangle); once every block is through, each one's rows solved against its L₂₂, the blocks on the threads together. Some n³ operations where two whole triangular solves took 2 n³. c's other triangle is neither read nor written.
 
template<typename T >
buffer< T > numerical::detail::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: by blocks (reduce_pencil, C's lower triangle, then its upper from it) where blocks, else by two whole triangular solves, L⁻¹ A and L⁻¹ (L⁻¹ A)ᴴ.
 

Variables

constexpr std::size_t numerical::detail::lu_block {64}
 The columns of one panel of the blocked LU: the trailing update, a product of this depth, is deep enough for the packed kernel while the unblocked panel stays a small part of the work.
 
constexpr std::size_t numerical::detail::lu_small_order {256}
 The order up to which the LU takes panels of lu_small_block columns: there the panels, a column at a time on one thread, are most of the time, and narrower ones halve their work (arm64, order 300 on every core: 14 % slower at 32 columns than at 64).
 
constexpr std::size_t numerical::detail::lu_small_block {32}
 The columns of one panel of the LU of an order up to lu_small_order.
 
constexpr std::size_t numerical::detail::lu_wide_order {3072}
 The order from which the LU takes panels of lu_wide_block columns: each trailing update rereads the whole trailing block, and from there the memory traffic of panels of 64, not their arithmetic, sets the time; 128 halves it. Order 4096: ten AVX-512 cores 322 → 273 ms, six AVX2 cores 416 → 330, eight arm64 cores 285 → 252; order 3072 10 to 17 % faster; 2560 the same; 2048 10 % slower, the wider panel's own work then the longer. The factors are the same to the bit at either width.
 
constexpr std::size_t numerical::detail::lu_wide_block {128}
 The columns of one panel of the LU from lu_wide_order.
 
constexpr std::size_t numerical::detail::lu_lookahead_columns {1024}
 The trailing columns at most past which the LU factorises its next panel beside the update of the rest (a look-ahead): a wider update runs well as one product, and cut in blocks beside the panel it ran longer (order 2048 on six x86-64 cores, 9 %); a narrower one leaves threads idle while the panel runs.
 
constexpr std::size_t numerical::detail::lu_fused_columns {512}
 The trailing columns at most past which each block of the update beside the panel solves its own rows of U₁₂: a wider update keeps every thread busy past the panel, and its rows solved on all of them first ran faster than on the workers alone (order 1000 on four AVX2 cores, 2 %).
 
constexpr std::size_t numerical::detail::lu_update_speedup {gemm_kernel_speedup}
 The multiply-adds of an LU's trailing update one of the tile's dependent ones stands for, as threads are weighed (gemm_kernel_speedup): the AMX tile's, on arm64; the AVX tiles' quarter of it on x86-64, where the update of order 256 waited on one thread (six cores: 690 → 622 µs, 1024: 12.5 → 12.1 ms).
 
constexpr std::size_t numerical::detail::narrow_solve {16}
 The most right-hand sides an LU solve takes row by row rather than by blocks through the product kernel.
 
constexpr std::size_t numerical::detail::slice_columns {64}
 The fewest columns an LU solve gives a thread of its own: a narrower slice starves the product kernel (arm64, order 256 and 64 right-hand sides in eight slices: 112 → 194 µs; 48 columns, order 300 and 300 right-hand sides: 8 % slower than 64).
 
constexpr std::size_t numerical::detail::solve_leaf {16}
 The columns of one leaf of the recursive LU panel.
 
constexpr std::size_t numerical::detail::inverse_band {16}
 The rows an LU inverse writes its identity into, and permutes the columns of, on one thread at a time.
 
constexpr std::size_t numerical::detail::svd_band {32}
 The rows of an SVD's input one thread scales and copies at a time.
 
constexpr std::size_t numerical::detail::zeroed_rows {32}
 The rows of a Cholesky factor whose upper part one thread zeroes at a time.
 
constexpr std::size_t numerical::detail::cholesky_block {64}
 The columns of one panel of the blocked Cholesky factorisation (as lu_block).
 
constexpr std::size_t numerical::detail::cholesky_diagonal_rows {4}
 The rows of a Cholesky diagonal block factorised together, one chain of sums each (one x86-64 AVX2 core, order 300: the diagonal blocks 128 → 65 µs; eight rows did no better).
 
constexpr std::size_t numerical::detail::cholesky_together_width {16}
 The narrowest Cholesky diagonal block whose rows go together: in a block of 8, the groups' loops cost more than the chains save (order 8, one arm64 core: 0.21 → 0.23 µs).
 
constexpr std::size_t numerical::detail::cholesky_one_panel {48}
 The order below which the Cholesky factorisation is one panel: no trailing product, whose packing the few panels of a small order do not repay (order 17 on one thread: 0.8 µs whole, 1.3 µs in panels of 16). Panels of 16 win from order 40 on x86-64 and from 48 on arm64.
 
constexpr std::size_t numerical::detail::cholesky_rows {64}
 The rows of one chunk of a Cholesky panel's rows below it, solved together along each column.
 
constexpr std::size_t numerical::detail::cholesky_update_columns {64}
 The fewest columns of the trailing block one Cholesky update's product takes: each product packs every row below its columns again, a panel's width apart the packing outweighed the products on the AMX (M1 Pro, order 128: 61 → 53 µs), and the triangle a wider block computes past the diagonal is wasted.
 
constexpr std::size_t numerical::detail::cholesky_update_rows {256}
 The rows of one tile of a Cholesky update: the tiles of a panel's update, each one product on one thread, share the threads in one parallel loop, where a parallel product for each block of columns started and joined the threads some thirty times a panel.
 
template<typename T >
constexpr carried_t< T > numerical::detail::rescue_below {std::is_same_v<value_range_t<T>, float> ? 0x1p-60 : 0x1p-500}
 The magnitude under which rescue_factor scales a T up: about the square root of the smallest normal number of its range, or below it (2⁻⁵⁰⁰ for a long double, whose range is the platform's).
 
constexpr double numerical::detail::plain_squares_low {0x1p-900}
 The smallest plain sum of squares plain_or_at_scale keeps: a term that underflowed is below 2⁻¹⁰²², so a sum this large loses at most count · 2⁻¹²² of itself to them.
 
constexpr double numerical::detail::plain_squares_high {0x1p900}
 The largest plain sum of squares plain_or_at_scale keeps: no term of it overflowed.
 
constexpr std::size_t numerical::detail::finite_chunk {std::size_t {1} << 15U}
 The elements all_finite_shared gives a thread at a time.
 
template<typename T >
constexpr bool numerical::detail::real_rows {std::is_same_v<T, double> || std::is_same_v<T, float>}
 Whether a solve of T goes by rows of real terms (lu_decomposition's solve_narrow): double and float.
 
constexpr std::size_t numerical::detail::triangular_block {32}
 The rows triangular_halves solves one by one; past them, by halves of a multiple of them.
 
constexpr std::size_t numerical::detail::triangular_slice {64}
 The columns of the right-hand sides a thread takes in triangular_halves' rows one by one.
 
constexpr std::size_t numerical::detail::lu_tall_ratio {2}
 The ratio of rows to columns up to which lu_factors factorises a tall matrix as the square of it beside zero columns (m³ / 3, by the blocked LU), past which by tall_lu_columns (m n² on narrow products): the two even near twice as tall as wide (arm64, 1200 rows).
 
constexpr std::size_t numerical::detail::qr_block {32}
 The reflectors of one panel of the blocked QR.
 
constexpr std::size_t numerical::detail::qr_look_ahead_threads {3}
 The fewest threads for which reflect_in_columns looks ahead, a panel factorised while the threads update the columns past it: on two, one thread would update the rest alone (ten AVX-512 cores, order 1024: 29.4 ms as it is, 36.3 looking ahead), from three a panel no longer waits for the update (four threads 22.1 → 16.5 ms, eight 19.8 → 13.9).
 
constexpr std::size_t numerical::detail::qr_update_slice {32}
 The fewest columns a task of reflect_in_columns' look-ahead updates: each task repacks the block, which narrow slices pay for too often (fixed slices of 64 columns on one thread, order 1024: 41 → 61 ms; with a slice per thread, a least of 32 or of 64 alike).
 
constexpr std::size_t numerical::detail::qr_transpose_tile {32}
 The side of the tiles in which the QR transposes (transpose_into): a tile's rows and columns both stay in the cache, where a whole column read across rows misses on every element.
 
constexpr std::size_t numerical::detail::jacobi_sweeps {60}
 The sweeps a Jacobi method may take: it converges quadratically, in under 15 on every matrix measured; the bound turns a non-convergence into an error instead of a hang.
 
constexpr std::size_t numerical::detail::corrected_product_least {512}
 The rows from which corrected_hermitian_product shares its coefficients and bands with the threads: on six x86-64 AVX2 cores from 256 (below, eigh of order 128 took 13 % longer), on an M1 Pro from 512 (from 256, eigh of order 512 on eight cores took 3 to 9 % longer).
 
constexpr std::size_t numerical::detail::tridiagonal_block {32}
 The reflections of one panel of the blocked tridiagonal reduction.
 
constexpr std::size_t numerical::detail::tridiagonal_band {512}
 The rows of each band of the tridiagonal reduction's trailing update: a band reaches its diagonal, so a wider one computes more of the upper triangle the reduction never reads, a narrower one runs the product kernel on smaller products.
 
constexpr std::size_t numerical::detail::ql_steps_per_value {30}
 The implicit QL steps the tridiagonal eigensolver may take per eigenvalue, as LAPACK's dsteqr bounds them (30 n in all): it converges cubically, in two or three per eigenvalue.
 
constexpr std::size_t numerical::detail::divide_leaf {25}
 The order up to which tridiagonal_divide_and_conquer diagonalises by implicit QL.
 
constexpr std::size_t numerical::detail::secular_iterations {100}
 The iterations one root of the secular equation may take: it converges in a few; the bound turns a non-convergence into an error instead of a hang.
 
constexpr std::size_t numerical::detail::lowner_block {32}
 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 numerical::detail::first_touch_chunk {std::size_t {1} << 15}
 The elements a task of workspace_of touches first: 64 pages of 4 KiB, so a buffer of a few megabytes spreads over every core.
 
constexpr std::size_t numerical::detail::kept_workspace {std::size_t {1} << 18}
 The most elements a buffer of a thread's merge_workspace keeps from one decomposition to the next: 2 MiB, every buffer an eigh of order 512 needs, so a thread keeps at most 8 MiB.
 
constexpr std::size_t numerical::detail::pencil_block {64}
 The columns reduce_pencil reduces a block at a time, as LAPACK's sygst by its block size.
 
template<typename T >
constexpr std::size_t numerical::detail::pencil_reduction_least {is_complex_number<T> ? 3072 : 2048}
 The order from which a pencil's standard form is reduced by blocks (reduce_pencil): half the operations of two whole triangular solves, but a block at a time, where the two solves share their columns among the threads whole. Below it the solves ran faster: ten AVX-512 cores up to order 1100 or so, six AVX2 cores up to 500, the M1 Pro (its products on AMX) up to some 2000 real and 2500 complex. From it: order 3072, six AVX2 cores 683 → 335 ms (complex 1749 → 884), ten AVX-512 cores 423 → 224 ms (complex 900 → 528), M1 Pro 204 → 161 ms (complex 724 → 684). One order whatever the threads: the bits of C do not depend on their number.
 

Detailed Description

The LU, Cholesky and QR factorisations and the symmetric and Hermitian eigen-decompositions.

numerical::lu_decomposition factorises a square matrix once (Gaussian elimination with partial pivoting — an in-place P A = L U), then answers any number of queries cheaply: numerical::lu_decomposition::solve a system, its numerical::lu_decomposition::determinant, or its numerical::lu_decomposition::inverse. Free numerical::solve, numerical::determinant and numerical::inverse are one-shot conveniences over it.

The scalar T must be a field (support division) — double, std::complex<double>, … — and the partial pivoting is numerically stable for well-conditioned systems. A singular matrix has a zero determinant; asking it to solve or invert throws numerical::singular_matrix_error.

Every factorisation here refuses an infinite or NaN entry where it starts, with a numerical::non_finite_error, since none of them means anything on one and the iterative ones would stop at once and return plausible values.

Definition in file factorizations.hpp.