×

Convergence analysis of adaptive DIIS algorithms with application to electronic ground state calculations. (English) Zbl 1492.65008

Summary: This paper deals with a general class of algorithms for the solution of fixed-point problems that we refer to as Anderson-Pulay acceleration. This family includes the DIIS technique and its variant sometimes called commutator-DIIS, both introduced by Pulay in the 1980s to accelerate the convergence of self-consistent field procedures in quantum chemistry, as well as the related Anderson acceleration which dates back to the 1960s, and the wealth of techniques they have inspired. Such methods aim at accelerating the convergence of any fixed-point iteration method by combining several iterates in order to generate the next one at each step. This extrapolation process is characterised by its depth, i.e. the number of previous iterates stored, which is a crucial parameter for the efficiency of the method. It is generally fixed to an empirical value. In the present work, we consider two parameter-driven mechanisms to let the depth vary along the iterations. In the first one, the depth grows until a certain nondegeneracy condition is no longer satisfied; then the stored iterates (save for the last one) are discarded and the method “restarts”. In the second one, we adapt the depth continuously by eliminating at each step some of the oldest, less relevant, iterates. In an abstract and general setting, we prove under natural assumptions the local convergence and acceleration of these two adaptive Anderson-Pulay methods, and we show that one can theoretically achieve a superlinear convergence rate with each of them. We then investigate their behaviour in quantum chemistry calculations. These numerical experiments show that both adaptive variants exhibit a faster convergence than a standard fixed-depth scheme, and require on average less computational effort per iteration. This study is complemented by a review of known facts on the DIIS, in particular its link with the Anderson acceleration and some multisecant-type quasi-Newton methods.

MSC:

65B99 Acceleration of convergence in numerical analysis
65H10 Numerical computation of solutions to systems of equations
65Z05 Applications to the sciences
81-08 Computational methods for problems pertaining to quantum theory
90C53 Methods of quasi-Newton type

Software:

Anderson; NKA; PySCF
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. An, X. Jia and H.F. Walker, Anderson acceleration and application to the three-temperature energy equations. J. Comput. Phys. 347 (2017) 1-19. · Zbl 1380.65092
[2] A. Anantharaman and E. Cancès, Existence of minimizers for Kohn-Sham models in quantum chemistry. Ann. Inst. H. Poincaré Anal. Non Linéaire 26 (2009) 2425-2455. · Zbl 1186.81138 · doi:10.1016/j.anihpc.2009.06.003
[3] D.G. Anderson, Iterative procedures for nonlinear integral equations. J. ACM 12 (1965) 547-560. · Zbl 0149.11503
[4] D.G.M. Anderson, Comments on “Anderson acceleration, mixing and extrapolation’’. Numer. Algorithms 80 (2019) 135-234. · Zbl 1477.65010
[5] 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.
[6] A.D. Becke, Density-functional exchange-energy approximation with correct asymptotic behavior. Phys. Rev. A 38 (1988) 3098-3100.
[7] C. Brezinski, M. Redivo-Zaglia and Y. Saad, Shanks sequence transformations and Anderson acceleration. SIAM Rev. 60 (2018) 646-669. · Zbl 1395.65001
[8] C.G. Broyden, A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19 (1965) 577-593. · Zbl 0131.13905
[9] M.T. Calef, E.D. Fichtl, J.S. Warsa, M. Berndt and N.N. Carlson, Nonlinear Krylov acceleration applied to a discrete ordinates formulation of the k-eigenvalue problem. J. Comput. Phys. 238 (2013) 188-209. · Zbl 1286.65048
[10] E. Cancès and C. Le Bris, Can we outperform the DIIS approach for electronic structure calculations?. Int. J. Quantum Chem. 79 (2000) 82-90.
[11] E. Cancès and C. Le Bris, On the convergence of SCF algorithms for the Hartree-Fock equations. ESAIM: M2AN 34 (2000) 749-774. · Zbl 1090.65548
[12] N.N. Carlson and K. Miller, Design and application of a gradient-weighted moving finite element code I: in one dimension. SIAM J. Sci. Comput. 19 (1998) 728-765. · Zbl 0911.65087
[13] X. Chen and C.T. Kelley, Convergence of the EDIIS algorithm for nonlinear equations. SIAM J. Sci. Comput. 41 (2019) A365-A379. · Zbl 1408.65030
[14] P. Császár and P. Pulay, Geometry optimization by direct inversion in the iterative subspace. J. Mol. Struct. 114 (1984) 31-34.
[15] H. De Sterck, A nonlinear GMRES optimization algorithm for canonical tensor decomposition. SIAM J. Sci. Comput. 34 (2012) A1351-A1379. · Zbl 1253.15035
[16] E. De Sturler, Truncation strategies for optimal Krylov subspace methods. SIAM J. Numer. Anal. 36 (1999) 864-889. · Zbl 0960.65031
[17] V. Eckert, P. Pulay and H.-J. Werner, Ab initio geometry optimization for large molecules. J. Comput. Chem. 18 (1997) 1473-1483.
[18] C. Evans, S. Pollock, L.G. Rebholz and M. Xiao, A proof that Anderson acceleration increases the convergence rate in linearly converging fixed point methods (but not in quadratically converging ones). SIAM J. Numer. Anal. 58 (2020) 788-810. · Zbl 1433.65102
[19] V. Eyert, A comparative study on methods for convergence acceleration of iterative vector sequences. J. Comput. Phys. 124 (1996) 271-285. · Zbl 0851.65003
[20] H.-R. Fang and Y. Saad, Two classes of multisecant methods for nonlinear acceleration. Numer. Linear Algebra Appl. 16 (2009) 197-221. · Zbl 1224.65134
[21] J.-L. Fattebert, Accelerated block preconditioned gradient method for large scale wave functions calculations in density functional theory. J. Comput. Phys. 229 (2010) 441-452. · Zbl 1183.82004
[22] V. Fock, Näherungsmethode zur Lösung des quantenmechanischen Mehrkörperproblems. Z. Phys. 61 (1930) 126-148. · JFM 56.1313.08
[23] V. Ganine, N.J. Hills and B.L. Lapworth, Nonlinear acceleration of coupled fluid-structure transient thermal problems by Anderson mixing. Int. J. Numer. Methods Fluids 71 (2013) 939-959. · Zbl 1430.74037
[24] A.J. Garza and G.E. Scuseria, Comparison of self-consistent field convergence acceleration techniques. J. Chem. Phys. 137 (2012) 054110.
[25] D.M. Gay and R.B. Schnabel, Solving systems of nonlinear equations by Broyden’s method with projected updates. Working Paper 169, National Bureau of Economic Research (1977). · Zbl 0464.65024
[26] A. Greenbaum, V. Pták and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES. SIAM. J. Matrix Anal. Appl. 17 (1996) 465-469. · Zbl 0857.65029
[27] A. Griewank, Broyden updating, the good and the bad! Documenta Math. Extra Volume: Optimization Stories. (2012) 301-315. · Zbl 1264.65078
[28] R. Haelterman, J. Degroote, D. Van Heule and J. Vierendeels, On the similarities between the quasi-Newton inverse least squares method and GMRES. SIAM J. Numer. Anal. 47 (2010) 4660-4679. · Zbl 1209.65048
[29] G.G. Hall, The molecular orbital theory of chemical valency. VIII. A method of calculating ionization potentials. Proc. Roy. Soc. London Ser. A 205 (1951) 541-552. · Zbl 0040.28402
[30] D.R. Hartree, The wave mechanics of an atom with a non-Coulomb central field. Part I. Theory and methods. Math. Proc. Cambridge Philos. Soc. 24 (1928) 89-110. · JFM 54.0966.05
[31] N.C. Henderson and R. Varadhan, Damped Anderson acceleration with restarts and monotonicity control for accelerating EM and EM-like algorithms. J. Comput. Graph. Stat. 28 (2019) 834-846. · Zbl 07499030
[32] N.J. Higham and N. Strabić, Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numer. Algorithms 72 (2016) 1021-1042. · Zbl 1347.65074
[33] P. Hohenberg and W. Kohn, Inhomogeneous electron gas. Phys. Rev. 136 (1964) B864-B871.
[34] X. Hu and W. Yang, Accelerating self-consistent field convergence with the augmented Roothaan-Hall energy function. J. Chem. Phys. 132 (2010) 054109.
[35] M. Kawata, C.M. Cortis and R.A. Friesner, Efficient recursive implementation of the modified Broyden method and the direct inversion in the iterative subspace method: acceleration of self-consistent calculations. J. Chem. Phys. 108 (1998) 4426-4438.
[36] W. Kohn and L.J. Sham, Self-consistent equations including exchange and correlation effects. Phys. Rev. 140 (1965) A1133-A1138.
[37] K.N. Kudin and G.E. Scuseria, Converging self-consistent field equations in quantum chemistry - Recent achievements and remaining challenges. ESAIM: M2AN 41 (2007) 281-296. · Zbl 1135.81381
[38] K.N. Kudin, G.E. Scuseria and E. Cancès, A black-box self-consistent field convergence algorithm: one step closer. J. Chem. Phys. 116 (2002) 8255-8261.
[39] C. Lee, W. Yang and R.G. Parr, Development of the Colle-Salvetti correlation-energy formula into a functional of the electron density. Phys. Rev. B 37 (1988) 785-789.
[40] P.A. Lott, H.F. Walker, C.S. Woodward and U.M. Yang, An accelerated Picard method for nonlinear systems related to variably saturated flow. Adv. Water Res. 38 (2012) 92-101. · doi:10.1016/j.advwatres.2011.12.013
[41] J. Nocedal and S.J. Wright, Numerical Optimization, 2nd edition. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York (2006). · Zbl 1104.65059
[42] A.L. Pavlov, G.W. Ovchinnikov, D.Y. Derbyshev, D. Tsetserukou and I.V. Oseledets, AA-ICP: iterative closest point with Anderson acceleration. In: 2018 IEEE International Conference on Robotics and Automation (ICRA) (2018) 3407-3412.
[43] F.A. Potra, On Q-order and R-order of convergence. J. Optim. Theory Appl. 63 (1989) 415-431. · Zbl 0663.65049
[44] F.A. Potra and H. Engler, A characterization of the behavior of the Anderson acceleration on linear problems. Linear Algebra Appl. 438 (2013) 393-398. · Zbl 1263.65036
[45] P.P. Pratapa and P. Suryanarayana, Restarted Pulay mixing for efficient and robust acceleration of fixed-point iterations. Chem. Phys. Lett. 635 (2015) 69-74.
[46] P. Pulay, Convergence acceleration of iterative sequences. The case of SCF iteration. Chem. Phys. Lett. 73 (1980) 393-398.
[47] P. Pulay, Improved SCF convergence acceleration. J. Comput. Chem. 3 (1982) 556-560.
[48] T. Rohwedder and R. Schneider, An analysis for the DIIS acceleration method used in quantum chemistry calculations. J. Math. Chem. 49 (2011) 1889-1914. · Zbl 1252.81135
[49] C.C.J. Roothaan, New developments in molecular orbital theory. Rev. Modern Phys. 23 (1951) 69-89. · Zbl 0045.28502
[50] Y. Saad and M.H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7 (1986) 856-869. · Zbl 0599.65018
[51] H. Sellers, The C^2-DIIS convergence acceleration algorithm. Int. J. Quantum Chem. 45 (1993) 31-41.
[52] H. Shepard and M. Minkoff, Some comments on the DIIS method. Mol. Phys. 105 (2007) 2839-2848.
[53] M. Spivak, A Comprehensive Introduction to Differential Geometry, 3rd edition. Vol. 1. Publish or Perish (1999). · Zbl 1213.53001
[54] Q. Sun, T.C. Berkelbach, N.S. Blunt, G.H. Booth, S. Guo, Z. Li, J. Liu, J.D. McClain, E.R. Sayfutyarova, S. Sharma, S. Wouters and G.K. Chan, PySCF: the Python-based simulations of chemistry framework. WIREs Comput. Mol. Sci. 8 (2017) e1340.
[55] L. Thøgersen, J. Olsen, A. Köhn, P. Jørgensen, P. Sałek and T. Helgaker, The trust-region self-consistent field method in Kohn-Sham density-functional theory. J. Chem. Phys. 123 (2005) 074103.
[56] A. Toth and C.T. Kelley, Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53 (2015) 805-819. · Zbl 1312.65083
[57] A. Toth, J.A. Ellis, T. Evans, S. Hamilton, C.T. Kelley, R. Pawlowski and S. Slattery, Local improvement results for Anderson acceleration with inaccurate function evaluations. SIAM J. Sci. Comput. 39 (2017) S47-S65. · Zbl 1422.65079
[58] H.F. Walker and P. Ni, Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49 (2011) 1715-1735. · Zbl 1254.65067
[59] Y.A. Wang, C.Y. Yam, Y.K. Chen and G. Chen, Linear-expansion shooting techniques for accelerating self-consistent field convergence. J. Chem. Phys. 134 (2011) 241103.
[60] T. Washio and C.W. Oosterlee, Krylov subspace acceleration for nonlinear multigrid schemes. Electron. Trans. Numer. Anal. 6 (1997) 271-290. · Zbl 0903.65096
[61] J. Willert, W.T. Taitano and D. Knoll, Leveraging Anderson acceleration for improved convergence of iterative solutions to transport systems. J. Comput. Phys. 273 (2014) 278-286. · Zbl 1351.82093
[62] D.M. Wood and A. Zunger, A new method for diagonalising large matrices. J. Phys. A Math. Gen. 18 (1985) 1343-1359. · Zbl 0615.65043
[63] Y.A. Zhang and Y.A. Wang, Perturbative total energy evaluation in self-consistent field iterations: tests on molecular systems. J. Chem. Phys. 130 (2009) 144116.
[64] J. Zhang, Y. Yao, Y. Peng, H. Yu and B. Deng, Fast K-Means clustering with Anderson acceleration. Preprint arXiv:1805.10638
[65] J. Zhang, B. O’Donoghue and S. Boyd, Globally convergent type-I Anderson acceleration for non-smooth fixed-point iterations. SIAM J. Optim. 30 (2020) 3170-3197. · Zbl 1525.47126
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.