# Order of scaling for different algorithms

There are many different computational methods used in matter modelling. For example: solving multi-electron Schroedinger equation, DFT with different approximations, Quantum Monte Carlo, etc.

How does each method scale with system size (and if possible, can you give a brief reason why)?

• +1. I think each QMC method (FCIQMC, VMC, DMC, AFQMC, etc.) could be the subject of one question, each deterministic Schroedinger-equation solver (CI, CC, MP2, CASSCF, etc.) can be the subject of another question, and so on. Mixing QMC with DFT and deterministic Schroedinger-equation solvers, seems like it could get quite messy (?). For QMC, perhaps the scaling properties can be discussed in each answer here. Jul 26 '20 at 3:10
• @NikeDattani. Yes. There is a good chance that this will become chaos. How do you suggest changing this question? May be limiting to only DFT?
– Thomas
Jul 26 '20 at 3:12

From my experience with Stochastic Series Expansion (SSE) QMC (a type of discrete-time QMC) the computational cost scales like $$\beta L^d$$.

In practice, it's often important to account for the finite-size gap $$\Delta \propto 1/L$$, so to stay consistently above or below that finite-size gap, $$\beta$$ is typically set to scale as $$\beta = cL$$, where $$c$$ is some constant, so the full scaling to see a desired effect is usually $$L^{d+1}$$.

I don't have experience with other forms of QMC, like continuous time QMC, but I believe they are similar.

Conventional implementations of Kohn-Sham DFT scale cubically with system size. This is principally because at some point they:

• orthonormalise a set of $$N$$ trial states, each expressed in a basis comprising $$M$$ basis states; this has a computational cost $$O(MN^2)+O(N^3)$$
• diagonalise a dense Hamiltonian matrix in the subspace of $$N$$ trial states, which has computational cost $$N^3$$

The number of basis states in the basis, $$M$$, also scales with simulation size. Precisely how it scales with simulation size depends on the nature of the basis set; for example, in plane-wave bases the number of states is proportional to the simulation volume, whereas in local basis sets it is proportional to the number of electrons.

The problem can be recast in terms of the density matrix, rather than the trial states directly, and for systems with a band-gap the off-diagonal terms in the real-space density-matrix $$D({\bf r},{\bf r^\prime})$$ decay exponentially with distance $$\vert{\bf r}-{\bf r^\prime}\vert$$. This allows the density matrix to be truncated safely beyond some chosen cut-off distance which, in turn, allows linear scaling methods to be used.