XC Linear Scaling

A simple implementation of the above procedure will produce an algorithm which scales as O(N³). In 1993 Johnson [148] showed that the integration could be performed in only linear work, with a few modifications to the above procedure taking advantage of the fast decay of the basis functions.

For each basis function $\phi_{\alpha}$, centered at ${\bf R}_{\alpha}$, a sphere is defined beyond which its influence is deemed negligible. The radius of the sphere, $\lambda_{\alpha}$, is found from choosing a threshold $\epsilon$ and requiring that $\vert\phi_{\alpha}({\bf r})\vert \le \epsilon$ for every point outside the sphere. For any grid point ${\bf r}_{g}$ all significant basis functions can be found by selecting those that fulfill
$$\begin{align}\vert{\bf r}_{g} - {\bf R}_{\alpha}\vert \le \lambda_{\alpha}. \end{align}$$
Therefore a list of all significant basis functions is created for every grid point. The important property of the list is that the number of significant basis functions at each grid point becomes independent of size for sufficiently large molecules. The construction of this list is an O(N²) process -- (number of grid points) x (number of basis functions), but Stratman et al. [149] have noticed that the computational time involved is insignificant for even very large molecules ( C₃₈₄H₄₈). If the formation of this list becomes a problem in the future, Pérez-Jordá and Yang [150] have reformulated the algorithm into one which scales as $O(N \log N)$.

The density at any grid point is given by
$$\begin{align}\rho({\bf r}_{g}) = \sum_{\alpha,\beta} P_{\alpha \beta} \phi_{\alpha}({\bf r}_{g}) \phi_{\beta}({\bf r}_{g}) \end{align}$$
which forces the evaluation of the density to scale as O(N³). However, if the summation is restricted to only those basis functions which are significant at the grid point, the computational effort per grid point becomes independent of size (for a sufficiently large molecule) and the density evaluation should scale linearly with the molecular size.