Chemistry Reference
In-Depth Information
EIGENVALUE PROBLEMS
It was mentioned earlier that aspects of eigenvalue problems exist that
make them more difficult to solve than the Poisson equation. Typically, we
would like to solve for the first
q
eigenfunctions for a given Hamiltonian
operator. This is what is done in a Kohn-Sham DFT calculation,
110,111
where
those
q
states are populated with 2
q
electrons, and the self-consistent solution
process minimizes the total electronic energy when converged. The most
difficult part of a DFT calculation is the eigenvalue problem, which can
be solved directly or cast in a different format, such as a density-matrix formu-
lation.
112,113
Even though the Hamiltonian operator is a linear operator,
solving the eigenvalue part of the problem is a nonlinear process since we
seek both the eigenvalues and the eigenfunctions.
106
First consider iterations on a single, fine grid. The relaxation step,
Eq. [9], is similar to the Poisson problem. Following the relaxation, additional
operations must be performed, however. Those operations correspond to
orthonormalizing the eigenfunctions in a Gram-Schmidt procedure and updat-
ing the eigenvalues (Eq. [27]). The Gram-Schmidt orthogonalization method
is discussed in applied mathematics texts (see Ref. 114 as an example). In this
step, the dot products of eigenvectors (the values of the wave function on the
grid) with all other eigenvectors must be computed. This operation thus scales
as
q
2
N
g
,or
N
e
, where
N
e
is the number of electrons. (The number of eigen-
functions
q
is typically
N
e
2, and the number of grid points required increases
linearly with the number of electrons.) This is a major bottleneck for eigenva-
lue problems in which the eigenfunctions span the whole physical domain.
Notice also that the updates of all the eigenvalues by Eq. [27] and the relaxa-
tion step for the eigenfunctions both scale as
qN
g
or
N
e
. It is clear from this
discussion that the only possible way to obtain linear scaling in real space is to
utilize localized functions of some sort.
=
Multigrid for the Eigenvalue Problem
We do not lay out in great detail here the FAS-MG method for the eigen-
value problem. An original effort in this direction was developed in 1983 by
Brandt, McCormick, and Ruge.
106
Their article presents a clear discussion of
the FAS method applied to eigenvalue problems. The algorithm contains all
the basic features discussed above for the Poisson equation but adds several
necessary modifications. Those additions will be summarized here briefly; the
reader is referred to the original article for the technical details.
106
One complication in the eigenvalue problem that becomes apparent
when writing a solver is that the wave functions are oscillatory for states above
the ground state. This suggests that the coarsest grid that may be used must
still have enough resolution to at least approximately represent the eigenfunc-
tion variations. This in turn slows down the convergence rates relative to the
