Stochastic algorithms for self-consistent calculations of electronic structures

Ko, Taehee; Li, Xiantao

doi:10.1090/mcom/3826

Stochastic algorithms for self-consistent calculations of electronic structures
HTML articles powered by AMS MathViewer

by Taehee Ko and Xiantao Li;

Math. Comp. 92 (2023), 1693-1728

DOI: https://doi.org/10.1090/mcom/3826

Published electronically: February 28, 2023

HTML | PDF | Request permission

Abstract:

The convergence property of a stochastic algorithm for the self-consistent field (SCF) calculations of electron structures is studied. The algorithm is formulated by rewriting the electronic charges as a trace/diagonal of a matrix function, which is subsequently expressed as a statistical average. The function is further approximated by using a Krylov subspace approximation. As a result, each SCF iteration only samples one random vector without having to compute all the orbitals. We consider the common practice of SCF iterations with damping and mixing. We prove that the iterates from a general linear mixing scheme converge in a probabilistic sense when the stochastic error has a second finite moment.

References

Y. I. Alber, C. Chidume, and J. Li, Stochastic approximation method for fixed point problems, Appl. Math. 3 (2012), no. 12, 2123–2132., DOI 10.4236/am.2012.312A293
H. Avron and S. Toledo, Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM 58 (2011), no. 2, 1–34 (en)., DOI 10.1145/1944345.1944349
A. S. Banerjee, P. Suryanarayana, and J. E. Pask, Periodic pulay method for robust and efficient convergence acceleration of self-consistent field iterations, Chem. Phys. Lett. 647 (2016), 31–35., DOI 10.1016/j.cplett.2016.01.033
T. L. Beck, Real-space mesh techniques in density-functional theory, Rev. Mod. Phys. 72 (2000), no. 4, 1041–1080 (en)., DOI 10.1103/RevModPhys.72.1041
C. Bekas, E. Kokiopoulou, and Y. Saad, An estimator for the diagonal of a matrix, Appl. Numer. Math. 57 (2007), no. 11-12, 1214–1229. MR 2355413, DOI 10.1016/j.apnum.2007.01.003
L. Bottou and O. Bousquet, The Tradeoffs of Large Scale Learning, Advances in Neural Information Processing Systems, vol. 20, 2007.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal, Optimization methods for large-scale machine learning, SIAM Rev. 60 (2018), no. 2, 223–311. MR 3797719, DOI 10.1137/16M1080173
D. R. Bowler and M. J. Gillan, An efficient and robust technique for achieving self consistency in electronic structure calculations, Chem. Phys. Lett. 325 (2000), no. 4, 473–476., DOI 10.1016/S0009-2614(00)00750-8
D. R. Bowler, T. Miyazaki, and M. J. Gillan, Recent progress in linear scaling ab initio electronic structure techniques, J. Phys. 14 (2002), no. 11, 2781.
E. Cancès, Self-consistent field algorithms for Kohn–Sham models with fractional occupation numbers, J. Chem. Phys. 114 (2001), no. 24, 10616–10622., DOI 10.1063/1.1373430
Éric Cancès, Gaspard Kemlin, and Antoine Levitt, Convergence analysis of direct minimization and self-consistent iterations, SIAM J. Matrix Anal. Appl. 42 (2021), no. 1, 243–274. MR 4223219, DOI 10.1137/20M1332864
E. Cancès and C. Le Bris, Can we outperform the DIIS approach for electronic structure calculations?, Int. J. Quantum Chem. 79 (2000), no. 2, 82–90., DOI 10.1002/1097-461X(2000)79:2<82::AID-QUA3>3.0.CO;2-I
Eric Cancès and Claude Le Bris, On the convergence of SCF algorithms for the Hartree-Fock equations, M2AN Math. Model. Numer. Anal. 34 (2000), no. 4, 749–774. MR 1784484, DOI 10.1051/m2an:2000102
K. L. Chung, On a stochastic approximation method, Ann. Math. Statistics 25 (1954), 463–483. MR 64365, DOI 10.1214/aoms/1177728716
Y. Cytter, E. Rabani, D. Neuhauser, and R. Baer, Stochastic density functional theory at finite temperatures, Phys. Rev. B 97 (2018), no. 11, 115207., DOI 10.1103/PhysRevB.97.115207
A. Defazio, F. Bach, and S. Lacoste-Julien, Saga: A fast incremental gradient method with support for non-strongly convex composite objectives, arXiv preprint arXiv:1407.0202 (2014).
Fasma Diele, Igor Moret, and Stefania Ragni, Error estimates for polynomial Krylov approximations to matrix functions, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1546–1565. MR 2486853, DOI 10.1137/070688924
Michael Eiermann and Oliver G. Ernst, A restarted Krylov subspace method for the evaluation of matrix functions, SIAM J. Numer. Anal. 44 (2006), no. 6, 2481–2504. MR 2272603, DOI 10.1137/050633846
M. Elstner, D. Porezag, G. Jungnickel, J. Elsner, M. Haugk, Th. Frauenheim, S. Suhai, and G. Seifert, Self-consistent-charge density-functional tight-binding method for simulations of complex materials properties, Phys. Rev. B 58 (1998), no. 11, 7260., DOI 10.1103/PhysRevB.58.7260
Haw-ren Fang and Yousef Saad, Two classes of multisecant methods for nonlinear acceleration, Numer. Linear Algebra Appl. 16 (2009), no. 3, 197–221. MR 2489203, DOI 10.1002/nla.617
Carlos J. García-Cervera, Jianfeng Lu, and Weinan E, A sub-linear scaling algorithm for computing the electronic structure of materials, Commun. Math. Sci. 5 (2007), no. 4, 999–1026. MR 2375058, DOI 10.4310/CMS.2007.v5.n4.a14
S. Goedecker, Linear scaling electronic structure methods, Rev. Mod. Phys. 71 (1999), no. 4, 1085., DOI 10.1103/RevModPhys.71.1085
F. Golse, S. Jin, and T. Paul, The random batch method for $N$-Body quantum dynamics, arXiv preprint arXiv:1912.07424 (2019).
T. P. Hamilton and P. Pulay, Direct inversion in the iterative subspace (DIIS) optimization of open-shell, excited-state, and small multiconfiguration scf wave functions, J. Chem. Phys. 84 (1986), no. 10, 5728–5734., DOI 10.1063/1.449880
J. Hermann, Z. Schätzle, and F. Noé, Deep-neural-network solution of the electronic Schrödinger equation, Nat. Chem. 12 (2020), no. 10, 891–897., DOI 10.1038/s41557-020-0544-y
P. Hohenberg and W. Kohn, Inhomogeneous electron gas, Phys. Rev. (2) 136 (1964), B864–B871. MR 180312, DOI 10.1103/PhysRev.136.B864
Shi Jin and Xiantao Li, Random batch algorithms for quantum Monte Carlo simulations, Commun. Comput. Phys. 28 (2020), no. 5, 1907–1936. MR 4188525, DOI 10.4208/cicp.oa-2020-0168
D. D. Johnson, Modified Broyden’s method for accelerating convergence in self-consistent calculations, Phys. Rev. B 38 (1988), no. 18, 12807., DOI 10.1103/PhysRevB.38.12807
R. Johnson and T. Zhang, Accelerating Stochastic Gradient Descent Using Predictive Variance Reduction, Advances in Neural Information Processing Systems, vol. 26, 2013, pp. 315–323.
D. Kincaid, D. R. Kincaid, and E. W. Cheney, Numerical analysis: mathematics of scientific computing, Vol. 2, American Mathematical Soc., 2009.
W. Kohn and L. J. Sham, Self-consistent equations including exchange and correlation effects, Phys. Rev. (2) 140 (1965), A1133–A1138. MR 189732, DOI 10.1103/PhysRev.140.A1133
G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set, Phys. Rev. B 54 (1996), no. 16, 11169., DOI 10.1103/PhysRevB.54.11169
L. Kronik, A. Makmal, M. L. Tiago, M. Alemany, M. Jain, X. Huang, Y. Saad, and J. R. Chelikowsky, PARSEC–the pseudopotential algorithm for real-space electronic structure calculations: recent advances and novel applications to nano-structures, Phys. Status Solidi (b) 243 (2006), no. 5, 1063–1079., DOI 10.1002/pssb.200541463
Harold J. Kushner, On the stability of stochastic dynamical systems, Proc. Nat. Acad. Sci. U.S.A. 53 (1965), 8–12. MR 176866, DOI 10.1073/pnas.53.1.8
Harold J. Kushner, Stochastic stability and control, Mathematics in Science and Engineering, Vol. 33, Academic Press, New York-London, 1967. MR 216894
Harold J. Kushner and G. George Yin, Stochastic approximation and recursive algorithms and applications, 2nd ed., Applications of Mathematics (New York), vol. 35, Springer-Verlag, New York, 2003. Stochastic Modelling and Applied Probability. MR 1993642
M. Lefebvre, Applied stochastic processes, Springer Science & Business Media, 2007.
L. Lin, Y. Saad, and C. Yang, Approximating spectral densities of large matrices, SIAM Rev. 58 (2016), no. 1, 34–65., DOI 10.1137/130934283
Lin Lin and Chao Yang, Elliptic preconditioner for accelerating the self-consistent field iteration in Kohn-Sham density functional theory, SIAM J. Sci. Comput. 35 (2013), no. 5, S277–S298. MR 3120773, DOI 10.1137/120880604
M. A. Marques, A. Castro, G. F. Bertsch, and A. Rubio, octopus: a first-principles tool for excited electron–ion dynamics, Comp. Phys. Commun. 151 (2003), no. 1, 60–78., DOI 10.1016/S0010-4655(02)00686-0
R. M. Martin, Electronic Structure: Basic Theory and Practical Methods, Cambridge University Press, 2011.
Per-Gunnar Martinsson and Joel A. Tropp, Randomized numerical linear algebra: foundations and algorithms, Acta Numer. 29 (2020), 403–572. MR 4189294, DOI 10.1017/s0962492920000021
D. Marx and J. Hutter, Ab Initio Molecular Dynamics: Basic Theory and Advanced Methods, Cambridge University Press, 2009., DOI 10.1017/CBO9780511609633
Carl Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX) and a solutions manual (iv+171 pp.). MR 1777382, DOI 10.1137/1.9780898719512
M. A. Morales-Silva, K. D. Jordan, L. Shulenburger, and L. K. Wagner, Frontiers of Stochastic Electronic Structure Calculations, AIP Publishing LLC, 2021., DOI 10.1063/5.0053674
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč, Sarah: A novel method for machine learning problems using stochastic recursive gradient, International conference on machine learning, 2017, pp. 2613–2621.
J. R. Norris, Markov chains, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 2, Cambridge University Press, Cambridge, 1998. Reprint of 1997 original. MR 1600720
R. G. Parr and W. Yang, Density-Functional Theory of Atoms and Molecules, Oxford University Press, 1995., DOI 10.1093/oso/9780195092769.001.0001
M. C. Payne, M. P. Teter, D. C. Allan, T. A. Arias, and J. D. Joannopoulos, Iterative minimization techniques for ab initio total-energy calculations: molecular dynamics and conjugate gradients, Rev. Mod. Phys. 64 (1992), no. 4, 1045., DOI 10.1103/RevModPhys.64.1045
S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola, Stochastic Variance Reduction for Nonconvex Optimization, International Conference on Machine Learning, 2016, pp. 314–323.
Sidney I. Resnick, A probability path, Modern Birkhäuser Classics, Birkhäuser/Springer, New York, 2014. Reprint of the fifth (2005) printing of the 1999 original [MR1664717]. MR 3135152, DOI 10.1007/978-0-8176-8409-9
P. J. Reynolds, D. M. Ceperley, B. J. Alder, and W. A. Lester Jr, Fixed-node quantum Monte Carlo for molecules, J. Chem. Phys. 77 (1982), no. 11, 5593–5603., DOI 10.1063/1.443766
Herbert Robbins and Sutton Monro, A stochastic approximation method, Ann. Math. Statistics 22 (1951), 400–407. MR 42668, DOI 10.1214/aoms/1177729586
Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 29 (1992), no. 1, 209–228. MR 1149094, DOI 10.1137/0729014
J. M. Soler, E. Artacho, J. D. Gale, A. García, J. Junquera, P. Ordejón, and D. Sánchez-Portal, The SIESTA method for ab initio order-N materials simulation, J. Phys. 14 (2002), no. 11, 2745.
Phanish Suryanarayana, Vikram Gavini, Thomas Blesgen, Kaushik Bhattacharya, and Michael Ortiz, Non-periodic finite-element formulation of Kohn-Sham density functional theory, J. Mech. Phys. Solids 58 (2010), no. 2, 256–280. MR 2649224, DOI 10.1016/j.jmps.2009.10.002
Kyle Thicke, Accelerating the Computation of Density Functional Theory’s Correlation Energy under Random Phase Approximations, ProQuest LLC, Ann Arbor, MI, 2019. Thesis (Ph.D.)–Duke University. MR 4035466
Alex Toth, J. Austin Ellis, Tom Evans, Steven Hamilton, C. T. Kelley, Roger Pawlowski, and Stuart Slattery, Local improvement results for Anderson acceleration with inaccurate function evaluations, SIAM J. Sci. Comput. 39 (2017), no. 5, S47–S65. MR 3716569, DOI 10.1137/16M1080677
Alex Toth and C. T. Kelley, Convergence analysis for Anderson acceleration, SIAM J. Numer. Anal. 53 (2015), no. 2, 805–819. MR 3324976, DOI 10.1137/130919398
L. N. Trefethen, Approximation theory and approximation practice, extended edition, SIAM, 2019., DOI 10.1137/1.9781611975949
M. E. Tuckerman, Ab initio molecular dynamics: basic concepts, current trends and novel applications, J. Phys. 14 (2002), no. 50, R1297.
Weinan E and Jianfeng Lu, Electronic structure of smoothly deformed crystals: Cauchy-Born rule for the nonlinear tight-binding model, Comm. Pure Appl. Math. 63 (2010), no. 11, 1432–1468. MR 2683390, DOI 10.1002/cpa.20330
David Williams, Probability with martingales, Cambridge Mathematical Textbooks, Cambridge University Press, Cambridge, 1991. MR 1155402, DOI 10.1017/CBO9780511813658
J. Wolfowitz, On the stochastic approximation method of Robbins and Monro, Ann. Math. Statistics 23 (1952), 457–461. MR 50242, DOI 10.1214/aoms/1177729391
Yuanzhe Xi, Ruipeng Li, and Yousef Saad, Fast computation of spectral densities for generalized eigenvalue problems, SIAM J. Sci. Comput. 40 (2018), no. 4, A2749–A2773. MR 3849124, DOI 10.1137/17M1135542
Chao Yang, Juan C. Meza, and Lin-Wang Wang, A constrained optimization algorithm for total energy minimization in electronic structure calculations, J. Comput. Phys. 217 (2006), no. 2, 709–721. MR 2260621, DOI 10.1016/j.jcp.2006.01.030
Xin Zhang, Jinwei Zhu, Zaiwen Wen, and Aihui Zhou, Gradient type optimization methods for electronic structure calculations, SIAM J. Sci. Comput. 36 (2014), no. 3, C265–C289. MR 3200427, DOI 10.1137/130932934
Y. Zhou, Y. Saad, M. L. Tiago, and J. R. Chelikowsky, Self-consistent-field calculations using chebyshev-filtered subspace iteration, J. Comput. Phys. 219 (2006), no. 1, 172–184., DOI 10.1016/j.jcp.2006.03.017