Petersdorff, Tobias Von; Schwab, Christoph
Numerical solution of parabolic equations in high dimensions
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 38 (2004) no. 1 , p. 93-127
Zbl 1083.65095 | MR 2073932 | 5 citations dans Numdam
doi : 10.1051/m2an:2004005
URL stable :

Classification:  65N30
We consider the numerical solution of diffusion problems in (0,T)×Ω for Ω d and for T>0 in dimension d1. We use a wavelet based sparse grid space discretization with mesh-width h and order p1, and hp discontinuous Galerkin time-discretization of order r=O(logh) on a geometric sequence of O(logh) many time steps. The linear systems in each time step are solved iteratively by O(logh) GMRES iterations with a wavelet preconditioner. We prove that this algorithm gives an L 2 (Ω)-error of O(N -p ) for u(x,T) where N is the total number of operations, provided that the initial data satisfies u 0 H ϵ (Ω) with ϵ>0 and that u(x,t) is smooth in x for t>0. Numerical experiments in dimension d up to 25 confirm the theory.


[1] H. Amann, Linear and Quasilinear Parabolic Problems 1: Abstract Linear Theory. Birkhäuser, Basel (1995). MR 1345385 | Zbl 0819.35001

[2] H.-J. 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

[3] S.C. Eisenstat, H.C. Elman and M.H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal. 20 (1983) 345-357. Zbl 0524.65019

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

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

[6] J.L. Lions and E. Magenes, Non-homogeneous boundary value problems and applications I. Springer-Verlag (1972). Zbl 0223.35039

[7] P. Oswald, On best N-term approximation by Haar functions in H s -norms, in Metric Function Theory and Related Topics in Analysis. S.M. Nikolskij, B.S. Kashin, A.D. Izaak Eds., AFC, Moscow (1999) 137-163 (in Russian).

[8] H.C. Öttinger, Stochastic Processes in polymeric fluids. Springer-Verlag (1998). MR 1383323 | Zbl 0995.60098

[9] A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations. Appl. Math. Sci., Springer-Verlag, New York 44 (1983). MR 710486 | Zbl 0516.47023

[10] G. Schmidlin, C. Lage and C. Schwab, Rapid solution of first kind boundary integral equations in 3 . Eng. Anal. Bound. Elem. 27 (2003) 469-490. Zbl 1038.65129

[11] D. Schötzau, hp-DGFEM for Parabolic Evolution Problems. Dissertation ETH Zurich (1999).

[12] D. Schötzau and C. Schwab, Time discretization of parabolic problems by the hp-version of the discontinuous Galerkin finite element method. SIAM J. Numer. Analysis 38 (2000) 837-875. Zbl 0978.65091

[13] D. Schötzau and C. Schwab, hp-Discontinuous Galerkin time-stepping for parabolic problems. C.R. Acad. Sci. Paris 333 (2001) 1121-1126. Zbl 0993.65108

[14] C. Schwab, p and hp Finite Element Methods. Oxford University Press (1998). MR 1695813 | Zbl 0910.73003

[15] C. Schwab and R.A. Todor, Sparse finite elements for stochastic elliptic problems-higher order moments (in press in Computing 2003), MR 2009650 | Zbl 1044.65006

[16] V. Thomee, Galerkin Finite Element Methods for Parabolic Problems. Springer-Verlag (1997). MR 1479170 | Zbl 0884.65097

[17] T. Von Petersdorff and C. Schwab, Wavelet-discretizations of parabolic integro-differential equations. SIAM J. Numer. Anal. 41 (2003) 159-180. Zbl 1050.65134

[18] T. Werder, D. Schötzau, K. Gerdes and C. Schwab, hp-Discontinuous Galerkin time-stepping for parabolic problems. Comput. Methods Appl. Mech. Eng. 190 (2001) 6685-6708. Zbl 0992.65103