From b8bc28c70a6f2b0e7de81e85a796303d514df008 Mon Sep 17 00:00:00 2001 From: y-jan137 Date: Fri, 20 Mar 2026 18:07:59 +0300 Subject: Update TODO --- README.md | 19 ++++++++++++++++++- include/qr.hpp | 6 ------ 2 files changed, 18 insertions(+), 7 deletions(-) diff --git a/README.md b/README.md index e3df582..497b50a 100644 --- a/README.md +++ b/README.md @@ -1,7 +1,7 @@ # Numerical Linear Algebra This repo contains a small C++ dense numerical linear algebra library for `double`, with a companion experiments directory for evaluating performance. -I mostly follow Trefethen & Bau, "Numerical Linear Algebra" +I mostly follow Trefethen & Bau, "Numerical Linear Algebra" and Golub & Van Loan, "Matrix Computations" The implementation supports compile-time SIMD backends for `AVX`, `AVX2`, `AVX512`, and `NEON` on `AArch64`/`ARM64` with FP64 vector support. ## Build @@ -36,6 +36,23 @@ ctest --test-dir build --output-on-failure - 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 +TODO: +- [ ] Cholesky factorization (cholesky) — for symmetric positive definite systems +- [ ] Rank-revealing QR — Householder QR with column pivoting (qr_colpiv) +- [ ] Symmetric tridiagonalization — Householder reduction before symmetric QR (tridiagonalize) +- [ ] Francis double-shift QR — bulge chasing for real matrices with complex conjugate eigenvalue pairs (eigenvalues_francis) +- [ ] Deflation — robust subdiagonal + 2×2 block deflation in Hessenberg QR +- [ ] Eigenvectors via inverse iteration (eigenvectors_inverse_iteration) +- [ ] SVD — Golub-Kahan bidiagonalization + QR (svd) +- [ ] Conjugate Gradient (solve_cg) — for symmetric positive definite systems +- [ ] GMRES (solve_gmres) — for general non-symmetric systems +- [ ] BiCGSTAB (solve_bicgstab) — lighter alternative to GMRES +- [ ] Condition number estimation — norm-based LINPACK estimator +- [ ] Preconditioners (precond_jacobi, precond_ilu0) — diagonal and ILU(0) +- [ ] Least squares solver (lstsq) — via QR or SVD with rank-deficient handling +- [ ] Arnoldi iteration (arnoldi) — falls out naturally from GMRES +- [ ] Matrix exponential (expm) — via Padé approximation + ## Run experiments ```bash diff --git a/include/qr.hpp b/include/qr.hpp index 4d6b4ec..c9e1638 100644 --- a/include/qr.hpp +++ b/include/qr.hpp @@ -5,12 +5,6 @@ namespace linalg { -// Thin QR factorization result. -// -// For an m x n matrix A with m >= n: -// Q is m x n with orthonormal columns (Q^T Q = I_n) -// R is n x n upper triangular -// A = Q * R struct QRResult { Matrix Q; Matrix R; -- cgit v1.2.3