The FEAST Algorithm

Developer Reference for Intel® oneAPI Math Kernel Library for C

Download PDF

ID 766684

Date 10/31/2024

Version

Public

Visible to Intel only — GUID: GUID-71167B41-F386-46BC-91EB-7E2AE18B8843

View Details

The FEAST Algorithm

The Extended Eigensolver functionality is a set of high-performance numerical routines for solving symmetric standard eigenvalue problems, Ax=λx, or generalized symmetric-definite eigenvalue problems, Ax=λBx. It yields all the eigenvalues (λ) and eigenvectors (x) within a given search interval [λ_min , λ_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 [λ_min , λ_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 ω_e. For example, for the case N_e = 8:

( x₁, ω₁ ) = (0.183434642495649 , 0.362683783378361),
( x₂, ω₂ ) = (-0.183434642495649 , 0.362683783378361),
( x₃, ω₃ ) = (0.525532409916328 , 0.313706645877887),
( x₄, ω₄ ) = (-0.525532409916328 , 0.313706645877887),
( x₅, ω₅ ) = (0.796666477413626 , 0.222381034453374),
( x₆, ω₆ ) = (-0.796666477413626 , 0.222381034453374),
( x₇, ω₇ ) = (0.960289856497536 , 0.101228536290376), and
( x₈, ω₈ ) = (-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)

Parent topic: Extended Eigensolver Routines

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