Next: 4. Tests of the
Up: Preconditioned conjugate gradient method
Previous: 2. Formulation of the
3. The iterative method
We shall now consider the case of a real, localized, nonorthogonal
basis set, and assume that a real symmetric generalized eigenvalue
problem is to be solved. To obtain the lowest eigenstates, we
minimize the objective function which is the sum of
eigenvalues (formed by the Rayleigh quotients)

(10) 
subject to the orthogonality constraints of Eq. (8). takes its minimum value when
spans the same subspace as the lowest
eigenvectors of Eq. (7). Even though the procedure
given below is for a single eigenvector update, it can be generalized
easily to an eigenvector (or block) update (see Appendix A).
The derivative of with respect to
is

(11) 
Eq. (11) defines a covariant gradient

(12) 
As pointed out by White et al. [19], it is important
to consider the tensor property of the search direction. We define
the dual basis functions
by the conditions

(13) 
The metric tensor
can be defined in terms of the
dual basis functions where

(14) 
It can be shown that
transforms covariant vectors
into contravariant vectors and that
. Hence we transform the covariant gradient
into a contravariant gradient
by using
the metric tensor
where

(15) 
The contravariant gradient can then be used to update the eigenvector
coefficients in Eq. (4).
The constraints of Eq. (8) can be maintained
(to first order) by ensuring that the search direction
obtained from
is orthogonal to the
space spanned by all the current approximate eigenvectors. By writing

(16) 
and imposing the requirement that
for all and , we find

(17) 
We then have

(18) 
and

(19) 
We can use Eq. (18) as the steepest descent
direction for constructing the conjugate gradients. However, the
convergence of the solution depends strongly on the ratio of the
largest and smallest eigenvalues of [14,20].
Since the largest eigenvalues are dominated by the basis functions
with large kinetic energy, we precondition the search direction using
the kinetic energy matrix where

(20) 
We propose to obtain the preconditioned steepest descent direction
in the same manner as in Ref. [14] from the equation

(21) 
which amounts to finding
by solving

(22) 
sets the kinetic energy scale for the preconditioning:
components of the gradient corresponding to basis functions with
kinetic energy much lower than are unaffected by the
preconditioning, whereas the contribution of components with kinetic
energy much higher than is suppressed. The limit
thus corresponds to the case of no
preconditioning, while the effect of preconditioning becomes stronger
as
. Preconditioning which is too aggressive
leads to a degradation of performance, and even the wrong answer being
obtained, because it can reorder the lowest eigenvectors. We discuss
the choice of in Sec. 4. This preconditioning
scheme does not rely on the ``diagonal approximation'' used in Ref. [14], which is appropriate in that case because the
overlap between different basis functions is not extensive. One can
solve Eq. (22) by using the standard preconditioned
conjugate gradient method for linear systems
[4,21].
The search direction to be obtained from
is also
required to be orthogonal to all approximate eigenvectors. By
carrying out the same procedure as in Eq. (16), we
find the gradient which is orthogonal to all approximate eigenvectors
is given by

(23) 
In the conjugate gradient minimization method,
will be used to construct a conjugate search direction
where

(24) 
where is from the previous iteration. We give
the expression for in the PolakRibière formula where

(25) 
The tilde signs again signify the quantities from the previous
iteration. Line minimization (see Appendix B) of is then
performed along the direction
where

(26) 
which is orthogonal to all approximate eigenvectors. We can
systematically update each eigenvector sequentially until the minimum
value of is found. The single eigenvector update procedure
described above can be generalized to a block update procedure where
all approximate eigenvectors are updated simultaneously. The
pseudocode for the block update procedure can be found in Appendix A.
Next: 4. Tests of the
Up: Preconditioned conjugate gradient method
Previous: 2. Formulation of the
Peter Haynes