Linear-scaling density-functional-theory calculations of electronic structure based on real-space grids: Design, analysis, and scalability test of parallel algorithms

We have implemented parallel algorithms for density-functional-theory (DFT) based electronic-structure calculations. These include a plane-wave based algorithm, a real-space-grid algorithm based on a high-order finite difference method, and a linear-scaling real-space algorithm using localized orbitals. Parallelization schemes are described for these algorithms, and the computational complexity and the communications involved in the resulting parallel algorithms are analyzed. Scalability tests of these algorithms on massively parallel computers show that the linear-scaling DFT algorithm is highly scalable. For a 110,592-atom gallium arsenide system on 1024 IBM SP3 processors, the parallel efficiency is as high as 93%. © 2001 Elsevier Science B.V. All rights reserved.