11
$\begingroup$

Theoretically, how does the time to do a density functional theory (DFT) calculation scale with the number of electrons? I'm interested in "typical" DFT implementations such as VASP, ABINIT, etc., not O(N) codes.

$\endgroup$
11
$\begingroup$

The simplest correct answer is that DFT is in $O(N_e^3)$. This comes from the idea that you are ultimately diagonalizing a Hamiltonian with dimension proportional to the number of elections and diagonalization is technically $O(n^3)$.


In reality, DFT is a bunch of steps and different steps are rate-limiting in different context. If we restrict ourselves to plane-wave (PW) DFT (VASP, ABINIT, QE, and others), we can make some stronger statements. An important idea to understand for PW DFT codes is that the Hamiltonian is never stored as a big matrix; instead, the action of the Hamiltonian operator is computed and used in what are generally `in house' iterative diagonalizers (conjugate gradient, davidson, etc). These diagonalizers are formally $O(n_e MV)$, where $MV$ is the cost of computing the action of the Hamiltonian, but given their role in an larger self-consistent algorithm, they tend to perform much faster.

The process of computing the action of the Hamiltonian occurs in a couple steps:

  • Local potential in real space requires an FFT, $O(n_v \ln n_v)$
  • Projection can occur in real or g-space, $O(n_a n_p)$ or $O(n_a n_p n_v)$, respectively
  • The non-local potential is either diagonal or block diagonal, $O(n_a n_p)$ or $O(n_a n_p^2)$, respectively

all of this has to happen once per electron (really, wave-function), so add a factor of $n_e$ to all of them.

Through some means (Gram-Schmidt, for example) the wave-functions (eigenfunctions of the Hamiltonian) must be kept orthogonal to one another, $O(n_e^2 n_v)$

Finally, the wave-functions need to be composed into an electron-density. In PW codes, this is accomplished with one last FFT per wave-function (and a sum), $O(n_e n_v \ln n_v)$.

Note that I've put in a few different $n$'s: $n_v$ is related to the volume (really, it is the basis size), $n_p$ is the number of projectors per atom, $n_a$ is the number of atoms, and $n_e$ the number of electrons. Formally $n_v$, $n_a$, and $n_e$ are all linearly related to one another ($n_p$ is a small integer), but you could imagine increasing the volume with fixed number of electrons (adding vacuum in slab/wire geometries) or increasing the number of projectors with fixed number of atoms and electrons (using a more accurate pseudo-potential).

It is common that problems are FFT-limited, in which case they are effectively $O(n^2 \ln n)$, which is a somewhat common answer in the literature, if not technically correct.

$\endgroup$
  • $\begingroup$ Do you really need the full eigendecomposition, or only a small part of the spectrum? $\endgroup$ – Victor Liu Mar 12 '13 at 5:58
  • $\begingroup$ You need $O(n_e)$ eigenfunctions (generally $n_e /2$). $\endgroup$ – Max Hutchinson Mar 12 '13 at 9:19
  • $\begingroup$ Thanks for your answer! Can you recommend any papers that have discussed this issue or performed benchmarks? $\endgroup$ – Max Radin Mar 22 '13 at 17:05
  • 1
    $\begingroup$ G. Kresse, Computational Materials Science 6, 15 (1996) is the standard introduction to VASP; you might want to start with section 6. R. M. Martin, Electronic Structure: Basic Theory and Practical Methods (Cambridge Univ Pr, 2004) is a great introduction to DFT (plane-wave and otherwise), but is probably less explicit about complexity. $\endgroup$ – Max Hutchinson Apr 1 '13 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.