Zolotarev Quadrature Rules and Load Balancing for the FEAST Eigensolver

Stefan Güttel, Eric Polizzi, Ping Tak Peter Tang, Gautier Viaud

Abstract

The FEAST eigensolver is a robust algorithm for finding all eigenvalues of a large matrix within a specified interval. However, its performance often depends on the distribution of eigenvalues near the interval boundaries, leading to slow convergence and significant load imbalances in parallel computing environments. This paper presents an optimized approach by replacing traditional quadrature-based filters with Zolotarev rational approximants. By reframing the filter construction as a rational approximation problem, the authors demonstrate that Zolotarev rules provide faster, more predictable convergence and solve critical load-balancing bottlenecks in large-scale electronic structure calculations.

Introduction

The FEAST algorithm has become a cornerstone in computational physics and chemistry for solving interior eigenvalue problems. At its core, FEAST applies a "rational filter" to a search space. Mathematically, this filter is a function designed to be 1 inside a target interval and 0 outside. Traditionally, this filter is constructed using standard numerical integration techniques, such as Gauss or Trapezoid quadrature rules.

While effective in many scenarios, these standard rules possess a significant weakness: their decay rate is often insufficient when "unwanted" eigenvalues reside close to the search interval's edges. This lack of steepness at the boundaries leads to slow convergence. In parallel computing, where the spectrum is partitioned into multiple intervals, this variability causes a "load imbalance" problem. Some processors may finish their assigned intervals in a few iterations, while others remain occupied for dozens, leaving expensive computational resources idling.

The Rational Approximation Framework

The authors propose a shift in perspective, viewing the FEAST filter not as a byproduct of quadrature, but as a direct rational approximation problem. They utilize Zolotarev rational functions, which are mathematically proven to be the "best uniform rational approximants" to the signum function. These functions are particularly well-suited for creating step-like filters.

Key to this approach is the use of Moebius Transformations to map Zolotarev's optimal functions from their native domain to the specific search interval $[G, G]$ required by the user. Unlike standard quadrature rules that decay smoothly, Zolotarev filters exhibit equioscillation—they ripple between fixed bounds. This property allows for a much steeper "slope" at the interval boundaries, effectively "cleaning" the search space of unwanted noise more efficiently than traditional methods.

Comparison of rational filter functions and their pole distributions for different parameters.

As shown in the figure above, the distribution of poles in the complex plane (top row) directly influences the filter's behavior (bottom row). As the parameter $S$ (related to the gap between wanted and unwanted eigenvalues) decreases, the poles move closer to the real axis, resulting in a sharper transition at the boundary ($z=1$). This mathematical predictability allows researchers to guarantee a "worst-case" performance, regardless of the specific eigenvalue distribution.

Experimental Results and Load Balancing

The effectiveness of the Zolotarev approach was evaluated using matrices from real-world electronic structure calculations, including a 2D Carbon Nanotube (cnt) and a 3D caffeine molecule (Caffeinep2). These large, sparse generalized eigenproblems are typical of the challenges faced in the field.

Convergence and Robustness

In the cnt matrix test ($N = 12,450$), the Zolotarev-based FEAST converged robustly even with a small search space where Gauss and Trapezoid rules struggled. The method proved remarkably insensitive to the "gap" problem—the distance between the last wanted eigenvalue and the first unwanted one. While standard FEAST performance degrades as this gap shrinks, Zolotarev's convergence rate remains nearly independent of the gap size.

Parallel Efficiency

The most striking results appeared in parallel tests using the Caffeinep2 matrix ($N = 176,622$). When splitting the spectrum across two intervals:

  • Gauss Rule: One interval required 39 iterations while the other took only 5, leading to massive idle time for the faster processor.
  • Zolotarev Rule: The intervals converged in 8 and 9 iterations, respectively.

This near-perfect synchronization represents a massive improvement in parallel efficiency, as the total time to solution is dictated by the slowest task.

Conclusion

By adopting Zolotarev rational functions, the FEAST eigensolver gains a level of mathematical optimality and predictability previously unavailable with standard quadrature rules. The steeper filter slopes and equioscillation properties ensure that convergence is both fast and uniform across different spectral regions. While the proximity of poles to the real line requires careful numerical handling, the benefits for load balancing in high-performance computing are substantial. These rules are a significant step forward for the FEAST software suite, providing a more reliable tool for the scientific community.

Summary updated

BibTeX
@article{guttel2015zolotarev,
  author = {Stefan Güttel and Eric Polizzi and Ping Tak Peter Tang and Gautier Viaud},
  title = {{Zolotarev Quadrature Rules and Load Balancing for the FEAST Eigensolver}},
  journal = {SIAM J. Sci. Comput.},
  year = {2015},
  doi = {10.1137/140980090},
}
Figure