A sparse interpolation algorithm for dynamical simulations in computational chemistry. (English) Zbl 1325.65194
Summary: In this paper we present a new implementation of Smolyak’s sparse grid interpolation algorithm designed for dynamical simulations. The implementation is motivated by an application to quantum chemistry where the goal is to simulate photo-induced molecular transformations. A molecule conforms to a geometry that minimizes its potential energy, and many molecules have multiple potential energy minima. These geometries correspond to local minima of the molecule’s potential energy surface, and one can simulate how a molecule transitions from one geometry to another by following the steepest descent path, or reaction path, on potential energy surfaces. Molecular vibrations and thermal fluctuations cause randomness in dynamics, so one must follow several paths simultaneously to more accurately simulate possible reaction paths. Current algorithms for reaction path following are too computationally burdensome for molecules of moderate size, but Smolyak’s interpolation algorithm offers a cheap surrogate for potential energy surfaces. While current implementations of Smolyak’s algorithm are not designed to simultaneously follow multiple reaction paths efficiently, our implementation of Smolyak’s algorithm achieves this efficiency by recursively defining Lagrange basis polynomials and making use of an efficient reformulation of Smolyak’s algorithm. In this paper we describe our new implementation of Smolyak’s algorithm and compare performance times to MATLAB’s Sparse Grid Interpolation Toolbox to demonstrate its computational savings. We also present dynamical simulations for the photoisomerization of 2-butene as an example of our reaction path following method.
MSC:
| 65Y20 | Complexity and performance of numerical algorithms |
| 92-08 | Computational methods for problems pertaining to biology |
| 92E99 | Chemistry |
Software:
Sparse Grid Interpolation; ode45; Fastsg; GAUSSIAN; Newton-X; Matlab; MATLAB ODE suite; Spinterp; Ode15s; ode23s; ode113; ode23References:
| [1] | M. Barbatti, M. Ruckenbauer, F. Plasser, J. Pittner, G. Granucci, M. Persico, and H. Lischka, {\it Newton-X: A surface-hopping program for nonadiabatic molecular dynamics}, Wiley Interdiscip. Rev. Comput. Molec. Sci., 4 (2014), pp. 26-33. |
| [2] | V. Barthelmann, E. Novak, and K. Ritter, {\it High dimensional polynomial interpolation on sparse grids}, Adv. Comput. Math., 12 (2000), pp. 273-288. · Zbl 0944.41001 |
| [3] | T. Beringhelli, A. Gavezzotti, and M. Simonetta, {\it Semi-empirical calculations on the thermal cis-trans isomerization of 2-butene, 2-pentene, beta-methylstyrene and stilbene}, J. Mol. Struct., 12 (1972), pp. 333-342. |
| [4] | A. B. Birkholz and H. B. Schlegel, {\it Coordinate reduction for exploring chemical reaction paths}, Theor. Chem. Acc., 131 (2012), 1170. |
| [5] | S. M. Blinder, {\it Basic concepts of self-consistent-field theory}, Amer. J. Phys., 33 (1965), pp. 431-443. |
| [6] | J. M. Bofill, W. Quapp, and M. Caballero, {\it Locating transition states on potential energy surfaces by the gentlest ascent dynamics}, Chem. Phys. Lett., 583 (2013), pp. 203-208. |
| [7] | H.-J. Bungartz and M. Griebel, {\it Sparse Grids}, Acta Numer. 13, Cambridge University Press, Cambridge, UK, 2004. |
| [8] | H.-J. Bungartz, A. Heinecke, D. Pflüger, and S. Schraufstetter, {\it Option pricing with a direct adaptive sparse grid approach}, J. Comput. Appl. Math., 236 (2012), pp. 3741-3750. · Zbl 1242.91184 |
| [9] | R. Courant, {\it Variational methods for the solution of problems of equilibrium and vibrations}, Bull. Amer. Math. Soc., 49 (1943), pp. 1-43. · Zbl 0063.00985 |
| [10] | M. J. Frisch, G. W. Trucks, H. B. Schlegel, G. E. Scuseria, M. A. Robb, J. R. Cheeseman, G. Scalmani, V. Barone, B. Mennucci, G. A. Petersson, H. Nakatsuji, M. Caricato, X. Li, H. P. Hratchian, A. F. Izmaylov, J. Bloino, G. Zheng, J. L. Sonnenberg, M. Hada, M. Ehara, K. Toyota, R. Fukuda, J. Hasegawa, M. Ishida, T. Nakajima, Y. Honda, O. Kitao, H. Nakai, T. Vreven, J. A. Montgomery, Jr., J. E. Peralta, F. Ogliaro, M. Bearpark, J. J. Heyd, E. Brothers, K. N. Kudin, V. N. Staroverov, R. Kobayashi, J. Normand, K. Raghavachari, A. Rendell, J. C. Burant, S. S. Iyengar, J. Tomasi, M. Cossi, N. Rega, J. M. Millam, M. Klene, J. E. Knox, J. B. Cross, V. Bakken, C. Adamo, J. Jaramillo, R. Gomperts, R. E. Stratmann, O. Yazyev, A. J. Austin, R. Cammi, C. Pomelli, J. W. Ochterski, R. L. Martin, K. Morokuma, V. G. Zakrzewski, G. A. Voth, P. Salvador, J. J. Dannenberg, S. Dapprich, A. D. Daniels, Ö. Farkas, J. B. Foresman, J. V. Ortiz, J. Cioslowski, and D. J. Fox, {\it Gaussian 09, Revision \textupA.1}, software, 2009, available at http://www.gaussian.com/. |
| [11] | J. Garcke and M. Griebel, {\it Data mining with sparse grids using simplicial basis functions}, in Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’01, ACM, New York, 2001, pp. 87-96. |
| [12] | V. Gradinaru, {\it Fourier transform on sparse grids: Code design and the time dependent Schrödinger equation}, Computing, 80 (2007), pp. 1-22. · Zbl 1117.65137 |
| [13] | M. Griebel and V. Thurner, {\it The efficient solution of fluid dynamics problems by the combination technique}, Internat. J. Numer. Methods Heat Fluid Flow, 5 (1995), pp. 251-269. · Zbl 0824.76064 |
| [14] | P. Hohenberg and W. Kohn, {\it Inhomogeneous electron gas}, Phys. Rev., 136 (1964), pp. 864-871. |
| [15] | H. Jónsson, G. Mills, and K. W. Jacobsen, {\it Nudged elastic band method for finding minimum energy paths of transitions}, in Classical and Quantum Dynamics in Condensed Phase Simulations, Proceedings of the International School of Physics, B. J. Berne, D. F. Coker, and G. Cicotti, eds., World Scientific Publishing, Singapore, 1998, pp. 385-404. |
| [16] | K. L. Judd, L. Maliar, S. Maliar, and R. Valero, {\it Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain}, J. Econom. Dynam. Control, 44 (2014), pp. 92-123. · Zbl 1402.91368 |
| [17] | A. Klimke, {\it Efficient Construction of Hierarchical Polynomial Sparse Grid Interpolants Using the Fast Discrete Cosine Transform}, technical report, Berichte aus dem Institut fur Angewandte Analysis und Numerische Simulation, Universität Stuttgart, 2006. |
| [18] | A. Klimke, {\it Sparse Grid Interpolation Toolbox User’s Guide}, technical report, Berichte aus dem Institut fur Angewandte Analysis und Numerische Simulation, Universität Stuttgart, 2008. |
| [19] | A. Klimke and B. Wohlmuth, {\it Algorithm 847: Spinterp: Piecewise multilinear hierarchical sparse grid interpolation in MATLAB}, ACM Trans. Math. Softw., 31 (2005), pp. 561-579. · Zbl 1136.65308 |
| [20] | W. Koch and M. C. Holthausen, {\it A Chemist’s Guide to Density Functional Theory}, 2nd ed., Wiley-VCH, Weinheim, 2001. |
| [21] | W. Kohn and L. J. Sham, {\it Self-consistent equations including exchange and correlation effects}, Phys. Rev., 140 (1965), pp. A1133-A1138. |
| [22] | X.-L. Luo, C. T. Kelley, L.-Z. Liao, and H. W. Tam, {\it Combining trust-region techniques and Rosenbrock methods to compute stationary points}, J. Optim. Theory Appl., 140 (2009), pp. 265-286. · Zbl 1190.90213 |
| [23] | B. A. Malin, D. Krueger, and F. Kubler, {\it Solving the multi-country real business cycle model using a Smolyak-collocation method}, J. Econom. Dynam. Control, 35 (2011), pp. 229-239. · Zbl 1231.91366 |
| [24] | R. M. Minyaev, {\it Reaction path as a gradient line on a potential energy surface}, Int. J. Quantum Chem., 49 (1994), pp. 105-127. |
| [25] | D. S. Mokrauer, {\it Interpolatory Surrogate Models for Light-Induced Transition Dynamics}, Ph.D. thesis, Department of Mathematics, North Carolina State University, Raleigh, NC, 2012. |
| [26] | D. S. Mokrauer and C. T. Kelley, {\it Sparse interpolatory reduced-order models for simulation of light-induced molecular transformations}, Optim. Methods Softw., 29 (2014), pp. 264-273. · Zbl 1284.82010 |
| [27] | D. S. Mokrauer, C. T. Kelley, and A. Bykhovski, {\it Simulations of light-induced molecular transformations in multiple dimensions with incremental sparse surrogates}, J. Algorithms Comp. Tech., 6 (2012), pp. 577-592. |
| [28] | A. Murarasu, G. Buse, D. Pfluger, J. Weidendorfer, B. Arndt, A. Murarau, D. Püger, and A. Bode, {\it Fastsg: A fast routines library for sparse grids}, Proc. Comp. Sci., 9 (2012), pp. 354-363. |
| [29] | A. Murarasu, D. Pflüger, J. Weidendorfer, G. Buse, and D. Butnaru, {\it Compact data structure and scalable algorithms for the sparse grid technique}, in Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), ACM, New York, 2011, pp. 1-10. |
| [30] | J. Nance, E. Jakubikova, and C. T. Kelley, {\it Reaction path following with sparse interpolation}, J. Chem. Theory Comput., 10 (2014), pp. 2942-2949. |
| [31] | E. Novak, {\it High dimensional numerical problems}, Nonlinear Anal., 30 (1997), pp. 1439-1446. · Zbl 0890.65052 |
| [32] | E. Novak and K. Ritter, {\it Simple cubature formulas with high polynomial exactness}, Constructive Approx., 15 (1999), pp. 499-522. · Zbl 0942.41018 |
| [33] | I. J. Palmer, I. N. Ragazos, F. Bernardi, M. Olivucci, and M. A. Robb, {\it An MC-SCF study of the S1 and S2 photochemical reactions of benzene}, J. Am. Chem. Soc., 115 (1993), pp. 673-682. |
| [34] | D. Pflüger, {\it Spatially Adaptive Sparse Grids for High-Dimensional Problems}, Ph.D. thesis, Institut für Informatik, Technische Universität München, Munich, Germany, 2010. · Zbl 1200.65100 |
| [35] | C. C. J. Roothaan, {\it New developments in molecular orbital theory}, Rev. Modern Phys., 23 (1951), pp. 69-89. · Zbl 0045.28502 |
| [36] | H. B. Schlegel, {\it Optimization of equilibrium geometries and transition structures}, J. Comput. Chem., 3 (1982), pp. 214-218. |
| [37] | Ch. Schwab and R. A. Todor, {\it Sparse finite elements for stochastic elliptic problems–Higher order moments}, Computing, 71 (2003), pp. 43-63. · Zbl 1044.65006 |
| [38] | L. F. Shampine and M. W. Reichelt, {\it The MATLAB ODE suite}, SIAM J. Sci. Comput., 18 (1997), pp. 1-22. · Zbl 0868.65040 |
| [39] | D. Sheppard, R. Terrell, and G. Henkelman, {\it Optimization methods for finding minimum energy paths}, J. Chem. Phys., 128 (2008), pp. 1-10. |
| [40] | S. Smolyak, {\it Quadrature and interpolation formulas for tensor products of certain classes of functions}, Soviet Math. Dokl., 4 (1963), pp. 240-243. · Zbl 0202.39901 |
| [41] | J. C. Tully, {\it Molecular dynamics with electronic transitions}, J. Chem. Phys., 93 (1990), pp. 1061-1071. |
| [42] | G. W. Wasilkowski and H. Wozniakowski, {\it Explicit cost bounds of algorithms for multivariate tensor product problems}, J. Complexity, 11 (1995), pp. 1-56. · Zbl 0819.65082 |
| [43] | D. L. Woolard, E. R. Brown, M. Pepper, M. Kemp, and R. Brown, {\it Terahertz frequency sensing and imaging: A time of reckoning future applications?}, Proc. IEEE, 93 (2005), pp. 1722-1743. |
| [44] | D. Xiu, {\it Efficient collocational approach for parametric uncertainty analysis}, Comm. Comput. Phys., 2 (2007), pp. 293-309. · Zbl 1164.65302 |
| [45] | C. Zenger, {\it Sparse grids}, in Notes Numer. Fluid Mech. 31, Vieweg, Braunschweig, Germany, 1991, pp. 241-251. · Zbl 0763.65091 |
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.
