Sparse grids for the Schrödinger equation

Griebel, Michael; Hamaekers, Jan

ESAIM: Modélisation mathématique et analyse numérique, Special issue on Molecular Modelling, Tome 41 (2007) no. 2, pp. 215-247.

We present a sparse grid/hyperbolic cross discretization for many-particle problems. It involves the tensor product of a one-particle multilevel basis. Subsequent truncation of the associated series expansion then results in a sparse grid discretization. Here, depending on the norms involved, different variants of sparse grid techniques for many-particle spaces can be derived that, in the best case, result in complexities and error estimates which are independent of the number of particles. Furthermore we introduce an additional constraint which gives antisymmetric sparse grids which are suited to fermionic systems. We apply the antisymmetric sparse grid discretization to the electronic Schrödinger equation and compare costs, accuracy, convergence rates and scalability with respect to the number of electrons present in the system.

[1] E. Ackad and M. Horbatsch, Numerical solution of the Dirac equation by a mapped Fourier grid method. J. Phys. A: Math. General 38 (2005) 3157-3171. | Zbl

[2] R.A. Adams, Sobolev spaces. Academic Press, New York (1975). | MR | Zbl

[3] A. Arnold, Mathematical concepts of open quantum boundary conditions. Transport Theory Statist. Phys. 30 (2001) 561-584. | Zbl

[4] P.W. Atkins and R.S. Friedman, Molecular quantum mechanics. Oxford University Press, Oxford (1997).

[5] K.I. Babenko, Approximation by trigonometric polynomials in a certain class of periodic functions of several variables. Dokl. Akad. Nauk SSSR 132 (1960) 672-675. | Zbl

[6] S. Balay, K. Buschelman, V. Eijkhout, W.D. Gropp, D. Kaushik, M.G. Knepley, L.C. Mcinnes, B.F. Smith and H. Zhang, PETSc users manual. Tech. Report ANL-95/11 - Revision 2.1.5, Argonne National Laboratory (2004).

[7] R. Bellmann, Adaptive control processes: A guided tour. Princeton University Press (1961). | MR | Zbl

[8] J. Boyd, Chebyshev and Fourier spectral methods. Dover Publications, New York (2000). | MR | Zbl

[9] H. Bungartz, Dünne Gitter und deren Anwendung bei der adaptiven Lösung der dreidimensionalen Poisson-Gleichung. Dissertation, Institut für Informatik, TU München (1992).

[10] H. Bungartz, Finite elements of higher order on sparse grids. Habilitationsschrift, Institut für Informatik, TU München and Shaker Verlag, Aachen (1998).

[11] H. Bungartz and M. Griebel, A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives. J. Complexity 15 (1999) 167-199. | Zbl

[12] H. Bungartz and M. Griebel, Sparse grids. Acta Numer. 13 (2004) 147-269. | Zbl

[13] Z. Cai, J. Mandel and S. Mccormick, Multigrid methods for nearly singular linear equations and eigenvalue problems. SIAM J. Numer. Anal. 34 (1997) 178-200. | Zbl

[14] T. Chan and I. Sharapov, Subspace correction multi-level methods for elliptic eigenvalue problems. Numer. Linear Algebra Appl. 9 (2002) 1-20. | Zbl

[15] C. Chui and Y. Wang, A general framework for compactly supported splines and wavelets. J. Approx. Theory 71 (1992) 263-304. | Zbl

[16] A. Cohen, Numerical analysis of wavelet methods, Studies in Mathematics and its Applications 32. North Holland (2003). | MR | Zbl

[17] E. Condon, The theory of complex spectra. Phys. Rev. 36 (1930) 1121-1133. | JFM

[18] I. Daubechies, Ten lectures on wavelets. CBMS-NSF Regional Conf. Series in Appl. Math. 61, SIAM (1992). | MR | Zbl

[19] G. Deslauriers and S. Dubuc, Symmetric iterative interpolation processes. Constr. Approx. 5 (1989) 49-68. | Zbl

[20] R. Devore, S. Konyagin and V. Temlyakov, Hyperbolic wavelet approximation. Constr. Approx. 14 (1998) 1-26. | Zbl

[21] N. Dobrovol'Skii and A. Roshchenya, Number of lattice points in the hyperbolic cross. Math. Notes 11 (1998) 319-324. | Zbl

[22] D. Donoho and P. Yu, Deslauriers-Dubuc: Ten years after, CRM Proceedings and Lecture Notes 18, G. Deslauriers and S. Dubuc Eds. (1999). | Zbl

[23] P. Ewald, Die Berechnung optischer und elektrostatischer Gitterpotentiale. Ann. Phys. 64 (1921) 253-287. | JFM

[24] E. Fattal, R. Baer and R. Kosloff, Phase space approach for optimizing grid representations: the mapped Fourier method. Phys. Rev. E 53 (1996) 1217-1227.

[25] T. Fevens and H. Jiang, Absorbing boundary conditions for the Schrödinger equation. SIAM J. Scientific Comput. 21 (1999) 255-282. | Zbl

[26] R. Feynman, There's plenty of room at the bottom: An invitation to enter a new world of physics. Engineering and Science XXIII, Feb. issue (1960), http://www.zyvex.com/nanotech/feynman.html.

[27] H.-J. Flad, W. Hackbusch, D. Kolb and R. Schneider, Wavelet approximation of correlated wavefunctions. I. Basics., J. Chem. Phys. 116 (2002) 9641-9857.

[28] H.-J. Flad, W. Hackbusch and R. Schneider, Best N term approximation in electronic structure calculations. I. One electron reduced density matrix. Tech. Report 05-9, Berichtsreihe des Mathematischen Seminars der Universität Kiel (2005).

[29] H. Fliegl, W. Klopper and C. Hättig, Coupled-cluster theory with simplified linear-r12 corrections: The CCSD(R12) model. J. Chem. Phys. 122 (2005) 084107.

[30] S. Fournais, M. Hoffmann-Ostenhof, T. Hoffmann-Ostenhof and T. Sørensen, The electron density is smooth away from the nuclei. Commun. Math. Phys. 228 (2002) 401-415. | Zbl

[31] S. Fournais, M. Hoffmann-Ostenhof, T. Hoffmann-Ostenhof and T. Sørensen, Sharp regularity results for Coulombic many-electron wave functions. Commun. Math. Phys. 255 (2005) 183-227. | Zbl

[32] K. Frank, S. Heinrich and S. Pereverzev, Information complexity of multivariate Fredholm equations in Sobolev classes. J. Complexity 12 (1996) 17-34. | Zbl

[33] G. Friesecke, The configuraton-interaction equations for atoms and molecules: Charge quantization and existence of solutions. Preprint, June 28, 1999, Mathematical Insitute, University of Oxford, UK.

[34] J. Garcke and M. Griebel, On the computation of the eigenproblems of hydrogen and helium in strong magnetic and electric fields with the sparse grid combination technique. J. Comput. Phys. 165 (2000) 694-716. | Zbl

[35] T. Gerstner and M. Griebel, Numerical integration using sparse grids. Numer. Algorithms 18 (1998) 209-232. | Zbl

[36] T. Gerstner and M. Griebel, Dimension-adaptive tensor-product quadrature. Computing 71 (2003) 65-87. | Zbl

[37] M. Griebel, Multilevel algorithms considered as iterative methods on semidefinite systems. SIAM J. Sci. Stat. Comput. 15 (1994) 547-565. | Zbl

[38] M. Griebel, Sparse grids and related approximation schemes for higher dimensional problems, in Proceedings of the conference on Foundations of Computational Mathematics (FoCM05), Santander, Spain, 2005. | MR | Zbl

[39] M. Griebel and S. Knapek, Optimized tensor-product approximation spaces. Constr. Approx. 16 (2000) 525-540. | Zbl

[40] M. Griebel and P. Oswald, On additive Schwarz preconditioners for sparse grid discretizations. Numer. Math. 66 (1994) 449-463. | Zbl

[41] M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms. Numer. Math. 70 (1995) 161-180. | Zbl

[42] M. Griebel and P. Oswald, Tensor product type subspace splitting and multilevel iterative methods for anisotropic problems. Adv. Comput. Math. 4 (1995) 171-206. | Zbl

[43] M. Griebel, P. Oswald and T. Schiekofer, Sparse grids for boundary integral equations. Numer. Mathematik 83 (1999) 279-312. | Zbl

[44] F. Gygi, Adaptive Riemannian metric for plane-wave electronic-structure calculations. Europhys. Lett. 19 (1992) 617.

[45] F. Gygi, Electronic-structure calculations in adaptive coordinates. Phys. Rev. B 48 (1993) 11692.

[46] D. Hamann, Comparison of global and local adaptive coordinates for density-functional calculations. Phys. Rev. B 63 (2001) 075107.

[47] V. Hernandez, J. Roman and V. Vidal, SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems. ACM Trans. Math. Software 31 (2005) 351-362. | Zbl

[48] R. Hochmuth, Wavelet bases in numerical analysis and restricted nonlinear approximation. Habilitationsschrift, Freie Universität Berlin (1999).

[49] R. Hochmuth, S. Knapek and G. Zumbusch, Tensor products of Sobolev spaces and applications. Tech. Report 685, SFB 256, Univ. Bonn (2000).

[50] M. Hoffmann-Ostenhof, T. Hoffmann-Ostenhof and T. Sørensen, Electron wavefunction and densities for atoms. Ann. Henri Poincaré 2 (2001) 77-100. | Zbl

[51] G. Karniadakis and S. Sherwin, Spectral/hp element methods for CFD. Oxford University Press (1999). | MR | Zbl

[52] T. Kato, On the eigenfunctions of many-particle systems in quantum mechanics. Commun. Pure Appl. Math. 10 (1957) 151-177. | Zbl

[53] J. Keller and D. Givoli, Exact non-reflecting boundary conditions. J. Comput. Phys. 82 (1989) 172-192. | Zbl

[54] S. Knapek, Approximation und Kompression mit Tensorprodukt-Multiskalenräumen. Dissertation, Universität Bonn, April (2000).

[55] S. Knapek, Hyperbolic cross approximation of integral operators with smooth kernel. Tech. Report 665, SFB 256, Univ. Bonn (2000).

[56] A. Knyazev and K. Neymeyr, Efficient solution of symmetric eigenvalue problem using multigrid preconditioners in the locally optimal block conjugate gradient method. Electronic Trans. Numer. Anal. 15 (2003) 38-55. | Zbl

[57] W. Kutzelnigg, Convergence of expansions in a Gaussian basis. Strategies and Applications in Quantum Chemistry, M. Defranceschi and Y. Ellinger Eds., Kluwer, Dordrecht (1996).

[58] W. Kutzelnigg and D. Mukherjee, Minimal parametrization of an n-electron state. Phys. Rev. A 71 (2005) 022502.

[59] C. Le Bris, Computational chemistry from the perspective of numerical analysis. Acta Numer. 14 (2005) 363-444. | Zbl

[60] I. Levine, Quantum chemistry, 5th edn., Prentice-Hall (2000).

[61] W. Liu and A. Sherman, Comparative analysis of Cuthill-McKee and reverse Cuthill-McKee ordering algorithms for sparse matrices. SIAM J. Numer Anal. 13 (1976) 198-213. | Zbl

[62] O. Livne and A. Brandt, $O(NlogN)$ multilevel calculation of $N$ eigenfunctions. Multiscale Computational Methods in Chemistry and Physics, A. Brandt, J. Bernholc and K. Binder Eds., NATO Science Series III: Computer and Systems Sciences, IOS Press 177 (2001) 112-136.

[63] V. Maz'Ya and G. Schmidt, On approximate approximations using Gaussian kernels. IMA J. Numer. Anal. 16 (1996) 13-29. | Zbl

[64] D. Mazziotti, Variational two-electron reduced density matrix theory for many-electron atoms and molecules: Implementation of the spin- and symmetry-adapted T-2 condition through first-order semidefinite programming. Phys. Rev. A 72 (2005) 032510.

[65] A. Messiah, Quantum mechanics. Vol. 1 and 2, North-Holland, Amsterdam, 1961/62. | Zbl

[66] P. Nitsche, Best $n$ term approximation spaces for sparse grids. Tech. Report 2003-11, ETH Zürich, Seminar für Angewandte Mathematik (2003).

[67] P. Oswald, Multilevel finite element approximation. Teubner Skripten zur Numerik, Teubner, Stuttgart (1994). | MR | Zbl

[68] R. Parr and W. Yang, Density Functional Theory of Atoms and Molecules. Oxford University Press, New York (1989).

[69] H.-J. Schmeisser and H. Triebel, Fourier analysis and functions spaces. John Wiley, Chichester (1987). | MR

[70] J.S. Sims and S.A. Hagstrom, High-precision Hy-CI variational calculations for the ground state of neutral helium and helium-like ions. Int. J. Quant. Chem. 90 (2002) 1600-1609.

[71] J. Slater, The theory of complex spectra. Phys. Rev. 34 (1929) 1293-1322. | JFM

[72] S. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions. Soviet Math. Dokl. 4 (1963) 240-243, Russian original in Dokl. Akad. Nauk SSSR 148 (1963) 1042-1045. | Zbl

[73] B. Szabo and I. Babuska, Finite element analysis. Wiley (1991). | MR | Zbl

[74] J. Szeftel, Design of absorbing boundary conditions for Schrödinger equations in ${ℝ}^{d*}$. SIAM J. Numer. Anal. 42 (2004) 1527-1551. | Zbl

[75] J. Weidmann, Linear operators in Hilbert spaces. Springer, New York (1980). | MR | Zbl

[76] H. Yserentant, On the electronic Schrödinger equation. Report 191, SFB 382, Univ. Tübingen (2003).

[77] H. Yserentant, On the regularity of the electronic Schrödinger equation in Hilbert spaces of mixed derivatives. Numer. Math. 98 (2004) 731-759. | Zbl

[78] D. Zung, The approximation of classes of periodic functions of many variables. Russian Math. Surveys 38 (1983) 117-118. | Zbl

[79] D. Zung, Approximation by trigonometric polynomials of functions of several variables on the torus. Math. USSR Sbornik 59 (1988) 247-267. | Zbl