The C++ library#
#include <numerical/numerical.hpp> brings in the whole library, in namespace numerical; C++
documents every class and the Doxygen reference every free function. This page says what is there and which
algorithm each part runs.
Using it#
The headers need a C++20 compiler and the threads library. numerical::numerical is the CMake target, through
add_subdirectory, FetchContent, or an installed config package:
# After `cmake --install <build> --prefix <prefix>`:
find_package(numerical CONFIG REQUIRED)
target_link_libraries(app PRIVATE numerical::numerical)
-DNUMERICAL_BUILD_BLAS=ON also builds the numerical_blas shared library (BLAS and LAPACK for other programs). Under GCC, compile with
-ffp-contract=on, and under Clang for arm64 with -mllvm -force-ordered-reductions=false; Reproducibility and threads
says why.
Supported toolchains#
These are the toolchains each push is built and tested with; an older one may work, and is not tested:
Toolchain |
Where |
|---|---|
GCC 14 |
Linux x86-64: the test suite, under ASan and UBSan too |
Clang 21 |
Linux x86-64: the test suite, under ASan and UBSan too |
GCC 13 (Ubuntu 24.04’s) |
Linux arm64: the CMake build, tests and install |
MSVC (Visual Studio 2022) |
Windows x64: the CMake build, tests and install |
Apple Clang 16 |
macOS arm64: the local gate ( |
CMake 3.16 or newer; Python 3.10 or newer for the binding. The x86-64 kernels are checked on an emulated AVX-512 processor in CI.
Containers#
numerical::vector<T>: a dense, value-semantic vector: element-wise arithmetic, scalar multiplication, dot product, tolerance comparison, shape checks.numerical::matrix<T>: a dense, row-major, value-semantic matrix: element-wise arithmetic, scalar, matrix–vector and matrix–matrix products, transpose, tolerance comparison, shape checks.numerical::tensor<T>: a dense, row-major, N-dimensional tensor (rank 1 a vector, rank 2 a matrix, rank 0 a scalar; built directly or from avectoror amatrix).tensor::transposed(axes)andtensor::slicedgive views (Tensors and dtypes),contiguous()says whetherdata()copies.einsum: Einstein-summation index notation for contractions and general products, as in NumPy and PyTorch, the unifying primitive of the algebra:"ij,jk->ik"is the matrix product,"i,i->"the dot product,"ij->ji"the transpose,"ii->"the trace,"i,j->ij"the outer product,"ij->i"a row reduction. It takes one or more operands and sums over every label absent from the output, in a deterministic order.Arithmetic on tensors (
tensor_ops.hpp):+ - * /element by element with NumPy’s broadcasting;sum,mean,max,minof every element or along an axis (sums by NumPy’s pairwise blocks);reshape; andzeros,ones,full,eye,arange,linspace.
Factorisations and solvers#
lu_decomposition<T>: an LU factorisation (partial pivoting) computed once and reused:solve(any number of right-hand sides),determinant,inverse, andlog_determinant()(NumPy’sslogdet, which does not underflow where the determinant does). The freesolve,determinantandinverseare one-shot conveniences.cholesky_decomposition<T>:A = L Lᴴfor a Hermitian positive-definite matrix (about twice as cheap as LU): the factorlower(),solveanddeterminant; it throwsnot_positive_definite_errorotherwise.ldl_decomposition<T>: the symmetric indefinite factorisationA = L D Lᴴ(orL D Lᵀ) of a symmetric or Hermitian matrix, asscipy.linalg.ldl(Bunch and Kaufman’s pivoting, LAPACK’ssytrf/hetrf, by panels from order 384;Dwith blocks of order 1 and 2), from either triangle.qr_decomposition<T>:A = Q Rby Householder reflections, soQstays orthonormal to rounding however ill-conditionedAis, for anm × nmatrix of any shape, as NumPy’s reducedqr:q()(m × k) andr()(k × n),k = min(m, n)(qr_mode::complete:q()m × m,r()m × n, the reduced factors extended), and form ≥ na least-squaressolveofA x ≈ b, which throwssingular_matrix_errorwhenAis rank-deficient.pivoted_qr_decomposition<T>:A P = Q Rwith column pivoting, asscipy.linalg.qr(a, pivoting=True)(LAPACK’sgeqp3),R’s diagonal revealing the rank.solve_triangular(a, b, lower, op, unit_diagonal):A X = B,Aᵀ X = BorAᴴ X = B(triangular_op) for a triangularA, as SciPy’s: its lower or upper triangle read, the other never;n² koperations, wheresolvefactorises first.solve_banded(l, u, ab, b)andsolveh_banded(ab, b, lower): banded systems in LAPACK’s diagonal-ordered form, asscipy.linalg’s (gbsv,pbsv);solve_toeplitz(c, r, b)(Levinson’s recursion) andsolve_circulant(c, b)(the Fourier transform); the matricestoeplitz,hankel,circulantandblock_diag.lstsq(a, b): the minimum-norm least-squares solution ofA x ≈ b, as NumPy’s, for any shape and rank (from the SVD),ba vector or a matrix of right-hand sides (assolve(a, b)takes too);least_squares(a, b)adds the residuals, the rank and the singular values NumPy returns beside it;pinv(a)from the same SVD.lstsq,least_squares,pinvandmatrix_ranktake arank_cutoff: NumPy’s default,rank_cutoff::relative(r)(rcond,rtol) orrank_cutoff::absolute(t)(tol);pinv(a, cutoff, true)andmatrix_rank(a, cutoff, true)take a Hermitianaby its eigendecomposition, its lower triangle alone read.
Scalar types#
The factorisations and solvers take a floating-point field (numerical::field: float, double, long double and
their complex forms), so that an integer matrix is refused at compile time. How far each carries its scalar:
LU (
lu_decomposition,solve), Cholesky and the unpivoted QR compute in the scalar itself: along doublematrix is factorised tolong double’s precision.The SVD takes any field and computes in
double: its singular values aredouble, and along doublematrix’s factors hold adouble’s precision. Wherelong doublereaches pastdouble’s range (x86-64’s 80 bits), a matrix one of whose nonzero singular values lies outsidedouble’s normal numbers is refused (argument_error) rather than answered 0 or ∞.The eigendecompositions (
eigen_decomposition,symmetric_eigen,hermitian_eigen), the Schur form, the pivoted QR, LDLᴴ and the generalized forms are ofdoubleandstd::complex<double>; the class templates among them takenumerical::double_fieldand refuse another scalar by that name. Afloatmatrix through the Python binding is computed indoubleand narrowed, below order 500; from order 500,solve,inv,det,slogdet,cholesky,lu_factorandlu_solvefactorise it infloat(see Linear algebra).
Eigenvalues and singular values#
symmetric_eigen: eigenvalues (ascending) and eigenvectors of a real symmetric matrix (A = V Λ Vᵀ): Householder tridiagonalisation by panels, then divide and conquer, as LAPACK’sdsyevd(most of the work in matrix products); implicit QL (eigen_method::tridiagonal_ql,dsyev’s) or cyclic Jacobi rotations (eigen_method::jacobi) on request.symmetric_eigenvalues(a)gives the values alone (NumPy’seigvalsh).hermitian_eigen: the same for a complex Hermitian matrix (real eigenvalues, a unitaryV), reduced to a real tridiagonal by Householder reflections and unit phases, then diagonalised by divide and conquer, as LAPACK’szheevd.symmetric_eigen(a, b),hermitian_eigen(a, b): the pencilA x = λ B x,Bpositive definite, asscipy.linalg.eigh(a, b)(LAPACK’ssygvd):B = L Lᴴ,L⁻¹ A L⁻ᴴdiagonalised, the vectorsB-orthonormal.eigen_decomposition<T>: the eigenvalues and right eigenvectors of a general real or complex square matrix, complex either way, asnumpy.linalg.eig(LAPACK’sdgeev/zgeev: balancing, blocked Hessenberg reduction, the multishift QR algorithm with aggressive early deflation);values(),vectors(), andeigenvalues(a)without the vectors (aseigvals).schur_decomposition<T>:A = Z T Zᴴ, asscipy.linalg.schur(LAPACK’sdgees/zgees, from the same reduction and iterations):t()quasi-triangular for a real matrix (a pair a 2 × 2 block in standard form), triangular for a complex one,z()orthogonal or unitary;values()inT’s order; given a predicate on the eigenvalues, or bysort(select)andreorder(chosen)afterwards, those selected moved to the leading block (LAPACK’strsen, MATLAB’sordschur),leading()their count.generalized_schur: the generalized Schur decomposition of a complex pencil,A = Q S ZᴴandB = Q T ZᴴwithSandTtriangular, asscipy.linalg.qz(a, b, output="complex")(LAPACK’szgges: QZ iterations with single shifts), reordered asordqz(ztgsen’s exchanges, refused where they would not keep the pencil triangular).real_generalized_schur: the generalized real Schur decomposition of a real pencil,A = Q S ZᵀandB = Q T ZᵀwithSquasi-triangular (2 × 2 blocks for conjugate pairs) andTtriangular, asscipy.linalg.qz(a, b)(LAPACK’sdgges: the operands scaled into range,dhgeqz’s double shifts), reordered asordqz(dtgsen’s exchanges of 1 × 1 and 2 × 2 blocks, refused as LAPACK refuses them).generalized_eigenvectors(d, left): the right (or left) eigenvectors of a pencil from its generalized Schur form, complex or real (real_generalized_schur, its 2 × 2 blocks made triangular first), as LAPACK’sztgevcandscipy.linalg.eig(a, b)(unit 2-norm).svd_decomposition<T>: the singular value decompositionA = U Σ Vᴴof a real or complexm × nmatrix, any shape: a Householder QR, then Golub–Kahan bidiagonalisation ofR(by panels, for a real one) and divide and conquer, as LAPACK’sdgesdd; implicit-shift QR (svd_method::bidiagonal_qr,dgesvd’s) or one-sided Jacobi onR(svd_method::jacobi, which gives every singular value to high relative accuracy) on request.singular_values()(descending),u()(m × k),v()(n × k) andvh(), withk = min(m, n)(full = true:u()m × mandv()n × n, the thin factors extended by an orthonormal basis of the complement);UandVstay orthonormal for a rank-deficientA.singular_values(a): the singular values without the vectors, by dqds as LAPACK’sdlasq1(a bidiagonal’s each to high relative accuracy), andmatrix_rank(a)from them.
Matrix functions and equations#
expm(a): the matrix exponential, asscipy.linalg.expm(Al-Mohy and Higham’s scaling and squaring of a Padé approximant, 2009);expm_frechet(a, e)andexpm_cond(a), its Fréchet derivative and condition number (Al-Mohy and Higham’s algorithm, 2009, or the exponential of[[A, E], [0, A]]).logm(a): the principal logarithm, asscipy.linalg.logm(inverse scaling and squaring, Al-Mohy and Higham 2012, on the Schur form; the norms exact where SciPy estimates them).sqrtm(a): the principal square root, asscipy.linalg.sqrtm(the Schur method, real for a real matrix with no real eigenvalue below 0;complex_sqrtmthe complex one of a real matrix).fractional_matrix_power(a, p):Ato a real power, asscipy.linalg.fractional_matrix_power(Higham and Lin’s Schur–Padé algorithm, 2013).funm(a, f): a function of a matrix, asscipy.linalg.funm: Parlett’s recurrence on the Schur form where the eigenvalues are well apart (SciPy’s error estimate); where they gather, Davies and Higham’s Schur–Parlett algorithm with each cluster by Cauchy’s integral (fthen also evaluated on circles about them); a Hermitian matrix by its eigendecomposition.plan_funmandfinish_funmsplit it around the evaluation off.solve_sylvester(a, b, q):A X + X B = Q, asscipy.linalg.solve_sylvester(Bartels and Stewart’s method, the triangular equation by blocks as LAPACK’strsyl).solve_continuous_are(a, b, q, r, e, s)andsolve_discrete_are: the stabilising solutions of the algebraic Riccati equations, asscipy.linalg’s (the extended pencil, balanced, its stable deflating subspace from the sorted generalized Schur form, real for real operands; withe, the balancing scales it as it scales the pencil, where SciPy 1.18 does not, scipy/scipy#26555).
Fourier transforms#
numerical::fft(fft.hpp): the discrete Fourier transform along an axis, asnumpy.fft:fft,ifft,rfft,irfft,hfft,ihfftandfftshift, NumPy’s points (cut or padded with zeros) and scalings (fft_norm). Any length: Stockham passes of radices 2 to 16 and every prime to 61, Bluestein’s convolution past them; twiddle factors computed in double-double, so each is the correctly rounded root. Two sets of bits only, each the same on every machine and compiler: the portable path’s (products rounded apart) and the vector paths’ (NEON, AMX, AVX2 and AVX-512: one fused complex product).dct,idct,dst,idst: the cosine and sine transforms ofscipy.fft, types 1 to 4, its norms andorthogonalize, by the real (types 1 to 3) or complex (type 4) transform: DCT-II by Makhoul’s reordering, DCT-III its inverse, the sines from the cosines.
Building from source#
The test suite, the binding and the lint tooling need SciForge checked out beside the repository;
CONTRIBUTING.md gives the layout and the gates run
before each commit, push and release, and RELEASING.md the release procedure. The single steps:
make test # build and run the test suite
make coverage # line-coverage summary + HTML report
make sanitize # tests under AddressSanitizer + UndefinedBehaviorSanitizer
make python # the Python extension, in place
make python-test # the binding's suite
make python-sanitize # the Python suite under the sanitizers (Linux, GCC)
make lint # clang-tidy
make format # uncrustify, in place
make doc # API reference (Doxygen) with embedded coverage
make help # every other target
make test CXX=g++-14 overrides the compiler. The binding’s suite includes a seeded differential fuzzer that checks
hundreds of random einsum specifications and linear-algebra problems against NumPy within tolerance, when NumPy is
importable, as in CI.