X

Search Results

Searching....

A.9 Quadratic Scaling

A.9.1 Overview

(April 13, 2024)

The success of quantitative modern quantum chemistry, relative to its primitive, qualitative beginnings, can be traced to two sources: better algorithms and better computers. While the two technologies continue to improve rapidly, efforts are heavily thwarted by the fact that the total number of ERIs increases quadratically with the size of the molecular system. Even large increases in ERI algorithm efficiency yield only moderate increases in applicability, hindering the more widespread application of ab initio methods to areas of, perhaps, biochemical significance where semi-empirical techniques 291 Dewar M. J. S.
Org. Mass. Spect.
(1993), 28, pp. 305.
Link
have already proven so valuable.

Thus, the elimination of quadratic scaling algorithms has been the theme of many research efforts in quantum chemistry throughout the 1990s and has seen the construction of many alternative algorithms to alleviate the problem. Johnson was the first to implement DFT exchange/correlation functionals whose computational cost scaled linearly with system size. This paved the way for the most significant breakthrough in the area with the linear scaling CFMM algorithm 1312 White C. A. et al.
Chem. Phys. Lett.
(1994), 230, pp. 8.
Link
leading to linear scaling DFT calculations. 1314 White C. A. et al.
Chem. Phys. Lett.
(1996), 253, pp. 268.
Link
Further breakthroughs have been made with traditional theory in the form of the QCTC 204 Challacombe M. et al.
Modern developments in hartree-fock theory: fast methods for computing the coulomb matrix
(1996), 1, pp. 53.
Link
, 203 Challacombe M., Schwegler E., Almlöf J.
J. Chem. Phys.
(1996), 104, pp. 4685.
Link
, 205 Challacombe M., Schwegler E.
J. Chem. Phys.
(1997), 106, pp. 5526.
Link
and ONX 1100 Schwegler E., Challacombe M.
J. Chem. Phys.
(1996), 105, pp. 2726.
Link
, 1101 Schwegler E., Challacombe M.
J. Chem. Phys.
(1996), 106, pp. 9708.
Link
algorithms, while more radical approaches 23 Adamson R. D., Dombroski J. P., Gill P. M. W.
Chem. Phys. Lett.
(1996), 254, pp. 329.
Link
, 312 Dombroski J. P., Taylor S. W., Gill P. M. W.
J. Phys. Chem.
(1996), 100, pp. 6272.
Link
may lead to entirely new approaches to ab initio calculations. Investigations into the quadratic Coulomb problem has not only yielded linear scaling algorithms, but is also providing large insights into the significance of many molecular energy components.

Linear scaling Coulomb and SCF exchange/correlation algorithms are not the end of the story as the 𝒪(N3) diagonalization step has been rate limiting in semi-empirical techniques and, been predicted to become rate limiting in ab initio approaches in the medium term. 1186 Strout D. L., Scuseria G. E.
J. Chem. Phys.
(1995), 102, pp. 8448.
Link
However, divide-and-conquer techniques 1358 Yang W.
Phys. Rev. A
(1991), 44, pp. 7823.
Link
, 1359 Yang W.
Phys. Rev. Lett.
(1991), 66, pp. 1438.
Link
, 1357 Yang W., Lee T.-S.
J. Chem. Phys.
(1995), 103, pp. 5674.
Link
, 719 Lee T.-S., York D. M., Yang W.
J. Chem. Phys.
(1996), 105, pp. 2744.
Link
and the recently developed quadratically convergent SCF algorithm 903 Ochsenfeld C., Head-Gordon M.
Chem. Phys. Lett.
(1997), 270, pp. 399.
Link
show great promise for reducing this problem.