diff options
| author | y-jan137 <yousefjan24000@gmail.com> | 2026-03-20 18:07:59 +0300 |
|---|---|---|
| committer | y-jan137 <yousefjan24000@gmail.com> | 2026-03-20 18:07:59 +0300 |
| commit | b8bc28c70a6f2b0e7de81e85a796303d514df008 (patch) | |
| tree | 22597d60b4951af27151a98992b4f8b8a7db6b66 | |
| parent | b27583941c200f98ab328901e81c9188945bf708 (diff) | |
Update TODO
| -rw-r--r-- | README.md | 19 | ||||
| -rw-r--r-- | include/qr.hpp | 6 |
2 files changed, 18 insertions, 7 deletions
@@ -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; |