🔢 mathematics

Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent

This paper analyzes the convergence of a nonlinear eigensolver based on rational approximation of the sketched resolvent, demonstrating how block probing and zooming techniques improve accuracy while establishing the stability of polefinding via a barycentric rational form.

Original authors: Nian Shao, Yuji Nakatsukasa

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nian Shao, Yuji Nakatsukasa

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 hidden "sweet spots" (eigenvalues) inside a giant, complex machine called a matrix. These sweet spots are special numbers where the machine behaves in a very specific way. Usually, finding them is like trying to hear a whisper in a hurricane.

For a long time, mathematicians have tried to find these spots by taking a "snapshot" of the machine's behavior (called the resolvent) and then guessing a simple formula (a rational approximation) that fits the snapshot. The idea is that the places where this simple formula breaks down (its poles) should be exactly where the hidden sweet spots are.

The Problem: The "Good Enough" Trap
The paper starts by showing that while this "guess the formula" method works, it's often frustratingly imprecise. The authors ran a test with a simple machine containing 9 distinct sweet spots. Even though their formula was incredibly accurate at the points they sampled (off by only about 0.00000000000001), the calculated locations of the sweet spots were still off. Some were wrong in the 12th decimal place, others in the 10th. It was like having a map that was perfect for the cities you visited, but when you tried to find the towns in between, you were still miles off.

The paper explicitly argues against the idea that you can just throw more random samples at the problem or use a single "probe" (a simple vector) to fix this. They show that even with perfect sampling, a naive approach fails to get high accuracy, especially for tricky spots inside the machine or when multiple spots are crowded together.

The Solution: Two Magic Tricks
To fix this, the authors propose two specific techniques that act like a super-powered magnifying glass and a multi-lens camera.

The Multi-Lens Camera (Block Probing):
Instead of looking at the machine with a single flashlight (a single vector), they suggest using a whole array of flashlights at once (a block of vectors, or a matrix).
- Why it works: Imagine trying to find a hidden object in a dark room. If you use one flashlight, you might miss it if it's behind a pillar. But if you use a wide beam or a grid of lights, you catch every angle. The paper proves mathematically that using this "block" approach ensures you don't accidentally miss any of the hidden spots, even if they are crowded or have complex structures. It also helps the computer figure out if a spot is actually a group of identical spots hiding together.
The Super-Magnifying Glass (Zooming In):
The second trick is to stop trying to find all the spots in the whole room at once. Instead, the algorithm divides the room into tiny, smaller rooms. It then zooms in on one small room, finds the spots there, and repeats the process.
- Why it works: The paper demonstrates that the accuracy of the guess gets better linearly as the size of the room gets smaller. If you shrink the search area by a factor of 10, your guess becomes 10 times more accurate. By recursively chopping the domain into smaller and smaller pieces, the method can pinpoint the locations with incredible precision.

The Result: From "Meh" to "Wow"
When the authors combined these two tricks, the results were dramatic. In their test with the 9 sweet spots, the naive method was off by digits in the 10th or 12th decimal place. But with the "Multi-Lens Camera" and "Super-Magnifying Glass," the new method found the spots with at least 15 digits of accuracy. The numbers went from 0.1000000000000026 to 0.1000000000000000.

How Sure Are They?
The authors didn't just guess that this would work; they proved it.

They provided rigorous mathematical proofs showing that using a block of probes recovers all the necessary information about the machine's structure.
They proved that as you shrink the search area (zoom in), the error shrinks linearly.
They showed that finding the roots of the formula is stable, provided the sampling points are well-spaced.
They backed up these proofs with computer simulations (numerical experiments) that matched their theoretical predictions perfectly.

What They Didn't Do
The paper is very careful to say what it doesn't do. It doesn't claim to have built the fastest possible software implementation. In fact, they admit that cleaning up "fake" spots (called Froissart doublets) that sometimes appear in the math is still a challenge that needs more work. They also didn't claim this works for every single type of machine in existence, but rather for a broad, standard class of problems known as nonlinear eigenvalue problems.

In short, the paper takes a method that was "okay but messy" and, by using a smarter way to look at the data and a strategy of breaking the problem into tiny pieces, turns it into a highly accurate tool for finding hidden mathematical treasures.

Technical Summary: Convergence Analysis of a Nonlinear Eigensolver Based on Rational Approximation of the Resolvent

Problem Statement
The paper addresses the challenge of solving Nonlinear Eigenvalue Problems (NEPs) of the form $T(\lambda)v = 0$ , where $T$ is a holomorphic matrix-valued function. The authors focus on a specific class of eigensolvers that compute eigenvalues by identifying the poles of a rational approximation to the resolvent $T^{-1}$ . While this approach, utilizing the Adaptive Antoulas-Anderson (AAA) algorithm for rational approximation, offers a flexible framework, it suffers from two primary limitations:

Accuracy Degradation: Even with high-precision rational approximations at sample points, the computed poles (eigenvalues) often lack high accuracy, particularly for interior eigenvalues or those with high multiplicity.
Multiplicity Detection: Standard approaches using scalar probing vectors fail to detect the multiplicity of eigenvalues, as the resulting scalar resolvent exhibits only simple poles regardless of the underlying algebraic multiplicity.

Methodology
The proposed approach constructs a "surrogate function" $F(z)$ by sketching the resolvent with random probing matrices $\Omega_L$ and $\Omega_R$ :
$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$
The algorithm proceeds in three main stages:

Block Probing: Instead of using scalar vectors, the method employs $n \times b$ probing matrices. This modification is designed to preserve spectral information regarding eigenvalue multiplicities and improve numerical robustness.
Rational Approximation: The (set-valued) AAA algorithm is applied to $F(z)$ to generate a barycentric rational approximation $R(z)$ .
Zooming In: To handle domains containing many eigenvalues, the algorithm recursively subdivides the computational domain $D$ into smaller subdomains. The polefinding procedure is applied to these smaller regions to reduce the number of poles per approximation, thereby enhancing accuracy.

The final step involves finding the poles of the rational approximation $R(z)$ by solving a generalized eigenvalue problem derived from its barycentric form.

Key Contributions and Theoretical Results
The paper provides a rigorous convergence analysis addressing three fundamental questions regarding the stability and accuracy of this method:

Spectral Recovery via Block Probing (Section 2):
- The authors establish that if the block size $b$ is at least the geometric multiplicity of an eigenvalue, the surrogate function $F(z)$ retains all essential spectral information.
- Theorem 2.3 demonstrates that the singular values of $F(z)$ near an eigenvalue $\lambda_i$ blow up at rates determined by the partial algebraic multiplicities, allowing for the recovery of multiplicity information.
- Theorem 2.7 proves that block probing significantly reduces the probability of "missing" an eigenvalue due to the sketching process (i.e., the sketched coefficient matrices becoming zero), offering a stronger anti-concentration bound than vector-based probing.
Convergence of Poles and the Effect of Zooming (Section 3):
- Theorem 3.2 quantifies the convergence of poles, showing that the accuracy of a computed pole with multiplicity $m$ is limited to $O(u^{1/m})$ (where $u$ is machine precision) if the domain is large. This explains the poor accuracy observed in naive approaches for high-multiplicity eigenvalues.
- The paper analyzes the "zooming in" technique, demonstrating that reducing the domain diameter $\delta$ linearly improves the accuracy of the computed eigenvalues, effectively mitigating the $O(u^{1/m})$ limitation.
- Theorem 3.4 provides a convergence result for domains with multiple poles, showing that the accuracy depends heavily on the number of poles within the domain. This theoretically justifies why partitioning the domain (reducing the number of poles per subdomain) leads to substantial accuracy improvements, especially when combined with block probing.
Stability of Polefinding (Section 4):
- The authors analyze the backward and forward stability of finding the roots of the rational approximation via a generalized eigenproblem.
- Theorem 4.3 establishes backward stability under the condition that the computed pole is not too close to multiple support points simultaneously.
- Theorem 4.4 characterizes the forward stability, confirming that the best achievable forward error is $O(u^{1/m})$ for an eigenvalue of multiplicity $m$ , consistent with classical dense eigensolvers.

Results
Numerical experiments validate the theoretical findings:

Toy Example: For a diagonal matrix with distinct eigenvalues, the naive approach (scalar probing, single domain) yields errors around $10^{-14}$ to $10^{-13}$ , with incorrect digits in the least significant places.
Improved Approach: Applying block probing (size 2) and zooming in (subdividing the domain) recovers eigenvalues with at least 15 digits of accuracy.
Butterfly Problem: In a complex NEP with 61 eigenvalues in a specific domain, the combination of block probing and domain subdivision significantly reduces the maximum error compared to using a single large domain, confirming that separating pole clusters improves accuracy.

Significance
The paper claims to provide the first theoretical analysis explaining the accuracy improvements offered by block probing and zooming in for resolvent-based eigensolvers. It clarifies that:

Block probing is necessary not just for detecting multiplicities but also for robustly recovering spectral modes that might otherwise be lost to sketching.
The "zooming in" technique is theoretically justified as a method to linearly improve accuracy by reducing the density of poles in the approximation domain, directly addressing the convergence limitations identified in Theorem 3.2.
The method is backward and forward stable provided the sampling points are well-distributed and the generalized eigenproblem is solved stably.

The authors note that while the theoretical analysis is complete, the implementation of a robust cleanup procedure for spurious poles (Froissart doublets) remains an open challenge for future work.

Technical Summary: Convergence Analysis of a Nonlinear Eigensolver Based on Rational Approximation of the Resolvent

More like this