Expediting Solutions for the Electronic Structure of Large Systems: A Spectrum Slicing Algorithm

Solving the Kohn-Sham equation requires computing a set of low lying eigenpairs. The standard methods for computing such eigenpairs require two procedures: (a) maintaining the orthogonality of an approximation space, and (b) forming approximate eigenpairs with the Rayliegh-Ritz method. These two procedures scale cubically with the number of desired eigenpairs. We present a method, applicable to {\it any} large Hermitian eigenproblem, by which the spectrum is partitioned among distinct groups of processors. This ``divide and conquer'' approach serves as a parallelization scheme at the level of the solver, making it compatible with existing schemes that parallelize at a physical level, {\it e.g.}, {\bf k}-points or symmetric representations, and at the level of primitive operations, matrix-vector multiplication. In addition, among all processor sets, the size of any approximation subspace is reduced, thereby reducing the cost of orthogonalization and the Rayleigh-Ritz method. We will explain the key aspects of the algorithm that give reliability, and demonstrate the accuracy of the algorithm by computing the electronic structure of a core-shell nanocrystal and a DNA segment. Overall scaling and the utility of the method for a wide variety of applications will be discussed.