Cache-Friendly, Low-Memory Lanczos Algorithm in Rust
11 days ago
- #memory optimization
- #Lanczos algorithm
- #matrix functions
- The standard Lanczos method for computing matrix functions has a high memory requirement, storing a basis matrix that grows with each iteration.
- A two-pass variant of the Lanczos algorithm reduces memory usage to O(n) by doubling the number of matrix-vector products, trading computation for memory efficiency.
- The two-pass method can be faster than the standard method for certain problems due to better cache behavior, despite performing more matrix-vector products.
- The Lanczos algorithm simplifies when the matrix is Hermitian, using a three-term recurrence to build an orthonormal basis without full orthogonalization.
- The two-pass approach involves a first pass to compute coefficients and a second pass to reconstruct the solution, avoiding storage of the full basis matrix.
- Implementation in Rust leverages efficient memory management and cache optimization, making the two-pass method competitive in runtime.
- Benchmarking shows the two-pass method's memory usage remains flat with increasing iterations, while the standard method's memory grows linearly.
- For dense matrices, the two-pass method's runtime is exactly twice as slow as the standard method, confirming the theoretical trade-off in compute-bound scenarios.
- The two-pass method's performance advantage diminishes for very large problems where matrix-vector product costs dominate.
- The code is open-source and available on GitHub, providing a practical exploration of memory-computation trade-offs in algorithm engineering.