A Fast Contour-Integral Eigensolver for Non-Hermitian Matrices

Xin Ye, Jianlin Xia, Raymond H. Chan, Stephen Cauley, Venkataramanan BalakrishnanSIAM J. Matrix Anal. Appl 2017 · DOI

TL;DR

This paper introduces a novel, accelerated algorithm for finding eigenvalues and eigenvectors of non-Hermitian matrices. By cleverly combining contour integration with rank-structured matrix approximations and efficient factorization updates, their method achieves near-optimal computational complexity, significantly outperforming existing techniques for large-scale problems.

What Problem Does This Paper Address?

Finding eigenvalues and eigenvectors is a fundamental problem in many scientific and engineering disciplines. While robust methods exist for Hermitian matrices, non-Hermitian matrices pose greater challenges due to their complex eigenvalues and eigenvectors. Traditional methods like QR iterations can be computationally expensive, especially for large matrices or when only a subset of eigenvalues is needed. Contour-integral methods offer robustness but can also suffer from high computational costs, particularly in the eigenvalue counting and linear system solving steps. This paper aims to bridge this gap by developing a fast and efficient contour-integral eigensolver that leverages advanced matrix approximation and factorization techniques to overcome these limitations.

Methods

The authors propose a two-stage approach:

  1. Quadsection Stage: This stage recursively partitions the search region for eigenvalues. It relies on low-accuracy HSS (Hierarchically Semi-Separable) matrix approximations to efficiently estimate the number of eigenvalues within each subregion. This is crucial because accurate eigenvalue counting can be computationally intensive. The key innovation here is demonstrating that low-accuracy approximations are sufficient for reliable counts, especially when contours are not too close to eigenvalues. They also utilize fast structured factorization updates to efficiently solve the linear systems required for these counts.
  2. Subspace Iteration Stage: Once subregions with a manageable number of eigenvalues are identified, a high-accuracy HSS approximation is used for the actual eigenvalue and eigenvector computation via a structured FEAST algorithm. This stage also benefits from the fast factorization updates and structured linear solvers.

A critical component throughout is the analysis of quadrature rules for approximating contour integrals. The paper analytically demonstrates that the Trapezoidal rule offers nearly optimal decay properties, making it superior to the commonly used Gauss-Legendre rule for this application.

Datasets

Not discussed in the paper. The paper focuses on algorithmic development and theoretical analysis, with numerical experiments conducted on constructed matrices.

Key Insights and Ideas

  • Low-accuracy approximations are sufficient for eigenvalue counting: This is a major breakthrough. The authors prove that for eigenvalue counting, using a slightly perturbed matrix (approximated by a low-accuracy HSS form) is often sufficient, as long as the contour is not too close to the eigenvalues. This dramatically reduces computational cost.
  • Trapezoidal rule excels for filter functions: Analytical evidence shows the Trapezoidal rule provides superior decay properties for filter functions in contour integration compared to Gauss-Legendre, leading to better accuracy and efficiency.
  • Rank-structured matrices are key enablers: The efficiency of the proposed method heavily relies on the properties of rank-structured matrices (specifically HSS matrices). These matrices allow for fast factorization and updates, which are essential for both the eigenvalue counting and the subspace iteration stages.
  • Optimal threshold for subregion size: The paper derives an optimal threshold for the number of eigenvalues per subregion (related to the HSS rank) to minimize overall computational complexity.

Key Results

  • The proposed FastEig algorithm achieves a computational complexity of O(rn²) + O(r²n) for finding all eigenpairs of a matrix with maximum off-diagonal rank r. This is a significant improvement over traditional methods.
  • Numerical experiments demonstrate substantial speedups. For Example 1 (Cauchy-like matrix), the algorithm is orders of magnitude faster than Intel MKL's ZGEEV for large problem sizes.
  • Example 2 (discretized matrix from Foldy-Lax formulation) shows that the combination of shifted factorization update and adaptive accuracy (low-accuracy for counting, high-accuracy for solving) provides the best performance, with significant time savings compared to methods without these accelerations.
  • The paper provides theoretical bounds and probabilistic arguments for the reliability of eigenvalue counts obtained using low-accuracy approximations.

Limitations and Future Work

  • Rank-structured matrices: The primary focus is on matrices that can be well-approximated by HSS forms. While the method can be applied to general matrices by first approximating them with HSS forms, the efficiency might be impacted if the approximation is poor or costly.
  • Clustered eigenvalues: The quadsection strategy might be less efficient if eigenvalues are highly clustered, leading to unbalanced quadtrees.
  • Future Work: The authors plan to extend their methods to more general matrix classes and matrices with clustered eigenvalues. They also aim to produce a scalable implementation for parallel computing. Further research into adapting the method for specific types of eigenvalues (e.g., real eigenvalues) is also mentioned.

Summary updated

BibTeX
@article{ye2017fast,
  author = {Xin Ye and Jianlin Xia and Raymond H. Chan and Stephen Cauley and Venkataramanan Balakrishnan},
  title = {{A Fast Contour-Integral Eigensolver for Non-Hermitian Matrices}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2017},
  doi = {10.1137/16m1086601},
}
Figure