Efficient low-order scaling method for large-scale electronic structure calculations with localized basis functions

An efficient low-order scaling method is presented for large-scale electronic structure calculations based on the density-functional theory using localized basis functions, which directly computes selected elements of the density matrix by a contour integration of the Green’s function evaluated with a nested dissection approach for resultant sparse matrices. The computational effort of the method scales as $\text{O}\left[N{\left({\text{log}}_{2}N\right)}^2\right]$, $\text{O}\left(N^2\right)$, and $\text{O}\left(N^{7/3}\right)$ for one-, two-, and three-dimensional systems, respectively, where $N$ is the number of basis functions. Unlike $\text{O}\left(N\right)$ methods developed so far the approach is a numerically exact alternative to conventional $\text{O}\left(N^3\right)$ diagonalization schemes in spite of the low-order scaling, and can be applicable to not only insulating but also metallic systems in a single framework. It is also demonstrated that the well separated data structure is suitable for the massively parallel computation, which enables us to extend the applicability of density-functional calculations for large-scale systems together with the low-order scaling.

Figure 1

(Color online) (a) The initial numbering for atoms in a linear-chain molecule consisting of ten atoms described by the $s$-valent NNTB and its corresponding matrix, (b) the renumbering for atoms by the first step in the nested dissection and its corresponding matrix, (c) the renumbering for atoms by the second step in the nested dissection and its corresponding matrix, and (d) the binary tree structure representing hierarchical interactions between domains in the structured matrix by the numbering shown in (c).

Figure 2

(Color online) (a) The square lattice model, described by the $s$-valent NNTB, of which unit cell contains 1024 atoms with periodic boundary condition. The right blue and red circles correspond to atoms in two domains and a separator, respectively, at the first step in the nested dissection. (b) The square lattice model at the final step in the nested dissection. The separator at the innermost and the outermost levels are labeled as separators 0 and 5, respectively, and the separators at each level are constructed by atoms with a same color.

Figure 3

(Color online) The development of recurrence formulas, Eqs. (28, 29, 30, 31, 32), which implies that the recurrence starts from $p=m+1=0$ and ends at $p=m+1=P$. The number on the right-hand side is the multiplicity for similar calculations by Eq. (29) due to the index $n$ at each $m+1$.

Figure 4

(Color online) The elapsed time of the inverse calculation by Eqs. (28, 29, 30, 31, 32) for a 1D linear chain, a 2D square lattice, and a 3D cubic lattice systems as a function of number of atoms in the unit cell under periodic boundary condition. The Hamiltonian of the systems is described by the $s$-valent NNTB models. The line for each system is obtained by a least-square method, and the computational orders obtained from the fitted curves are $\text{O}\left[N^{0.90}{\left({\text{log}}_{2}N\right)}^2\right]$, $\text{O}\left(N^{1.90}\right)$, and $\text{O}\left(N^{2.35}\right)$ for the 1D, 2D, and 3D systems, respectively. The size of domains at the innermost level is set to 20 for all the cases.

Figure 5

(Color online) The norm of residual in the SCF calculation of DNA, with a periodic double helix structure (650 atoms/unit) consisting of cytosines and guanines, calculated by the conventional and proposed methods, where the residual is defined as the difference between the input and output charge densities in momentum space. The electric temperature of 700 K and 80 poles for the contour integration are used. The number in parenthesis is the total energy (hartree) of the system calculated by each method.

Figure 6

(Color online) The number of iterations for searching the chemical potential which conserves the total number of electrons within a criterion of ${10}^{-8}$ electron/system for a ${\text{C}}_{60}$ molecule, DNA, and a ${\text{Pt}}_{63}$ cluster, where the electric temperature of 600, 700, and 1000 K, and 80, 80, and 90 poles for the contour integration are used for the ${\text{C}}_{60}$ molecule, DNA, and the ${\text{Pt}}_{63}$ cluster.

Figure 7

(Color online) Speed-up ratio in the parallel computation of the diagonalization in the SCF calculation for DNA by a hybrid scheme using MPI and OPENMP. The speed-up ratio is defined by $2T_2/T_p$, where $T_2$ and $T_p$ are the elapsed times obtained by two MPI processes and by the corresponding number of processes and threads. The structure of DNA is the same as in Fig. 5. The parallel calculations were performed on a Cray XT5 machine consisting of AMD opteron quad core processors (2.3 GHz). The electric temperature of 700 K and 80 poles for the contour integration are used. For comparison, the speed-up ratio for the parallel computation of the conventional scheme using Householder and QR methods is also shown for the case with a single thread.