Daniel Osei-Kuffuor
An accurate and scalable O(N) algorithm for Large-Scale First-Principles Molecular Dynamics computations

Lawrence Livermore National Laboratory
P O Box 808
L-561
Livermore
CA 94551
oseikuffuor1@llnl.gov
Daniel Osei-Kuffuor
Jean-Luc Fattebert

Traditional algorithms for First-Principles Molecular Dynamics (FPMD) simulations only gain a modest capability increase from current petascale computers, due to their $O(N^3)$ complexity. To address this issue, we are developing a truly scalable FPMD algorithm, based on density functional theory (DFT), with $O(N)$ complexity and controllable accuracy. The computational model uses a general non-orthogonal orbital formulation for the energy functional in the DFT equations, which requires knowledge of selected elements of the inverse of the associated overlap matrix. We present a scalable algorithm for approximately computing selected entries of the inverse of the overlap matrix, based on an approximate inverse technique, by inverting local blocks corresponding to principal submatrices of the global overlap matrix. The new FPMD algorithm exploits sparsity and uses nearest neighbor communication to provide a computational scheme capable of extreme scalability. Accuracy is controlled by the mesh spacing of the finite difference discretization, the size of the localization regions in which the electronic wave functions are confined, and a cutoff beyond which the entries of the overlap matrix can be omitted when computing selected entries of its inverse. We demonstrate the algorithm's excellent parallel scaling for up to $O(100K)$ atoms on $O(100K)$ processors, with a wall-clock time of $O(1)$ minute per molecular dynamics time step.