diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 37 |
1 files changed, 16 insertions, 21 deletions
@@ -1,5 +1,4 @@ -This is a small C++ dense numerical linear algebra library, with a companion experiments directory -for evaluating performance. +This is a small C++ dense numerical linear algebra library. I mostly follow Trefethen & Bau, "Numerical Linear Algebra" and Golub & Van Loan, "Matrix Computations." The implementation uses `NEON` SIMD on ARM64 systems when available. @@ -11,7 +10,7 @@ The library is packaged as a C++20 named module (`linalgebra`): - CMake 4.1.x - Ninja - LLVM Clang ≥ 18 with libc++ (Homebrew LLVM 22 is what's tested; AppleClang - doesn't yet support module dependency scanning) + doesn't yet support C++20 module dependency scanning) ```bash cmake -S . -B build -G Ninja -DCMAKE_CXX_COMPILER=/opt/homebrew/opt/llvm/bin/clang++ @@ -56,25 +55,21 @@ ctest --test-dir build --output-on-failure - LU factorization with partial pivoting (`lu_factor`, `lu_solve`) - QR factorization — classical GS, modified GS, and Householder (`qr_classical_gs`, `qr_modified_gs`, `qr_householder`) -- Rank-revealing QR — Householder with column pivoting (`qr_colpiv`); reports numerical rank - and ensures |R(i,i)| ≥ |R(i+1,i+1)| +- Rank-revealing QR — Householder with column pivoting (`qr_colpiv`) - Eigenvalue computation via QR iteration: - - Unshifted QR (`eigenvalues_unshifted`) — linear convergence, T&B Algorithm 28.1 - - Wilkinson-shifted QR (`eigenvalues_shifted`) — typically cubic convergence, T&B Lecture 29 - - Hessenberg + Givens QR (`eigenvalues_hessenberg`) — O(n²) per step after one O(n³) reduction; - ~10–30× faster than `eigenvalues_shifted` for n ≥ 50 - - Francis double-shift QR (`eigenvalues_francis`) — implicit bulge chasing on Hessenberg form; - handles complex conjugate eigenvalue pairs without complex arithmetic; robust subdiagonal + - 2×2 block deflation with exceptional shifts (GVL §7.5) + - Unshifted QR (`eigenvalues_unshifted`) + - Wilkinson-shifted QR (`eigenvalues_shifted`) + - Hessenberg + Givens QR (`eigenvalues_hessenberg`) + - Francis double-shift QR (`eigenvalues_francis`) - Cholesky factorization (`cholesky_factor`, `cholesky_solve`) - Symmetric tridiagonalization -- Eigenvectors via inverse iteration (eigenvectors_inverse_iteration) -- SVD — Golub-Kahan bidiagonalization + QR (svd) -- Conjugate Gradient (solve_cg) -- GMRES (solve_gmres) -- BiCGSTAB (solve_bicgstab) +- Eigenvectors via inverse iteration (`eigenvectors_inverse_iteration`) +- SVD — Golub-Kahan bidiagonalization + QR (`svd`) +- Conjugate Gradient (`solve_cg`) +- GMRES (`solve_gmres`) +- BiCGSTAB (`solve_bicgstab`) - Condition number estimation -- Preconditioners (precond_jacobi, precond_ilu0) -- Least squares solver (lstsq) -- Arnoldi iteration (arnoldi) -- Matrix exponential (expm) +- Preconditioners (`precond_jacobi`, `precond_ilu0`) +- Least squares solver (`lstsq`) +- Arnoldi iteration (`arnoldi`) +- Matrix exponential (`expm`) |