The FEAST Algorithm

Developer Reference for Intel® oneAPI Math Kernel Library for C

Download PDF

ID 766684

Date 4/28/2026

Version

Public

The FEAST Algorithm

The Extended Eigensolver functionality is a set of high-performance numerical routines for solving symmetric standard eigenvalue problems, \(Ax = \lambda x\) , or generalized symmetric-definite eigenvalue problems, \(A x = \lambda Bx\) . It yields all the eigenvalues ( \(\lambda\) ) and eigenvectors ( \(x\) ) within a given search interval \([\lambda_{min}, \lambda_{max}]\) . It is based on the FEAST algorithm, an innovative fast and stable numerical algorithm presented in [Polizzi09] , which fundamentally differs from the traditional Krylov subspace iteration based techniques (Arnoldi and Lanczos algorithms [Bai00] ) or other Davidson-Jacobi techniques [Sleijpen96] . The FEAST algorithm is inspired by the density-matrix representation and contour integration techniques in quantum mechanics.

The FEAST numerical algorithm obtains eigenpair solutions using a numerically efficient contour integration technique. The main computational tasks in the FEAST algorithm consist of solving a few independent linear systems along the contour and solving a reduced eigenvalue problem. Consider a circle centered in the middle of the search interval \([\lambda_{min}, \lambda_{max}]\) . The numerical integration over the circle in the current version of FEAST is performed using \(N_{e}\) - point Gauss-Legendre quadrature with \(x_{e}\) the \(e\) -th Gauss node associated with the weight \(\omega_{e}\) . For example, for the case \(N_{e} = 8\) :

\(( x_1, \omega_1 ) = (0.183434642495649 , 0.362683783378361)\),
\(( x_2, \omega_2 ) = (-0.183434642495649 , 0.362683783378361)\),
\(( x_3, \omega_3 ) = (0.525532409916328 , 0.313706645877887)\),
\(( x_4, \omega_4 ) = (-0.525532409916328 , 0.313706645877887)\),
\(( x_5, \omega_5 ) = (0.796666477413626 , 0.222381034453374)\),
\(( x_6, \omega_6 ) = (-0.796666477413626 , 0.222381034453374)\),
\(( x_7, \omega_7 ) = (0.960289856497536 , 0.101228536290376)\), and
\(( x_8, \omega_8 ) = (-0.960289856497536 , 0.101228536290376)\).

The figure FEAST Pseudocode shows the basic pseudocode for the FEAST algorithm for the case of real symmetric (left pane) and complex Hermitian (right pane) generalized eigenvalue problems, using N for the size of the system and M for the number of eigenvalues in the search interval (see [Polizzi09] ).

NOTE:

The pseudocode presents a simplified version of the actual algorithm. Refer to http://arxiv.org/abs/1302.0432 for an in-depth presentation and mathematical proof of convergence of FEAST.

FEAST Pseudocode

`A` : real symmetric `B` : symmetric positive definite (SPD) ℜ { `x` }: real part of `x`	`A` : complex Hermitian `B` : Hermitian positive definite (HPD)

Select Your Language

Using Intel.com Search

Quick Links

Recent Searches

Advanced Search

Only search in

Developer Reference for Intel® oneAPI Math Kernel Library for C

The FEAST Algorithm

FEAST Pseudocode