Linear convergence of iterative contour integral-based eigensolvers for nonlinear eigenvalue problems

Technical Summary: Linear Convergence of Iterative Contour Integral-Based Eigensolvers for Nonlinear Eigenvalue Problems

Problem Statement
The paper addresses the challenge of solving nonlinear eigenvalue problems (NEPs) of the form $T(\lambda)u = 0$, where $T(\cdot)$ is a holomorphic matrix-valued function. While contour integral-based methods are attractive for reliably targeting all eigenvalues within a prescribed domain $D \subset \mathbb{C}$, traditional approaches like Beyn's method and the nonlinear Sakurai–Sugiura (SS) method lack an inherent iterative refinement mechanism. Consequently, achieving high accuracy in these methods requires increasing the number of quadrature nodes to reduce discretization error, which leads to prohibitive computational costs due to the need for repeated matrix factorizations. Although the NLFEAST algorithm combines contour integrals with a nonlinear Rayleigh–Ritz extraction step and behaves empirically as an iterative method, its theoretical convergence properties have remained insufficiently understood.

Methodology and Framework
The authors propose a general framework for iterative contour integral-based eigensolvers (Algorithm 1) that unifies existing methods and facilitates convergence analysis. The framework operates in two alternating steps per iteration:

1. Extraction: Given a subspace $X^{(k)}$, approximate eigenpairs $(\rho_i^{(k)}, x_i^{(k)})$ are extracted using a Rayleigh–Ritz procedure.
2. Filtering: A filter operator $F_{it}(\rho_i^{(k)})$ is applied to the approximate eigenvectors to generate a new subspace $X^{(k+1)}$. This filter is a discretized approximation of a continuous operator $F_{ci}(\rho)$, derived from the contour integral representation of the spectral projector.

The continuous operator $F_{ci}(\rho)$ is defined as:
$$F_{ci}(\rho) := \frac{1}{2\pi i} \oint_{\partial D} \frac{1}{\xi - \rho} \left( I - T(\xi)^{-1}T(\rho) \right) d\xi$$
Using Keldysh's theorem, the authors characterize the spectral properties of this operator, showing that it annihilates components outside the target eigenspace while preserving those within it.

Key Contributions and Theoretical Results
The primary contribution of the paper is the establishment of a rigorous convergence theory for this framework:

• Necessary Condition for Iterative Refinement: The authors demonstrate that for an iterative method to converge, the filter must map the approximate eigenvectors into the target invariant subspace $U_D$ as the approximation improves. They prove that standard discretizations, such as those used in Beyn's method, fail this condition because the discretized pencil $M_{1,N} - \xi M_{0,N}$ does not share the same invariant subspace as the exact NEP unless the quadrature is exact. This explains why Beyn's method cannot improve accuracy through iteration alone.
• Sufficient Condition for Linear Convergence (Theorem 6): Under mild assumptions (simple eigenvalues and linearly independent eigenvectors), the authors prove that if the filter family satisfies specific asymptotic error bounds (where the error in the "out-of-subspace" components is reduced by a factor $\gamma_N$), the algorithm exhibits local linear convergence. Specifically, the angle between the computed subspace and the exact eigenspace decreases linearly: $\angle(X^{(k+1)}, U_D) = O(\gamma_N \angle(X^{(k)}, U_D))$.
• Convergence of NLFEAST (Theorem 7 & Corollary 8): The paper applies this theory to the NLFEAST algorithm. By utilizing the specific filter structure defined in NLFEAST (a rational approximation of the indicator function combined with the residual inverse iteration concept), the authors prove that NLFEAST satisfies the necessary conditions for linear convergence. The convergence rate depends on the quadrature error $\gamma_N$, which decays exponentially with the number of quadrature nodes $N$.

Numerical Results
The theoretical findings are validated through extensive numerical experiments on nine challenging NEPs from the NLEVP collection and a specific photonic problem:

• Convergence Behavior: The experiments confirm that NLFEAST achieves linear convergence, with residuals decreasing steadily as iterations proceed, even with a limited number of quadrature nodes.
• Comparison with Beyn's Method: In direct comparisons, NLFEAST significantly outperforms Beyn's method in terms of computational time required to reach high accuracy. While Beyn's method requires increasing $N$ (and thus re-factorizing matrices) to improve accuracy, NLFEAST reuses the LU factorizations of the matrices $T(\xi_j)$ computed in the first iteration, relying on cheaper triangular solves in subsequent steps.
• Robustness: The method is shown to be robust even in special cases where eigenvectors corresponding to different eigenvalues are linearly dependent (e.g., sharing the same left or right eigenvectors), provided a reliable solver is used for the compressed NEP.

Significance and Claims
The paper claims to provide the first theoretical justification for the linear convergence of NLFEAST, clarifying why it functions effectively as an iterative method while other contour integral-based approaches (like Beyn's method) do not. The authors emphasize that their analysis explains the "failure" of certain methods to converge via iteration: they lack a fixed point in the subspace manifold due to quadrature errors that cannot be mitigated by iteration.

The significance lies in demonstrating that high accuracy in NEPs can be achieved without the prohibitive cost of increasing quadrature nodes indefinitely. Instead, a moderate number of nodes combined with iterative refinement (as in NLFEAST) is sufficient. The authors conclude that this framework opens a path for designing novel iterative nonlinear eigensolvers with improved properties, though they modestly note that constructing filters that satisfy the convergence conditions remains challenging and that, currently, NLFEAST is the primary known instance fitting this framework.