Density-matrix-based algorithm for solving eigenvalue problems

A fast and stable numerical algorithm for solving the symmetric eigenvalue problem is presented. The technique deviates fundamentally from the traditional Krylov subspace iteration based techniques (Arnoldi and Lanczos algorithms) or other Davidson-Jacobi techniques and takes its inspiration from the contour integration and density-matrix representation in quantum mechanics. It will be shown that this algorithm—named FEAST—exhibits high efficiency, robustness, accuracy, and scalability on parallel architectures. Examples from electronic structure calculations of carbon nanotubes are presented, and numerical performances and capabilities are discussed.

Figure 1

Schematic representation of the complex contour integral defined by the positive half circle ${\mathcal{C}}^{+}$. In practice, the vectors $\mathbf{Q}$ are computed via a numerical integration (e.g., Gauss-Legendre quadrature) where only few linear systems $\mathbf{G}\left(Z\right)\mathbf{Y}$ needs to be solved at specific points $Z_e$ along the contour.

Figure 2

FEAST pseudocode (sequential version) for solving the generalized eigenvalue problem $\mathbf{A}\mathbf{x}=\lambda \mathbf{B}\mathbf{x}$, where $\mathbf{A}$ is real symmetric and $\mathbf{B}$ is spd, and obtaining all the $M$ eigenpairs within a given interval $\left[{\lambda }_{\text{min}},{\lambda }_{\text{max}}\right]$. The numerical integration is performed using $N_e$-point Gauss-Legendre quadrature with $x_e$ the $e\text{th}$ Gauss node associated with the weight ${\omega }_e$. For the case $N_e=8$, one can use $\left(x_1,{\omega }_1\right)=\left(0.183434642495649,0.362683783378361\right)$, $\left(x_3,{\omega }_3\right)=\left(0.525532409916328,0.313706645877887\right)$, $\left(x_5,{\omega }_5\right)=\left(0.796666477413626,0.222381034453374\right)$, $\left(x_7,{\omega }_7\right)=\left(0.960289856497536,0.101228536290376\right)$, and ${\left(x_{2i},{\omega }_{2i}\right)}_{i=1,\dots ,4}=\left(-x_{2i-1},{\omega }_{2i-1}\right)$.

Figure 3

Band-structure calculations of a (5,5) metallic CNT. The eigenvalue problems are solved successively for all the $\mathbf{k}$ points (from $\mathbf{\Gamma }$ to $\mathbf{X}$), while the computed subspace of size $M_0=25$ at the point $\mathbf{k}$ is used as initial guess for the point $\mathbf{k}+1$. The number of eigenvalues found ranges from 13 to 20 and by the third $\mathbf{k}$ point, the FEAST convergence is obtained using only one refinement loop. The convergence is obtained with the relative error on trace of the eigenvalues smaller or equal to ${10}^{-8}$, while the inner linear systems are solved using an iterative method with an accuracy of ${10}^{-3}$. The final relative residuals on the eigenpairs range from ${10}^{-3}$ to ${10}^{-5}$.