Developer Reference

  • 0.10
  • 10/21/2020
  • Public Content
Contents

The FEAST Algorithm

The Extended Eigensolver functionality is a set of high-performance numerical routines for solving symmetric standard eigenvalue problems,
A
x
=
λ
x
, or generalized symmetric-definite eigenvalue problems,
A
x
=
λ
B
x
. 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
    1
    ,
    ω
    1
    ) = (0.183434642495649 , 0.362683783378361),

    (
    x
    2
    ,
    ω
    2
    ) = (-0.183434642495649 , 0.362683783378361),

    (
    x
    3
    ,
    ω
    3
    ) = (0.525532409916328 , 0.313706645877887),

    (
    x
    4
    ,
    ω
    4
    ) = (-0.525532409916328 , 0.313706645877887),

    (
    x
    5
    ,
    ω
    5
    ) = (0.796666477413626 , 0.222381034453374),

    (
    x
    6
    ,
    ω
    6
    ) = (-0.796666477413626 , 0.222381034453374),

    (
    x
    7
    ,
    ω
    7
    ) = (0.960289856497536 , 0.101228536290376), and

    (
    x
    8
    ,
    ω
    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]).
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)

Product and Performance Information

1

Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804