Lecture 13: Iterative methods - Efficient Plane Wave and Grid Calculations
Return to Main Page
No Power Point Slides for Lecture 13
Text: Appendices L and M.
Iterative methods are extensively used in modern electronic structure codes. Because they are much faster than traditional methods, they have made possible entirely new advances in calculations of properties of materials.
In traditional methods the wavefunctions are expanded in a basis set of size NB, leading to a
hamiltonian matrix of size NB x NB. Finding the eigenvectors with a standard diagonalization
routine such as LAPACK requires a number of operations proportional to NB3. In addition, solution of the self-consistent Kohn-Sham equations involves repeated updating of the hamiltonian and diagonalizations.
Iterative methods recast the problem as a minimization procedure, which can often be viewed as either the embodiment of physical principles or as the adaptation of powerful numerical techniques.
The result is that methods such as plane waves can often be extremely efficient even for very large problems.
Iterative methods are particularly important for plane wave and uniform grid methods which are examples of the "keep it simple" approach. All matrix elements are easy to calculate, but the penalty to be paid is that many plane-waves or grid points
are necessary for the accurate representation of the wavefunctions.
Iterative methods allow us to handle the large basis sets or grids in an efficient manner.
Important reference for numerical methods: Press, Teukolsky, Vetterling,
Flannery, Numerical Recipes (in C, Fortran,...).
Review Article: M. C. Payne, M. P. Teter, D. C. Allen, T. A. Arias, J. D. Joannopoulos, Rev. Mod. Phys. 64, 1045 (1992).
- Why (when) use iterative methods? (App. M)
- Solution of Schrodinger-like equations in a basis of size NB
- Diagonalization scales as NB3
- Two approaches:
- Small basis sets adapted to the problem: LCAO, LMTO, ...
- Large basis sets applicable to general problems: plane-waves, real space grids, ....
- Iterative methods very useful for finding a small number of
eigenvectors of large problems
- Iterative methods in quantum mechanics (App. M - Physics principles of perturbations - iterative methods in linear algebra)
- Iterating H |psin > ---> |psin+1 >
- Grandfather of iterative methods: Jacobi 1848
- Basic idea: Minimization of the residual R
- Preconditioning
- Krylov subspace
- Lanczos method
- Davidson, Residual minimization in subspace (RMM-DIIS - Pulay)
- Powerful approaches for independent-particle and many-body problems
- Minimization methods (App. M, Sec. 8 and App. L -- Physics principle of minimizing energy - numerical analysis problem of minimizing a function of many variables)
- Variational principle
- Steepest descent
- Conjugate directions and metric methods
- Conjugate gradient method
- The problem of constraints - minimization preserving orthonormality
- Quasi-Newton methods
- Broyden Jacobian update methods
- Special advantages of plane waves and uniform grids (App. M, Sec. 11)
- Kinetic and potential operations
- Fast Fourier Transform (FFT), aliasing, and efficient plane wave algorithms
- Putting it together in full algorithms
- The Teter-Payne-Allan pre-conditioned conjugate-gradient "band-by-band" solution of the self-consistent Kohn-Sham problem - used in ABINIT
- The RMM-DIIS solution for eigenvectors - used in VASP
- Other proposals - Lanczos, ....
- Next Time: "quantum" molecular dynamics; the Car-Parrinello methods