From 606ad99e8363bd520506ea2e88b831911fe03c18 Mon Sep 17 00:00:00 2001 From: y-jan137 Date: Sun, 15 Mar 2026 14:08:51 +0300 Subject: Add QR iteration algos --- README.md | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'README.md') diff --git a/README.md b/README.md index 172f1a7..e3df582 100644 --- a/README.md +++ b/README.md @@ -1,8 +1,8 @@ # Numerical Linear Algebra This repo contains a small C++ dense numerical linear algebra library for `double`, with a companion experiments directory for evaluating performance. - -The current matmul uses a vectorized dot-product kernel. The implementation supports compile-time SIMD backends for `AVX`, `AVX2`, `AVX512`, and `NEON` on `AArch64`/`ARM64` with FP64 vector support. +I mostly follow Trefethen & Bau, "Numerical Linear Algebra" +The implementation supports compile-time SIMD backends for `AVX`, `AVX2`, `AVX512`, and `NEON` on `AArch64`/`ARM64` with FP64 vector support. ## Build @@ -31,17 +31,15 @@ ctest --test-dir build --output-on-failure - Triangular solvers (forward / backward substitution) - 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`) - -## Run examples - -```bash -./build/linear_system -./build/matmul -``` +- 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 ## Run experiments ```bash +./build/matmul ./build/pivoting_vs_no_pivoting ./build/hilbert_qr ``` -- cgit v1.2.3