|
NumericAL
A header-only C++20 lexer built on REAL
|
The singular value decomposition and what it answers: the singular values, least squares, the pseudo-inverse and the numerical rank. The bidiagonal reduction and its iterations, divide and conquer and one-sided Jacobi live here, apart from the factorisations they build on (factorizations.hpp). More...
#include <algorithm>#include <array>#include <atomic>#include <bit>#include <cfloat>#include <cmath>#include <complex>#include <concepts>#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 "dqds.hpp"#include "factorizations.hpp"Go to the source code of this file.
Classes | |
| struct | numerical::detail::arrow_workspace |
The buffers merge_arrow works in, kept by each thread from one join to the next (thread_arrow_workspace): mapping their pages anew took 11–16 % of an svd of order 64 to 512 on one x86-64 core, 13–20 % on six. More... | |
| struct | numerical::detail::bidiagonal_node |
| One block of bidiagonal_divide's tree: the bidiagonal it decomposes (its own copies scaled by a power of two, or its parent's), the two halves it splits into, and its decomposition once solved. More... | |
| class | numerical::svd_decomposition< T > |
The singular value decomposition A = U Σ Vᴴ of an m × n matrix. More... | |
| struct | numerical::detail::shifted_tridiagonal |
The factors of T − λ I for a symmetric tridiagonal T, as LAPACK's dlagtf leaves them: P (T − λ I) = L U, U of diagonal a and two superdiagonals b and d, L's multipliers in c, the row interchanges in swapped. More... | |
| struct | numerical::eigen_subset< T > |
| Some eigenvalues of a Hermitian matrix and their eigenvectors (hermitian_eigen_subset). More... | |
| struct | numerical::least_squares_solution< T > |
A least-squares solution and what numpy.linalg.lstsq reports beside it (least_squares). More... | |
Namespaces | |
| namespace | numerical |
| The NumericAL public API. | |
| namespace | numerical::detail |
Enumerations | |
| enum class | numerical::svd_method { numerical::bidiagonal_qr , numerical::jacobi , numerical::divide_and_conquer } |
How numerical::svd_decomposition computes the decomposition of R, after a Householder QR. More... | |
Functions | |
| template<typename T > | |
| void | numerical::detail::one_sided_jacobi (buffer< T > &w, buffer< T > &v, std::size_t n, std::size_t max_sweeps) |
One-sided (Hestenes) Jacobi on the columns of the n × n row-major w: plane rotations, accumulated into v, until every pair of columns is orthogonal to rounding. The column norms are then the singular values of the input, each to high relative accuracy. | |
| template<typename T > | |
| void | numerical::detail::form_bidiagonal_bases (const std::vector< buffer< T > > &left, std::vector< buffer< T > > right, const std::vector< T > &left_tau, const std::vector< T > &right_tau, const buffer< T > &left_phase, const buffer< T > &right_phase, std::size_t n, buffer< T > &ut, buffer< T > &vt) |
The bases of a bidiagonal reduction from its reflectors: U_b = (H₀ H₁ …) diag(conj left phases) and V_b = (H'₀ H'₁ …) diag(right phases), each formed by blocks of reflectors through the matrix product kernel, as QR's Q is, or a reflector at a time below bidiagonal_basis_crossover. | |
| template<typename T > | |
| void | numerical::detail::bidiagonalize_unblocked (buffer< T > &b, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form) |
bidiagonalize_unblocked of the square n × n row-major b. | |
| template<typename T > requires std::is_floating_point_v<T> || split_complex<T> | |
| void | numerical::detail::bidiagonalize (buffer< T > &b, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form=true) |
Reduces the square n × n row-major b to upper-bidiagonal form, B = U_b D V_bᴴ, by panels of bidiagonal_block reflections from each side, as LAPACK's dgebrd and dlabrd (zgebrd, zlabrd): the matrix a panel's later steps see is B − V Ȳᵀ − X Ūᵀ (V, U the reflectors, Y, X what they move, Ȳ and Ū held conjugated, so a complex matrix's update is a plain product), applied to the one column and the one row each step needs; the trailing block takes it after the panel, through the matrix product kernel. A real bidiagonal keeps its signs, which the iterations that follow take; a complex one is turned real as bidiagonalize_unblocked turns it, a unit phase on row k before its right reflection and on column k + 1 once that column comes to be reflected. | |
| template<typename T > | |
| void | numerical::detail::bidiagonalize_unblocked (buffer< T > &b, std::size_t rows, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form) |
Reduces the rows × n row-major b (rows ≥ n) to real upper-bidiagonal form, B = U_b D V_bᴴ with D real and n × n, by Householder reflections alternately from the left and the right (Golub–Kahan, LAPACK's dgebd2), the left ones rows − k long; the bases formed for a square b alone. | |
| template<typename T > requires (!std::is_floating_point_v<T> && !split_complex<T>) | |
| void | numerical::detail::bidiagonalize (buffer< T > &b, std::size_t n, buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, bool form=true) |
bidiagonalize_unblocked, for any T the panels do not take (a complex long double). | |
| template<typename T > | |
| void | numerical::detail::bidiagonal_qr (buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, std::size_t n, std::size_t max_steps) |
The singular values of the real upper bidiagonal (d, e) by implicit-shift QR with deflation (the Golub–Kahan–Reinsch iteration, LINPACK's dsvdc), the rotations accumulated into the rows of ut and vt. Each block's bulge is chased from its larger end, as LAPACK's dbdsqr chases it: from the top only, a block graded up (its small entries first) never converged. | |
| template<typename Entry > | |
| double | numerical::detail::largest_magnitude (std::size_t rows, std::size_t cols, const Entry &entry) |
The power_of_two_scale of the largest magnitude of entry over rows rows of cols: by bands of rows on the threads, each band's largest then the largest of those (a maximum, the same whatever the order). | |
| template<typename T > | |
| matrix< T > | numerical::detail::adjoint (const matrix< T > &a) |
The conjugate transpose of a, as numerical::transpose copies (by blocks, on the threads). | |
| double | numerical::detail::singular_secular_root (const buffer< double > &d, const buffer< double > &z, std::size_t i, std::size_t max_iterations, double *below, double *above) |
Singular value i of the arrow M whose first row is z and whose diagonal is d (d₀ = 0, d strictly ascending): root σ of 1 + Σⱼ zⱼ²/(dⱼ² − σ²) = 0, as LAPACK's dlasd4. | |
| void | numerical::detail::rotate_columns (buffer< double > &m, std::size_t cols, std::size_t a, std::size_t b, double c, double s) |
Columns a and b of the row-major m (cols per row) rotated: a ← c a + s b, b ← c b − s a. | |
| arrow_workspace & | numerical::detail::thread_arrow_workspace () |
| The calling thread's arrow_workspace, kept from one decomposition to the next. A join uses it whole on one thread and nests no other join; release_large_arrow_workspace lets a large buffer go after. | |
| void | numerical::detail::release_large_arrow_workspace (arrow_workspace &work) |
Releases the buffers of work longer than kept_workspace. | |
| void | numerical::detail::merge_arrow (buffer< double > &d, buffer< double > z, double alpha, double beta, buffer< double > &u, buffer< double > &v, std::size_t n, std::size_t m, std::size_t split, arrow_workspace &work) |
The singular value decomposition of the arrow M (first row z, diagonal d, d₀ = 0), carried into the bases u (n × n) and v (m × m, its first n columns the arrow's; a last, null column when m = n + 1), as LAPACK's dlasd1–dlasd3: on return d holds the singular values ascending and u, v the singular vectors, v's null column last. | |
| std::size_t | numerical::detail::plan_bidiagonal (std::vector< bidiagonal_node > &nodes, const double *d, const double *e, std::size_t n, std::size_t extra, std::size_t depth) |
Appends the block (d, e, n, extra) and everything below it to nodes, parents before children, each scaled to work near unit size by a power of two (exactly): the secular equation works on squares, which overflow past 1e154. | |
| void | numerical::detail::start_bidiagonal_node (bidiagonal_node &node) |
Its singular values and vectors into node's, from scratch: u zero, v the identity. | |
| void | numerical::detail::solve_bidiagonal_leaf (bidiagonal_node &node) |
Decomposes the leaf node by implicit-shift QR. | |
| void | numerical::detail::join_bidiagonal_node (bidiagonal_node &node, const bidiagonal_node &one, const bidiagonal_node &two, arrow_workspace &work) |
Joins the two decomposed halves of node, one and two, by merge_arrow, node started (start_bidiagonal_node). | |
| void | numerical::detail::unscale_bidiagonal_node (bidiagonal_node &node) |
The singular values of a solved node scaled back. | |
| void | numerical::detail::join_bidiagonal_halves (std::vector< bidiagonal_node > &nodes, std::size_t index, arrow_workspace &work) |
Joins the halves of nodes' block index in work, then lets them go. | |
| void | numerical::detail::solve_bidiagonal_subtree (std::vector< bidiagonal_node > &nodes, std::size_t index, arrow_workspace &work) |
Decomposes the block index of nodes and everything below it, each block right after its halves. | |
| void | numerical::detail::bidiagonal_divide (const double *d, const double *e, std::size_t n, std::size_t extra, buffer< double > &sigma, buffer< double > &u, buffer< double > &v) |
The singular value decomposition of the upper bidiagonal n × (n + extra) (extra 0 or 1) with diagonal d[0…n-1] and superdiagonal e[0…n+extra-2] (e[n-1] the last column's entry when extra is 1), by divide and conquer, as LAPACK's dbdsdc: sigma ascending, u (n × n) and v (m × m, m = n + extra, the null vector last) row-major, their columns the singular vectors. | |
| template<typename T > | |
| void | numerical::detail::bidiagonal_divide_and_conquer (buffer< double > &d, buffer< double > &e, buffer< T > &ut, buffer< T > &vt, std::size_t n) |
The singular values of the upper bidiagonal (d, e) into d, descending, the singular vectors accumulated into the rows of ut and vt as bidiagonal_qr accumulates them, by divide and conquer (bidiagonal_divide): most of the work in matrix products. | |
| double | numerical::detail::singular_value_in_double (double x) noexcept |
A singular value of a decomposition carried in double: x itself. | |
| double | numerical::detail::singular_value_in_double (long double x) |
| A singular value of a long double matrix, computed in double at the matrix's scale and scaled back, as the double its type holds. Where long double's range is wider than double's (x86-64's 80 bits), one past double's normal numbers cannot be held, and the decomposition refuses the matrix rather than answer 0 or ∞. | |
| std::size_t | numerical::detail::numerical_rank (const vector< double > &sigma, std::size_t rows, std::size_t cols, rank_cutoff cutoff={}) |
How many of the singular values sigma of an rows × cols matrix exceed cutoff: its numerical rank (the first that many, where sigma is descending). | |
| template<typename T > | |
| T | numerical::detail::scaled_by_two (const T &x, int exponent) |
x times two to the exponent, exactly where the result is a normal number (no power of two is formed, so none overflows). | |
| template<typename U > | |
| std::complex< U > | numerical::detail::scaled_by_two (const std::complex< U > &x, int exponent) |
| scaled_by_two for a complex number, part by part. | |
| template<typename T > | |
| buffer< T > | numerical::detail::upper_inverse (const buffer< T > &r, std::size_t n) |
R⁻¹, upper triangular, of the n × n upper-triangular r (row-major): back substitution against the identity in parallel chunks of columns, each row's terms in registers (subtract_products). A chunk's rows past its last column stay zero; a zero on the diagonal leaves infinities or NaN. | |
| template<typename T > | |
| buffer< double > | numerical::detail::square_singular_values (buffer< T > b, std::size_t n, qd_index sweeps=dqds_sweeps) |
| template<typename T > | |
| std::optional< matrix< T > > | numerical::detail::lstsq_by_qr (const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff, buffer< double > &values, std::pair< buffer< T >, int > *const r=nullptr) |
The least-squares solution of A X ≈ B by a QR factorisation, of A, or of Aᴴ for a wide A (the minimum-norm solution), where it is the one the singular value decomposition gives: with A divided by a power of two near its largest magnitude, the bound 1 / ‖R⁻¹‖_F under its smallest singular value must stay qr_rank_margin times above cutoff of the bound ‖R‖_F over its largest, so that every singular value is far above the cutoff and the rank full (a zero on R's diagonal makes the first bound zero, or NaN, which fails). Else nothing. A fraction of the decomposition's work, the rest in matrix products. | |
| template<typename T > | |
| buffer< double > | numerical::detail::tall_singular_values (buffer< T > b, std::size_t rows, std::size_t n, qd_index sweeps=dqds_sweeps) |
The singular values of the square n × n row-major b, descending, without its vectors: those of its Golub–Kahan bidiagonal by dqds (dqds_singular_values), no basis formed; by the implicit-shift QR iteration (bidiagonal_qr) where dqds does not converge within sweeps steps per value. | |
| template<typename T > | |
| matrix< T > | numerical::detail::lstsq_from_svd (const svd_decomposition< T > &s, std::size_t rank, const matrix< T > &b) |
The minimum-norm least-squares solution of A X ≈ B from the singular value decomposition s of A (m × n), its first rank triplets: X = V Σ⁺ Uᴴ B. | |
| template<field T> | |
| vector< T > | numerical::lstsq (const matrix< T > &a, const vector< T > &b, rank_cutoff cutoff={}) |
The minimum-norm least-squares solution of A x ≈ b, as NumPy's lstsq gives it. | |
| template<field T> | |
| matrix< T > | numerical::lstsq (const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff={}) |
The minimum-norm least-squares solution of A X ≈ B for every column of B at once, as numpy.linalg.lstsq with a matrix right-hand side: one SVD of A, X = V Σ⁺ Uᴴ B; or, where a bound on the condition number shows the rank full with room to spare, the same solution to rounding by one QR factorisation (detail::lstsq_by_qr). | |
| template<field T> | |
| vector< double > | numerical::singular_values (const matrix< T > &a) |
The singular values of a, descending, without its singular vectors, as numpy.linalg.svd(a, compute_uv=False): the Householder R of a tall A (of Aᴴ when wide), its Golub–Kahan bidiagonal and the dqds algorithm on it (LAPACK's dlasq1, as dgesdd takes it without vectors), no basis formed. Each value to an absolute accuracy of the largest times the machine epsilon, as svd_decomposition's; those of a bidiagonal A each to high relative accuracy. | |
| template<field T> | |
| vector< double > | numerical::symmetric_eigenvalues (const matrix< T > &a) |
The eigenvalues of the real symmetric or complex Hermitian a, ascending, without its eigenvectors, as numpy.linalg.eigvalsh: its Householder tridiagonal (no basis formed) and the implicit QL iteration on it, no rotation kept. Only the lower triangle is read, and of the diagonal its real part. Each value to an absolute accuracy of the largest magnitude times the machine epsilon, as symmetric_eigen's; a graded tridiagonal's small values to their relative accuracy, as LAPACK's dsteqr keeps them. | |
| double | numerical::detail::scaled_tridiagonal (const vector< double > &d, const vector< double > &e, buffer< double > &diagonal, buffer< double > &off) |
The diagonal d and off-diagonal e of a symmetric tridiagonal matrix divided by the power of two of their largest magnitude (returned), e padded with a 0 to d's length, as the QL iteration takes them. | |
| vector< double > | numerical::tridiagonal_eigenvalues (const vector< double > &d, const vector< double > &e) |
The eigenvalues of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e, ascending, as scipy.linalg.eigvalsh_tridiagonal: the implicit QL iteration, no rotation kept, on the matrix divided by the power of two of its largest magnitude (as symmetric_eigenvalues runs it on the tridiagonal it forms). | |
| std::size_t | numerical::detail::sturm_count (const double *d, const double *e2, std::size_t n, double x, double pivmin) |
The number of eigenvalues below x of the symmetric tridiagonal of diagonal d and squared off-diagonal e2 (n and n − 1 entries), by Sturm's sequence: the negative pivots of T − x I, a pivot smaller than pivmin taken as −pivmin, as LAPACK's dlaebz. | |
| vector< double > | numerical::tridiagonal_eigenvalues (const vector< double > &d, const vector< double > &e, std::size_t first, std::size_t last) |
The eigenvalues of indices first to last (ascending, from 0) of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e, as LAPACK's dstebz (scipy.linalg.eigvalsh_tridiagonal with a selection): each by bisection of Gershgorin's interval on Sturm's counts, to ε ‖T‖ (LAPACK's tolerance when none is given), on the matrix divided by the power of two of its largest magnitude. n k operations a bisection step where the QL iteration takes n² for all. | |
| std::pair< std::ptrdiff_t, std::ptrdiff_t > | numerical::tridiagonal_eigenvalue_range (const vector< double > &d, const vector< double > &e, double low, double high) |
The indices [first, last] (ascending, from 0) of the eigenvalues in (low, high] of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e, by Sturm's counts (last < first where none lies there), as dstebz selects them with a range. | |
| void | numerical::detail::factor_shifted_tridiagonal (const double *diagonal, const double *off, std::size_t n, double lambda, shifted_tridiagonal &f) |
Factorises T − λ I, n from 2, T of diagonal diagonal and off-diagonal off, with partial pivoting as LAPACK's dlagtf: at each step the row of the larger entry relative to its row's size (the first where they tie). | |
| void | numerical::detail::solve_shifted_tridiagonal (const shifted_tridiagonal &f, std::size_t n, double *y, double &tol) |
Solves (T − λ I) x = y in place in y from factor_shifted_tridiagonal's factors, as LAPACK's dlagts (job −1): a pivot that would overflow the quotient, or is zero, moved away from zero by tol, then by twice as much, until it does not; tol, where 0, set first to ε times the factors' largest magnitude (ε itself if that is 0), for the next solves. | |
| void | numerical::detail::start_vector (std::size_t index, double *x, std::size_t n) noexcept |
A start vector of n entries in [−1, 1) for tridiagonal_eigenvectors' eigenvalue index, its own draw (splitmix64 from the index), so that each vector is the same on any number of threads. | |
| bool | numerical::detail::inverse_iteration (const buffer< double > &diagonal, const buffer< double > &off, std::size_t n, const buffer< double > &values, buffer< double > &z, std::size_t most_solves=5) |
The eigenvectors (rows of z, k × n) of the symmetric tridiagonal of diagonal diagonal and off-diagonal off (n from 2) for its eigenvalues values (k, ascending), as LAPACK's dstein: inverse iteration from a random vector, each solve of T − λ I scaled so that the iterate's largest entry reaches √(0.1 / n) once the eigenvector dominates, then two more; an eigenvalue within 10 ε |λ| of the one before moved up to that distance; the vectors of eigenvalues within 10⁻³ ‖T‖₁ of one another (a cluster) orthogonalised against the cluster's earlier ones at each step. The clusters on the threads. | |
| matrix< double > | numerical::tridiagonal_eigenvectors (const vector< double > &d, const vector< double > &e, const vector< double > &values) |
The orthonormal eigenvectors (the columns, in their order) of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e for the eigenvalues values, ascending (from tridiagonal_eigenvalues with indices, say), as LAPACK's dstein: inverse iteration (detail::inverse_iteration), some n operations a solve for each, where all the eigenvectors take n³; on the matrix divided by the power of two of its largest magnitude. Where an iterate does not converge or a cluster is too large, the vectors are the whole spectrum's (tridiagonal_eigen) of the eigenvalues nearest. | |
| std::pair< vector< double >, matrix< double > > | numerical::tridiagonal_eigen (const vector< double > &d, const vector< double > &e) |
The eigenvalues, ascending, and the orthonormal eigenvectors (the columns, in their order) of the real symmetric tridiagonal matrix of diagonal d and off-diagonal e, as scipy.linalg.eigh_tridiagonal: divide and conquer (LAPACK's dstedc, the eigenvectors by matrix products), the implicit QL iteration up to its leaves' order, on the matrix divided by the power of two of its largest magnitude. | |
| template<typename T > | |
| eigen_subset< T > | numerical::detail::hermitian_subset (const matrix< T > &a, const std::function< std::pair< std::ptrdiff_t, std::ptrdiff_t >(const vector< double > &, const vector< double > &, double)> &select, bool vectors, const std::string &name) |
hermitian_eigen_subset of the indices select gives from the tridiagonal form's diagonal and off-diagonal and the matrix's scale ([first, last], last < first for none), its vectors where vectors. select behind one type: one instance per T. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| eigen_subset< T > | numerical::hermitian_eigen_subset (const matrix< T > &a, std::size_t first, std::size_t last, bool vectors=true) |
The eigenvalues of indices first to last (ascending, from 0) of the real symmetric or complex Hermitian a, its lower triangle read, and their eigenvectors where vectors, as scipy.linalg.eigh(a, subset_by_index=[first, last]): the tridiagonal form (LAPACK's sytrd, hetrd), the eigenvalues by bisection (tridiagonal_eigenvalues, stebz), the vectors by inverse iteration (detail::inverse_iteration, stein) taken back through the reflections (ormtr, unmtr): past the reduction, n² k operations where the whole spectrum's vectors take n³ and more. On the matrix divided by the power of two of its largest magnitude. Where an iterate does not converge or a cluster of eigenvalues is too large, the vectors are the whole spectrum's by divide and conquer. | |
| template<typename T > requires std::same_as<T, double> || std::same_as<T, std::complex<double>> | |
| eigen_subset< T > | numerical::hermitian_eigen_subset_by_value (const matrix< T > &a, double low, double high, bool vectors=true) |
hermitian_eigen_subset of the eigenvalues in (low, high], as scipy.linalg.eigh(a, subset_by_value=[low, high]): their indices by Sturm's counts on the tridiagonal form (tridiagonal_eigenvalue_range); none, the vectors n × 0. | |
| template<typename T > | |
| least_squares_solution< T > | numerical::least_squares (const matrix< T > &a, const matrix< T > &b, rank_cutoff cutoff={}) |
lstsq, with the residuals, the rank and the singular values numpy.linalg.lstsq returns beside the solution: the residual sums of squares are given only where the solution is unique and need not be exact, A tall (m > n) and of full column rank, as NumPy gives them. | |
| template<typename T > | |
| matrix< T > | numerical::detail::hermitian_from_lower (const matrix< T > &a) |
The real symmetric or complex Hermitian matrix whose lower triangle is the square a's, and of its diagonal the real part. | |
| template<typename T > | |
| matrix< T > | numerical::detail::inverse_on_kept (const vector< double > &sigma, const matrix< T > &right, const matrix< T > &left, rank_cutoff cutoff) |
Σ_d right_d (1 / σ_d) left_dᴴ over the columns d of right (cols × k) and left (rows × k) whose sigma is above cutoff (of the largest magnitude in sigma): a pseudo-inverse from a singular value decomposition (right = V, left = U) or from an eigendecomposition (V both, σ the eigenvalues, signed). Through the matrix product kernel: summed term by term it ran five times as long as NumPy's at order 512. | |
| template<typename T > | |
| vector< double > | numerical::detail::hermitian_singular_values (const matrix< T > &a) |
The singular values of the real symmetric or complex Hermitian matrix whose lower triangle is a's: of the matrix made whole, for a scalar the eigendecompositions do not take (they compute in double). | |
| template<typename T > | |
| vector< double > | numerical::detail::eigenvalue_magnitudes (const matrix< T > &a) |
The magnitudes of the eigenvalues of the real symmetric or complex Hermitian a, its lower triangle read: its singular values, unordered. | |
| vector< double > | numerical::detail::hermitian_singular_values (const matrix< double > &a) |
hermitian_singular_values in double: the magnitudes of the eigenvalues, cheaper. | |
| vector< double > | numerical::detail::hermitian_singular_values (const matrix< std::complex< double > > &a) |
hermitian_singular_values in std::complex<double>: the magnitudes of the eigenvalues, cheaper. | |
| template<typename T > | |
| matrix< T > | numerical::detail::hermitian_pseudo_inverse (const matrix< T > &a, rank_cutoff cutoff) |
The pseudo-inverse of the real symmetric or complex Hermitian matrix whose lower triangle is a's: from the singular value decomposition of the matrix made whole, for a scalar the eigendecompositions do not take. | |
| matrix< double > | numerical::detail::hermitian_pseudo_inverse (const matrix< double > &a, rank_cutoff cutoff) |
hermitian_pseudo_inverse in double: V Λ⁺ Vᵀ from the eigendecomposition, cheaper. | |
| matrix< std::complex< double > > | numerical::detail::hermitian_pseudo_inverse (const matrix< std::complex< double > > &a, rank_cutoff cutoff) |
hermitian_pseudo_inverse in std::complex<double>: V Λ⁺ Vᴴ from the eigendecomposition, cheaper. | |
| template<field T> | |
| std::size_t | numerical::matrix_rank (const matrix< T > &a, rank_cutoff cutoff={}, bool hermitian=false) |
The numerical rank of a, as numpy.linalg.matrix_rank counts it: its singular values above cutoff. | |
| template<field T> | |
| matrix< T > | numerical::pinv (const matrix< T > &a, rank_cutoff cutoff={}, bool hermitian=false) |
The Moore–Penrose pseudo-inverse of the m × n a (n × m), as numpy.linalg.pinv gives it: V Σ⁺ Uᴴ, a singular value at or under cutoff counting as zero. | |
Variables | |
| constexpr double | numerical::detail::jacobi_tiny {std::numeric_limits<double>::min() / std::numeric_limits<double>::epsilon()} |
The sum of squares under which one-sided Jacobi judges a pair of columns over their norms: below it a square has lost digits to underflow (DBL_MIN / ε). | |
| constexpr double | numerical::detail::jacobi_large {1e150} |
The |ζ| past which one-sided Jacobi takes the rotation's tangent as 1 / (2|ζ|): ζ² stays finite under it. | |
| constexpr double | numerical::detail::cancelled {64.0} |
The fall of a column's norm, in units of √n ε, past which one_sided_jacobi takes what a rotation left of it for rounding alone. | |
| constexpr std::size_t | numerical::detail::svd_qr_steps_per_value {30} |
| The QR steps the bidiagonal singular value iteration may take per value: it converges in two or three; the bound turns a non-convergence into an error instead of a hang. | |
| constexpr std::size_t | numerical::detail::bidiagonal_crossover {128} |
The order below which a real bidiagonal reduction goes a reflection at a time, as LAPACK's dgebrd falls back to dgebd2: the panels' products are too small to pay for packing. Order 64: 33 % shorter on six x86-64 cores, 7 % on arm64; order 160: 30 % longer on arm64, where x86-64 still gains 8 %. | |
| constexpr std::size_t | numerical::detail::bidiagonal_basis_crossover {64} |
| The order below which the bases of a bidiagonal reduction are formed a reflector at a time: the blocks' packing and triangular factor cost more than they save. Order 32: 11 % shorter on six x86-64 cores, 12 % on arm64; order 96: 7 % longer on both. | |
| constexpr std::size_t | numerical::detail::bidiagonal_block {32} |
| The rows from which a step of the blocked bidiagonal reduction shares its coefficients and corrections with the threads: on x86-64 (six AVX2 cores, the reduction of order 512 −5 to −14 %, 1024 −12 %); never on arm64, where its serial part is smaller and the shared step gained nothing (M1 Pro, eight cores, order 1024 0.97 to 1.05 times as long). | |
| constexpr std::size_t | numerical::detail::bidiagonal_product_weight {1} |
| The weight of a multiply-add of the bidiagonal reduction's matrix-vector products, which read the trailing block once for each column: on x86-64 a thread shares them from a quarter of the work (six cores, singular values of order 256: 8.1 → 7.3 ms, 512: 35 → 30); on arm64 that slowed order 256 by 10 %. | |
| constexpr std::size_t | numerical::detail::sort_rows {64} |
| The rows a task of merge_arrow reorders in place, one row's buffer between them. | |
| constexpr std::size_t | numerical::detail::bidiagonal_leaf {32} |
| The order up to which bidiagonal_divide decomposes by implicit-shift QR. | |
| constexpr double | numerical::detail::qr_rank_margin {100.0} |
| How far above the rank cutoff a bound on the smallest singular value must stay for lstsq_by_qr to answer: nearer, the singular value decomposition decides the rank. | |
| constexpr std::size_t | numerical::detail::sturm_bisection_work {256} |
| One eigenvalue's bisection in parallel_for's units per order of the matrix: some 60 halvings, each a Sturm count whose step divides (some four multiply-adds). | |
| constexpr std::size_t | numerical::detail::inverse_iteration_cluster_most {64} |
The most eigenvalues tridiagonal_eigenvectors reorthogonalises together: a larger cluster's vectors come from the whole spectrum's divide and conquer, n k² reorthogonalisation passing its n³'s share. | |
The singular value decomposition and what it answers: the singular values, least squares, the pseudo-inverse and the numerical rank. The bidiagonal reduction and its iterations, divide and conquer and one-sided Jacobi live here, apart from the factorisations they build on (factorizations.hpp).
Definition in file svd.hpp.