ONX: Order N Exchange

The first method to be able to calculate the Hartree-Fock exchange energy in only O(N) work was developed by Schwegler and Challacombe in 1996 [185]. It can be shown that the one particle density matrix $\rho_{1}({\bf r}_{1},{\bf r}_{2})$ decays exponentially with $\vert{\bf r}_{1}-{\bf r}_{2}\vert$ for one-dimensional insulators [186]. A similar behaviour for three-dimensional insulators has also been speculated. Kohn [187] conjectured that, for disordered molecular systems, the density matrix behaves as
$$\begin{align}\rho({\bf r}_{1},{\bf r}_{2}) \sim e^{-\vert{\bf r}_{1}-{\bf r}_{2}\vert/l}, \qquad (\vert{\bf r}_{1}-{\bf r}_{2}\vert \rightarrow \infty) \end{align}$$
where l is a system-specific parameter. This fast decay should allow the long-range exchange matrix elements to be screened out.

This screening had not been possible previously as the off-diagonal elements of the density matrix were shown to decay only slowly. Schwegler and Challacombe have pointed out that this slow decay is simply an artifact of the incomplete basis set. Thus, it was thought reasonable to assume
$$\begin{align}K_{ab} = \iint \frac{\rho_{ab}({\bf r}_{1},{\bf r}_{2})}{\vert{\bf ... ...^{-\vert{\bf r}_{1}-{\bf r}_{2}\vert/l} \, d{\bf r}_{1} d{\bf r}_{2} \end{align}$$
where
$$\begin{align}\rho_{ab}({\bf r}_{1},{\bf r}_{2})=\phi_{a}^{*}({\bf r}_{1})\phi_{b}({\bf r}_{2}) \end{align}$$
which, with the introduction of some thresholding criteria, leads to an O(N) algorithm for computing the exchange matrix.

The ONX method is not without its problems however. Most importantly, it is only linear for insulators. For non-insulators the computational time becomes the traditional O(N²). The algorithm is also extremely expensive compared to the CFMM (which is calculating the Coulomb matrix). This shows just how much harder an O(N) exchange algorithm is compared to the Coulomb problem.