Griebel, Michael; Hamaekers, Jan
Sparse grids for the Schrödinger equation
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 41 (2007) no. 2 , p. 215-247
Zbl pre05252000 | MR 2339626
doi : 10.1051/m2an:2007015
URL stable :

Classification:  35J10,  65N25,  65N30,  65T40,  65Z05
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 1065.81036

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

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

[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 0102.05301

[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 134403 | Zbl 0103.12901

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

[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 0954.65078

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

[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 0873.65030

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

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

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

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

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

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

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

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

[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 0971.65008

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

[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 0938.35013

[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),

[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). MR 2223504

[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 1005.81095

[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 1075.35063

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

[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 0979.65101

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

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

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

[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 2277104 | Zbl 1106.65332

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

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

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

[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 0826.65099

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

[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 1136.65315

[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 0985.81133

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

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

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

[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 1031.65126

[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 1119.65390

[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 0331.65022

[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 0838.65005

[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 0102.42602

[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 1312165 | Zbl 0830.65107

[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 891189

[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 55.0535.04

[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 0202.39901

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

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

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

[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 1062.35100

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

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