Eigenvalue Calculations

Tools for Solution of Algebraic Systems
Eigenvalue Calculations


Developing scalable eigenvalue algorithms and solvers for problems with millions to billions of degrees of freedom.

The goal of eigensystems research in FASTMath is to develop scalable and robust solvers for tackling large-scale linear and nonlinear eigenvalue problems. The work on eigensystems has been motivated primarily by SciDAC science partnerships, and consequently it leverages support from a number of SAPs in which FASTMath members are engaged.

Linear symmetric (Hermitian) eigensystems arise in many applications. For example, in atomic and nuclear physics, the many-body Schrödinger equations is a Hermitian linear eigenvalue problem. Using the so-call configuration interaction approach, one can obtain approximate solutions to this problem by computing a few eigenpairs of a very large but sparse Hamiltonian matrix. Several algorithms such as the Lanczos method, Davidson method, and locally optimal block preconditioned conjugate gradient (LOBPCG) method can be used to solve this type of problem. To make the computation efficient, we develop techniques to accelerate the convergence of these methods (e.g., by constructing good initial guesses and effective preconditioners). We use a variety of techniques to improve the parallel scalability of the eigenvalue calculation (e.g. through efficient data distribution, overlapping computation with communication). This type of eigenvalue problem can also be formulated as a tensor eigenvalue problem in which both the matrix operator and the eigenvector can be decomposed in tensor train format. Low-rank approximation is the key to reduce the complexity of the computation. We plan to develop efficient algorithms for solving this type of problem.

Non-Hermitian eigenvalue problems often arise in linear response (perturbation) calculations. In some cases, a non-Hermitian eigenvalue problem can be transformed into a Hermitian eigenvalue problem through a special transformation. In other cases, they must be treated as general non-Hermitian eigenvalue problems. We develop techniques to compute eigenvalues deep inside the spectrum on a complex plane and algorithms that can preserve certain special structures of the solution (e.g. positive and negative pairing of the eigenvalues).

In many spectroscopy studies, scientists are often interested in the general profile of the absorption spectrum of materials or chemical systems. The spectrum profile can be used as a screening tool to identify materials or chemical systems of interest. We develop methods to approximate the spectrum directly without explicitly computing eigenvalues and eigenvectors.

Nonlinear eigenvalue problems arise in Kohn-Sham density functional theory-based electronic structure calculations. The nonlinear eigenvalue problem is often solved by a self-consistent field (SCF) iteration in which a sequence of linear eigenvalue problems need to be solved. The number of eigenpairs to be computed is proportional to the number of electrons. For large complex systems, it can reach thousands or even tens of thousands. We develop efficient algorithms to compute many eigenpairs through spectrum slicing and other techniques. These techniques aim at reducing the cost of the Rayleigh-Ritz procedure, which is used to compute eigenpairs of a projected problem that can become very large for complex systems.

We work closely with computational scientists to integrate the latest development in eigensystem solvers with application software packages directly. 

Recent accomplishments:

FASTMath has developed a projected precondtioned conjugate gradient (PPCG) algorithm for computing a relatively large number of eigenpairs of a Hermitian matrix. The main feature of the algorithm is that it performs a minimal number of Rayleigh-Ritz calculations within a subspace of a large dimension, which is often a bottleneck that requires solving a relatively large dense eigenvalue problem. Instead, the new algorithm obtains updates of the approximation by solving a number of independent 3x3 small eigenvalue problems and performing a Cholesky QR factorization, which can be implemented efficiently on leadership-class machines. We have shown that PPCG is generally two times faster than the existing eigensolver in the quantum espresso electronic structure calculation software package.

We have also developed a new algorithm called a Generalized Preconditioned Local Harmonic Ritz Projection (GPLHR) method for computing interior eigenvalues of a non-Hermitian matrix. The algorithm is closely related to a block version of the Jacobi-Davidson algorithm. It reuses the Krylov subspace constructed to solve the Newton correction equation to obtain approximation to the desired eigenpairs.

We have also developed a structure-preserving algorithm for solving the Bathe Salpeter eigenvalue problem. This problem has a very special structure and is a special class of structured eigenvalue problems called Hamiltonian eigenvalue problems. We have developed a parallel algorithm that preserves the desire eigenvalue pairing and plan to integrate it with the BerkeleyGW software package for computed excited states of electrons in complex materials.

We have also developed new algorithms for estimating the absorption spectrum of molecules and solids in the context of linear response time-dependent density functional theory (TDDFT).

We have developed a spectrum-slicing algorithm and a prototype implementation (called eigenvalue slicing EVSL) for computing a relatively large number of eigenpairs of a Hermitian matrix. This algorithm makes use of our previous work on estimating the spectral density of a Hermitian matrix.

We have studied and implemented flexible solution strategies for nonlinear eigenvalue problems through rational approximations (e.g. using Pade approximants), exploiting potential low-rank properties of the operators that define the problem.

This cover page highlights the excitation energies calculated by the GPLHR algorithm developed by FASTMath.

This figure highlights the absorption spectrum of a large molecule calculated by the Lanczos-based spectrum estimation algorithm matching well with a time domain simulation (which is more costly).

This figure shows the type of polynomial filters constructed for the spectrum slicing algorithm.



Esmond G. Ng

Lawrence Berkeley National Laboratory, One Cyclotron Road, Mail Stop 50A3111, Berkeley, CA 94720

Chao Yang

Lawrence Berkeley National Laboratory, One Cyclotron Road, Mail Stop 50F, Berkeley, CA 94720