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.
Keywords: Fixed-point iteration, Anderson acceleration, DIIS, nonlinear GMRES, quantum chemistry
@article{M2AN_2021__55_6_2785_0,
author = {Chupin, Maxime and Dupuy, Mi-Song and Legendre, Guillaume and S\'er\'e, \'Eric},
title = {Convergence analysis of adaptive {DIIS} algorithms with application to electronic ground state calculations},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {2785--2825},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {6},
doi = {10.1051/m2an/2021069},
mrnumber = {4344859},
language = {en},
url = {https://www.numdam.org/articles/10.1051/m2an/2021069/}
}
TY - JOUR AU - Chupin, Maxime AU - Dupuy, Mi-Song AU - Legendre, Guillaume AU - Séré, Éric TI - Convergence analysis of adaptive DIIS algorithms with application to electronic ground state calculations JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2021 SP - 2785 EP - 2825 VL - 55 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/m2an/2021069/ DO - 10.1051/m2an/2021069 LA - en ID - M2AN_2021__55_6_2785_0 ER -
%0 Journal Article %A Chupin, Maxime %A Dupuy, Mi-Song %A Legendre, Guillaume %A Séré, Éric %T Convergence analysis of adaptive DIIS algorithms with application to electronic ground state calculations %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2021 %P 2785-2825 %V 55 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/m2an/2021069/ %R 10.1051/m2an/2021069 %G en %F M2AN_2021__55_6_2785_0
Chupin, Maxime; Dupuy, Mi-Song; Legendre, Guillaume; Séré, Éric. Convergence analysis of adaptive DIIS algorithms with application to electronic ground state calculations. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 55 (2021) no. 6, pp. 2785-2825. doi: 10.1051/m2an/2021069
[1] , and , Anderson acceleration and application to the three-temperature energy equations. J. Comput. Phys. 347 (2017) 1–19. | MR | DOI
[2] and , Existence of minimizers for Kohn-Sham models in quantum chemistry. Ann. Inst. H. Poincaré Anal. Non Linéaire 26 (2009) 2425–2455. | MR | Zbl | Numdam | DOI
[3] , Iterative procedures for nonlinear integral equations. J. ACM 12 (1965) 547–560. | MR | Zbl | DOI
[4] , Comments on ``Anderson acceleration, mixing and extrapolation’’. Numer. Algorithms 80 (2019) 135–234. | MR | DOI
[5] , and , Periodic Pulay method for robust and efficient convergence acceleration of self-consistent field iterations. Chem. Phys. Lett. 647 (2016) 31–35. | DOI
[6] , Density-functional exchange-energy approximation with correct asymptotic behavior. Phys. Rev. A 38 (1988) 3098–3100. | DOI
[7] , and , Shanks sequence transformations and Anderson acceleration. SIAM Rev. 60 (2018) 646–669. | MR | DOI
[8] , A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19 (1965) 577–593. | MR | Zbl | DOI
[9] , , , and , Nonlinear Krylov acceleration applied to a discrete ordinates formulation of the -eigenvalue problem. J. Comput. Phys. 238 (2013) 188–209. | MR | Zbl | DOI
[10] and , Can we outperform the DIIS approach for electronic structure calculations?. Int. J. Quantum Chem. 79 (2000) 82–90. | DOI
[11] and , On the convergence of SCF algorithms for the Hartree-Fock equations. ESAIM: M2AN 34 (2000) 749–774. | MR | Zbl | Numdam | DOI
[12] and , Design and application of a gradient-weighted moving finite element code I: in one dimension. SIAM J. Sci. Comput. 19 (1998) 728–765. | MR | Zbl | DOI
[13] and , Convergence of the EDIIS algorithm for nonlinear equations. SIAM J. Sci. Comput. 41 (2019) A365–A379. | MR | DOI
[14] and , Geometry optimization by direct inversion in the iterative subspace. J. Mol. Struct. 114 (1984) 31–34. | DOI
[15] , A nonlinear GMRES optimization algorithm for canonical tensor decomposition. SIAM J. Sci. Comput. 34 (2012) A1351–A1379. | MR | Zbl | DOI
[16] , Truncation strategies for optimal Krylov subspace methods. SIAM J. Numer. Anal. 36 (1999) 864–889. | MR | Zbl | DOI
[17] , and , Ab initio geometry optimization for large molecules. J. Comput. Chem. 18 (1997) 1473–1483. | DOI
[18] , , and , 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. | MR | DOI
[19] , A comparative study on methods for convergence acceleration of iterative vector sequences. J. Comput. Phys. 124 (1996) 271–285. | MR | Zbl | DOI
[20] and , Two classes of multisecant methods for nonlinear acceleration. Numer. Linear Algebra Appl. 16 (2009) 197–221. | MR | Zbl | DOI
[21] , Accelerated block preconditioned gradient method for large scale wave functions calculations in density functional theory. J. Comput. Phys. 229 (2010) 441–452. | MR | Zbl | DOI
[22] , Näherungsmethode zur Lösung des quantenmechanischen Mehrkörperproblems. Z. Phys. 61 (1930) 126–148. | JFM | DOI
[23] , and , Nonlinear acceleration of coupled fluid-structure transient thermal problems by Anderson mixing. Int. J. Numer. Methods Fluids 71 (2013) 939–959. | MR | DOI
[24] and , Comparison of self-consistent field convergence acceleration techniques. J. Chem. Phys. 137 (2012) 054110. | DOI
[25] and , Solving systems of nonlinear equations by Broyden’s method with projected updates. Working Paper 169, National Bureau of Economic Research (1977). | MR | Zbl | DOI
[26] , and , Any nonincreasing convergence curve is possible for GMRES. SIAM. J. Matrix Anal. Appl. 17 (1996) 465–469. | MR | Zbl | DOI
[27] , Broyden updating, the good and the bad! Documenta Math. Extra Volume: Optimization Stories. (2012) 301–315. | MR | Zbl
[28] , , and , On the similarities between the quasi-Newton inverse least squares method and GMRES. SIAM J. Numer. Anal. 47 (2010) 4660–4679. | MR | Zbl | DOI
[29] , 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
[30] , 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 | DOI
[31] and , Damped Anderson acceleration with restarts and monotonicity control for accelerating EM and EM-like algorithms. J. Comput. Graph. Stat. 28 (2019) 834–846. | MR | DOI
[32] and , Anderson acceleration of the alternating projections method for computing the nearest correlation matrix. Numer. Algorithms 72 (2016) 1021–1042. | MR | DOI
[33] and , Inhomogeneous electron gas. Phys. Rev. 136 (1964) B864–B871. | MR | DOI
[34] and , Accelerating self-consistent field convergence with the augmented Roothaan-Hall energy function. J. Chem. Phys. 132 (2010) 054109. | DOI
[35] , and , 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. | DOI
[36] and , Self-consistent equations including exchange and correlation effects. Phys. Rev. 140 (1965) A1133–A1138. | MR | DOI
[37] and , Converging self-consistent field equations in quantum chemistry – Recent achievements and remaining challenges. ESAIM: M2AN 41 (2007) 281–296. | MR | Zbl | Numdam | DOI
[38] , and , A black-box self-consistent field convergence algorithm: one step closer. J. Chem. Phys. 116 (2002) 8255–8261. | DOI
[39] , and , Development of the Colle-Salvetti correlation-energy formula into a functional of the electron density. Phys. Rev. B 37 (1988) 785–789. | DOI
[40] , , and , An accelerated Picard method for nonlinear systems related to variably saturated flow. Adv. Water Res. 38 (2012) 92–101. | DOI
[41] and , Numerical Optimization, 2nd edition. Springer Series in Operations Research and Financial Engineering. Springer-Verlag, New York (2006). | MR | Zbl
[42] , , , and , AA-ICP: iterative closest point with Anderson acceleration. In: 2018 IEEE International Conference on Robotics and Automation (ICRA) (2018) 3407–3412. | DOI
[43] , On -order and -order of convergence. J. Optim. Theory Appl. 63 (1989) 415–431. | MR | Zbl | DOI
[44] and , A characterization of the behavior of the Anderson acceleration on linear problems. Linear Algebra Appl. 438 (2013) 393–398. | MR | Zbl | DOI
[45] and , Restarted Pulay mixing for efficient and robust acceleration of fixed-point iterations. Chem. Phys. Lett. 635 (2015) 69–74. | DOI
[46] , Convergence acceleration of iterative sequences. The case of SCF iteration. Chem. Phys. Lett. 73 (1980) 393–398. | DOI
[47] , Improved SCF convergence acceleration. J. Comput. Chem. 3 (1982) 556–560. | DOI
[48] and , An analysis for the DIIS acceleration method used in quantum chemistry calculations. J. Math. Chem. 49 (2011) 1889–1914. | MR | Zbl | DOI
[49] , New developments in molecular orbital theory. Rev. Modern Phys. 23 (1951) 69–89. | Zbl | DOI
[50] and , GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7 (1986) 856–869. | MR | Zbl | DOI
[51] , The C2-DIIS convergence acceleration algorithm. Int. J. Quantum Chem. 45 (1993) 31–41. | DOI
[52] and , Some comments on the DIIS method. Mol. Phys. 105 (2007) 2839–2848. | DOI
[53] , A Comprehensive Introduction to Differential Geometry, 3rd edition. Vol. 1. Publish or Perish (1999). | Zbl | MR
[54] , , , , , , , , , , and , PySCF: the Python-based simulations of chemistry framework. WIREs Comput. Mol. Sci. 8 (2017) e1340. | DOI
[55] , , , , and , The trust-region self-consistent field method in Kohn-Sham density-functional theory. J. Chem. Phys. 123 (2005) 074103. | DOI
[56] and , Convergence analysis for Anderson acceleration. SIAM J. Numer. Anal. 53 (2015) 805–819. | MR | Zbl | DOI
[57] , , , , , and , Local improvement results for Anderson acceleration with inaccurate function evaluations. SIAM J. Sci. Comput. 39 (2017) S47–S65. | MR | Zbl | DOI
[58] and , Anderson acceleration for fixed-point iterations. SIAM J. Numer. Anal. 49 (2011) 1715–1735. | MR | Zbl | DOI
[59] , , and , Linear-expansion shooting techniques for accelerating self-consistent field convergence. J. Chem. Phys. 134 (2011) 241103. | DOI
[60] and , Krylov subspace acceleration for nonlinear multigrid schemes. Electron. Trans. Numer. Anal. 6 (1997) 271–290. | MR | Zbl
[61] , and , Leveraging Anderson acceleration for improved convergence of iterative solutions to transport systems. J. Comput. Phys. 273 (2014) 278–286. | Zbl | DOI
[62] and , A new method for diagonalising large matrices. J. Phys. A Math. Gen. 18 (1985) 1343–1359. | MR | Zbl | DOI
[63] and , Perturbative total energy evaluation in self-consistent field iterations: tests on molecular systems. J. Chem. Phys. 130 (2009) 144116. | DOI
[64] , , , and , Fast K-Means clustering with Anderson acceleration. Preprint [cs.LG] (2018). | arXiv
[65] , and , Globally convergent type-I Anderson acceleration for non-smooth fixed-point iterations. SIAM J. Optim. 30 (2020) 3170–3197. | MR | Zbl | DOI
Cité par Sources :
