Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] acpz_v1_0.gz(22 Kbytes)
Manuscript Title: A Davidson program for finding a few selected extreme eigenpairs of a large, sparse, real, symmetric matrix.
Authors: A. Stathopoulos, C.F. Fischer
Program title: DVDSON
Catalogue identifier: ACPZ_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 79(1994)268
Programming language: Fortran.
Computer: Sun-3/80.
Operating system: Sun OS Release 4.1.2, Unix System V/386 3.2.
Keywords: General purpose, Eigenvalue, Eigenvector, Sparse, Symmetric matrix, Matrix-vector Multiplication, Davidson method, Lanczos method, Electronic structure, Computational physics, Computational quantum Chemistry.
Classification: 4.8.

Nature of problem:
Finding a few extreme eigenpairs of a real, symmetric matrix is of great importance in scientific computations. Examples abound in structural engineering, quantum chemistry and electronic structure physics [1,2]. The matrices involved are usually too large to be efficiently solved using standard methods. Moreover, their large size often prohibits full storage forcing various sparse representations. Even sparse representations cannot always be stored in main memory [3]. Thus, an iterative method is needed that converges rapidly to the few eigenpairs required and takes advantage of the symmetry, sparsity and possibly the secondary storage of the matrix.

Library Routines used: LAPACK, BLAS


Solution method:
This program implements a version of the original Davidson method [4], focusing on high performance on vector processors and adopting many previously proposed extensions [3,5,6] which have not appeared together in a published program. The features of the current version are:
  • Selected eigenpairs at either the lower or the higher end of the spectrum can be found, without enforcing convergence for interspersed unwanted ones.
  • The basis of eigenvectors as well as all other program arrays are kept in memory.
  • The matrix-vector multiplication routine must be supplied by the user.
  • A block method is used, where more than one vector may be targeted in each iteration.
  • The vectors offering improvement are targeted without the need to explicitly compute all residuals.
  • A reorthogonalization procedure is included for numerical stability.
  • Initial eigenvector estimates can either be provided by the user or generated by the program.
  • The user can control basis size, block size, reorthogonalization, and convergence through three criteria.
  • All floating-point intensive code is vectorizable.

Restrictions:
For performance improvements, DVDSON keeps the basis in memory which may cause memory overflow problems if exceedingly large matrices are used. This program bears two of the Davidson method's weaknesses: convergence is slow when the diagonal of the matrix is constant and not guaranteed for the required eigenpair when the matrix is permutationally equivalent to a block diagonal matrix.

Running time:
For each eigenpair, the Davidson method takes 10-30 iterations if the block size is one. For larger block sizes the number of iterations decreases significantly.

References:
[1] B.N. Parlett, SIAM J. Sci. Stat. Comput. 5(1984) 590.
[2] C.F. Fischer, Comput. Phys. Commun. 64(1991)369.
[3] E.R. Davidson, Comput. Phys. Commun. 53(1989)49.
[4] E.R. Davidson, J. Comput. Phys. 17(1975)87.
[5] G. Cisneros, M. Berrondo and C.F. Bunge, Compu. Chem. 10(1986)281.
[6] J. Weber, R. Lacroix and G. Wanner, Comput. Chem. 4(1980)55.