# Why does orbital-free DFT scale linearly with system size?

In answering another question here (Is there any relevant DFT formalism apart from the Kohn-Sham approach?), I came across numerous statements that Orbital-Free DFT should scale linearly with system size. From the implementation details in GPAW, this seems to be a result of using the same machinery as for a typical Kohn-Sham DFT calculation, but with only a single "orbital" (actually the square root of the density). But from the other statements, there seems to be a more fundamental physical reason why we would expect orbital free DFT to scale linearly with system size. Why should orbital free DFT be linearly scaling and by what metric for system size (since KS DFT is usually said to scale cubically with the number of orbitals)?

There is linear scaling DFT, where you use density matrix as your object throughout SCF iterations instead of the wavefunctions. The linear scaling comes from the sparsity assumption/truncation on the density matrix. Usually, the wavefunctions are dense vectors, and any eigensolver results in cubic scaling with respect to the number of electrons/bases. However, if the density matrix is truncated to a sparse matrix with linear scaling sparsity (w.r.t. number of electrons), then the linear eigensolver in SCF iteration can be implemented through a density filtering method. The main operation in the density filtering method is multiplying the Hamiltonian operator to the density matrix, which scales linearly. Therefore, in the end, the overall cost for the DFT scales linearly.

Regarding the sparsity of density matrix, it can be related to Wannier function, which is localized molecular orbital of crystalline system. The Wannier function is much sparser than the wavefunction (theoretical understanding is available for gaped systems). In DFT calculation, Wannier function can be constructed through rotating (transforming) your wavefunctions. Since Wannier function decays exponentially, it can be well approximated by a truncated function with constant size support. On the other hand, the density matrix (the product of wavefucntions) equals to the product of Wannier functions (two rotation matrices in the middle cancel with each other). Hence the density matrix is sparse and the sparsity scales linearly with respect to the number of electrons.

I am not familiar with OFDFT. Since OFDFT also uses the density matrix as the object, I guess the linear scaling argument is due to the similar reason above.

For linear scaling both Hamiltonian matrix ($$H$$) and density matrix ($$D$$) need to be sparse. If either $$D$$ or $$H$$ are dense, then the resulting scaling is quadratic $$O(N^2)$$. When both $$H$$ and $$D$$ are dense, then the scaling is cubic $$O(N^3)$$. As mentioned above the underlying computational cost is determined by matrix-matrix multiplication. For example, to calculate $$C = A * B$$ we note that one has to find $$N^2$$ elements of $$C$$ and each element of $$C$$ requires $$2N$$ operations:

$$C(i,j) = \sum_{k=1}^N A(i,k) * B(k,j)$$

The reduction from cubic to quadratic or linear comes from the assumption that $$A$$ and/or $$B$$ are not dense and so the summation is reduced to some "fixed" number of elements smaller than N or perhaps the structure of C fixes the number of elements. Hence, not all $$N^2$$ elements are required to be calculated. For interesting problems of materials science, physics, chemistry, it is very difficult to achieve linear scaling because, depending on the choice of basis set representation, one matrix can be dense which kills linear scaling. Typically, localized orbital basis sets are most promising because they lead to dense Hamiltonian, but for metallic systems the Density matrix becomes delocalized and dense. You can switch to delocalized orbitals in hope to get sparse density matrix but you will get delocalized, dense hamiltonian matrix. In practice the linear scaling is only achieved in the so called "biological systems" (such as a box of waters) in which wide band gap leads to sparse density and hamiltonian matrices. There is a good paper on this topic: Stefan Godecker, Rev. Mod. Phys. 1998.

• I can't seem to find the article you are referring. I guess the following would match your answer: Goedecker, S. Linear scaling electronic structure methods. Rev. Mod. Phys. 1999, 71 (4), 1085–1123. DOI: 10.1103/RevModPhys.71.1085. – Martin - マーチン May 16 at 9:45
• that is the one – Jacek Jakowski May 17 at 2:43