🔢 mathematics

Lanczos with compression for symmetric eigenvalue problems

This paper proposes a novel "Lanczos with compression" strategy for symmetric eigenvalue problems that utilizes rational approximation to compress the Krylov subspace, offering theoretical convergence guarantees and practical performance advantages over traditional implicit restarting methods like Krylov--Schur while relying solely on matrix-vector products.

Original authors: Angelo A. Casulli, Daniel Kressner, Nian Shao

Published 2026-02-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Angelo A. Casulli, Daniel Kressner, Nian Shao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the deepest valleys (the smallest eigenvalues) in a massive, foggy mountain range (a giant matrix). You have a hiker (the Lanczos method) who can only take steps by looking at the ground directly in front of them.

To find the deepest valleys, the hiker needs to explore a huge area. But there's a problem: the hiker has a limited backpack. If they keep walking and remembering every single step they've ever taken, their backpack will get too heavy, and they'll run out of memory before they find the bottom.

The Old Way: "The Reset Button"

For decades, the standard solution was Implicit Restarting (like the Krylov–Schur method).

Think of this as the hiker walking for a while, getting tired, and then hitting a "Reset Button."

The hiker looks at the path they've walked.
They use a magic filter (a polynomial) to say, "I don't care about these hills; I only care about the valleys."
They wipe their memory clean, keeping only the most promising direction, and start walking again from scratch with a fresh, smaller backpack.

This works, but it's a bit clunky. Every time you hit "Reset," you lose some momentum, and the process of filtering out the "wrong" hills isn't always perfectly efficient.

The New Way: "The Compression Suit"

This paper introduces a new strategy called Lanczos with Compression. Instead of hitting a reset button, the hiker wears a magic compression suit.

Here is how it works, using our mountain analogy:

1. The Problem with the Backpack
As the hiker walks, they collect "breadcrumbs" (vectors) to remember the path. If they walk too far, the breadcrumbs pile up.

Old method: Stop, throw away 50% of the breadcrumbs, keep the best 50%, and start over.
New method: Keep walking, but every few steps, put all the breadcrumbs into a magic vacuum bag.

2. The Magic Vacuum Bag (Rational Approximation)
This is the core innovation. The hiker doesn't just throw away the "bad" breadcrumbs. Instead, they use a special mathematical tool (called rational approximation) to squeeze the entire path into a tiny, compact bag.

Imagine you have a long, winding road map.
The "polynomial filter" (old way) tries to cut out the parts of the map that aren't valleys.
The "rational compression" (new way) realizes that the map has a pattern. It folds the map so tightly that the shape of the valleys is preserved perfectly, but the paper takes up 90% less space.

3. Why This is Better
The paper proves two main things:

It doesn't lose the map: Even though the bag is tiny, the hiker can still find the exact same valleys as if they had the full, heavy map. The "error" introduced by squeezing the map is so small it's practically invisible.
It's faster: Because the bag is smaller, the hiker spends less time organizing their backpack (a process called orthogonalization). In the old method, organizing a huge backpack gets exponentially harder as you walk further. With the compression suit, the backpack stays small, so the hiker can run much faster.

The "Ghost" Problem and the "Fill-In" Fix

There was a catch. When you squeeze a map, sometimes the lines get a little blurry, and you might accidentally create "ghost valleys" (fake solutions) that don't exist.

The authors realized that simply squeezing the map wasn't enough. They had to add a special "Fill-In" technique.

Imagine that when you fold the map, you add a little extra glue (fill-in) to the creases to make sure the lines stay sharp and don't smudge.
This ensures that even after the map is compressed, the hiker is still walking on solid ground and not getting tricked by ghosts.

The Results: A Race to the Bottom

The authors tested this new "Compression Suit" against the old "Reset Button" method on real-world problems (like simulating electricity in materials or fluid dynamics).

The Race: They measured how many steps (matrix-vector multiplications) it took to find the answer.
The Winner: The Compression Suit won. It found the valleys 4% to 30% faster than the old method, depending on the difficulty of the mountain.
The Big Picture: For the biggest, most complex mountains (huge scientific simulations), this method saves a massive amount of computer time and memory.

Summary

The Goal: Find specific numbers (eigenvalues) in giant data sets without running out of memory.
The Old Way: Walk a bit, throw away the trash, and start over. (Effective, but slow).
The New Way: Walk continuously, but use a "magic vacuum" to shrink your memory usage while keeping all the important information.
The Result: You get to the bottom of the valley faster, with less effort, and without losing your way.

This paper is essentially teaching computers how to carry a lighter backpack so they can solve the world's hardest math problems faster.

1. Problem Statement

The paper addresses the challenge of computing a few extreme eigenvalues (smallest or largest) and their corresponding eigenvectors for large-scale symmetric matrices ( $A \in \mathbb{R}^{n \times n}$ ).

The Bottleneck: Standard Krylov subspace methods (like the Lanczos algorithm) require storing the entire basis of the Krylov subspace to maintain orthogonality and avoid "ghost eigenvalues." As the subspace dimension grows, memory usage and the cost of orthogonalization (which scales quadratically with the subspace size) become prohibitive.
Current Solutions: The industry standard is Implicit Restarting (e.g., the Krylov–Schur method or IRL). These methods periodically truncate the subspace using polynomial filtering to retain only the most relevant spectral information. However, theoretical convergence guarantees for these restarted methods are often qualitative, and they can be computationally expensive in terms of matrix-vector products (matvecs).

2. Methodology: Lanczos with Compression (LC)

The authors propose a novel strategy called Lanczos with Compression, which replaces polynomial filtering with rational approximation to compress the Krylov subspace.

Core Concepts

Krylov-like Decomposition: Unlike standard restarting, which preserves the tridiagonal Krylov structure, compression sacrifices the strict Krylov structure. The authors introduce a generalized decomposition:
$A Q_m = Q_m T_m + q_{i+1} b_m^T + F_m$
where $F_m$ is an "error" term. Crucially, the paper proves that compressing the basis $Q_m$ via an orthonormal matrix $V_\ell$ preserves this generalized structure, allowing the Lanczos process to continue.
Rational Approximation: Instead of using a polynomial to filter the spectrum, the method uses a rational function $r(x)$ $r (x)$ to approximate the step function $\chi_\tau(x)$ $χ_{τ} (x)$ (which is 1 for eigenvalues below a threshold $\tau$ $τ$ and 0 otherwise).
- The compression matrix $V_\ell$ is constructed to span a subspace containing the eigenvectors of interest.
- This subspace is the sum of the first $k$ eigenvectors of the current tridiagonal matrix and a Rational Krylov Subspace generated by the poles of the rational function.
Adaptive Pole Selection: The algorithm adaptively selects the degree of the rational function and the location of its poles based on the current Ritz values. It aims to minimize the dimension of the compressed subspace while keeping the approximation error below a tolerance ( $tol_{ra}$ ).
Reorthogonalization with Fill-in: A critical contribution is handling numerical stability. Standard reorthogonalization destroys the structure of the $F_m$ term. The authors propose a "Reorthogonalization with Fill-in" strategy. This technique implicitly updates the $F_m$ term without explicitly storing it, ensuring backward stability and preventing the loss of orthogonality that leads to ghost eigenvalues.

Algorithm Flow

Expansion: Perform standard Lanczos steps to expand the basis up to a maximum dimension $m$ .
Compression:
- Compute the rational approximation parameters based on the current spectrum.
- Construct the orthonormal compression matrix $V_\ell$ .
- Project the current basis and matrix $T_m$ onto the smaller subspace of dimension $\ell < m$ .
- Update the decomposition to include the "fill-in" terms required for stability.
Iteration: Continue the Lanczos process from the compressed basis until convergence.

3. Key Contributions

Novel Compression Strategy: The introduction of rational Krylov compression as an alternative to polynomial filtering for restarting. This allows for more flexible and potentially more efficient spectral filtering.
Theoretical Error Bounds:
- Convergence: The authors prove that the error introduced by compression is bounded by $O(tol_{ra}^2)$ . This implies that the convergence rate of the compressed method is nearly identical to the standard (unrestarted) Lanczos method, provided the rational approximation tolerance is sufficiently small.
- Backward Stability: They establish a backward stability result similar to the Krylov–Schur method, proving that the computed Ritz values correspond to the exact eigenvalues of a slightly perturbed matrix $A + E$ .
Complexity Analysis: The paper provides a complexity analysis showing that for problems with small relative eigenvalue gaps, the cost of orthogonalization is reduced. While standard restarting requires orthogonalizing against a large fixed restart length, LC orthogonalizes against a compressed basis whose size grows only logarithmically with the inverse of the gap.
Practical Implementation: The development of a robust algorithm (Algorithm 2) that integrates adaptive pole selection, rational approximation, and the specialized reorthogonalization scheme.

4. Numerical Results

The authors compared their method (LC) against the standard Krylov–Schur method (KS) using Matlab implementations.

Laplacian Eigenvalue Problems:
- On discretized 2D Laplacian matrices (L-shaped domain), LC consistently outperformed KS.
- Improvement: LC required 4% to 7% fewer matrix-vector multiplications than KS to achieve the same accuracy.
- Scalability: The performance advantage of LC increased as the matrix size ( $n$ ) grew.
- Robustness: The improvement was consistent across 100 trials with different random initial vectors.
Density Functional Theory (DFT) Matrices:
- Tested on indefinite matrices from DFT applications (e.g., $H_2O$ , $SiO_2$ ).
- LC generally outperformed KS, particularly for matrices with larger numbers of desired eigenvalues.
- Stagnation Issue: The authors observed that for very large numbers of eigenvalues (e.g., 55 or 86), LC sometimes stagnated due to round-off errors affecting the rank-one structure of the off-diagonal blocks. However, they demonstrated that their "fill-in" reorthogonalization scheme was essential to maintain backward stability, whereas standard reorthogonalization failed immediately after the first compression.

5. Significance and Conclusion

Efficiency: The method offers a tangible reduction in computational cost (matvecs) for large-scale symmetric eigenvalue problems, which is the primary bottleneck in these applications.
Theoretical Rigor: Unlike many heuristic restarting strategies, this work provides rigorous convergence guarantees showing that compression introduces negligible error compared to the standard Lanczos method.
Stability: The proposed "fill-in" reorthogonalization is a significant technical advancement that ensures the method remains numerically stable, addressing a known weakness of subspace compression techniques.
Future Work: The authors note that while the method is robust, handling the stagnation observed in high-dimensional indefinite problems (likely due to accumulated round-off errors in the fill-in terms) remains an open challenge for future research.

In summary, Lanczos with Compression presents a mathematically sound and practically superior alternative to implicit restarting for symmetric eigenvalue problems, leveraging rational approximation to reduce memory and computational costs while maintaining high accuracy and stability.