Numerical solution of parabolic equations in high dimensions

Tobias von Petersdorff; Christoph Schwab

ESAIM: Mathematical Modelling and Numerical Analysis (2010)

  • Volume: 38, Issue: 1, page 93-127
  • ISSN: 0764-583X

Abstract

top
We consider the numerical solution of diffusion problems in (0,T) x Ω for Ω ⊂ ℝ d and for T > 0 in dimension dd ≥ 1. We use a wavelet based sparse grid space discretization with mesh-width h and order pd ≥ 1, and hp discontinuous Galerkin time-discretization of order r = O ( log h ) on a geometric sequence of O ( log h ) many time steps. The linear systems in each time step are solved iteratively by O ( log h ) GMRES iterations with a wavelet preconditioner. We prove that this algorithm gives an L2(Ω)-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.

How to cite

top

von Petersdorff, Tobias, and Schwab, Christoph. "Numerical solution of parabolic equations in high dimensions." ESAIM: Mathematical Modelling and Numerical Analysis 38.1 (2010): 93-127. <http://eudml.org/doc/194210>.

@article{vonPetersdorff2010,
abstract = { We consider the numerical solution of diffusion problems in (0,T) x Ω for $\Omega\subset \mathbb\{R\}^d$ and for T > 0 in dimension dd ≥ 1. We use a wavelet based sparse grid space discretization with mesh-width h and order pd ≥ 1, and hp discontinuous Galerkin time-discretization of order $r = O(\left|\log h\right|)$ on a geometric sequence of $O(\left|\log h\right|)$ many time steps. The linear systems in each time step are solved iteratively by $O(\left|\log h\right|)$ GMRES iterations with a wavelet preconditioner. We prove that this algorithm gives an L2(Ω)-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 \in H^\varepsilon(\Omega)$ 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. },
author = {von Petersdorff, Tobias, Schwab, Christoph},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Discontinuous Galerkin method; sparse grid; wavelets.; discontinuous Galerkin method; wavelets; parabolic partial differential equation; high dimension; finite elements; GMRES iterations; preconditioner; error estimates; algorithm; convergence; numerical results; heat equation},
language = {eng},
month = {3},
number = {1},
pages = {93-127},
publisher = {EDP Sciences},
title = {Numerical solution of parabolic equations in high dimensions},
url = {http://eudml.org/doc/194210},
volume = {38},
year = {2010},
}

TY - JOUR
AU - von Petersdorff, Tobias
AU - Schwab, Christoph
TI - Numerical solution of parabolic equations in high dimensions
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2010/3//
PB - EDP Sciences
VL - 38
IS - 1
SP - 93
EP - 127
AB - We consider the numerical solution of diffusion problems in (0,T) x Ω for $\Omega\subset \mathbb{R}^d$ and for T > 0 in dimension dd ≥ 1. We use a wavelet based sparse grid space discretization with mesh-width h and order pd ≥ 1, and hp discontinuous Galerkin time-discretization of order $r = O(\left|\log h\right|)$ on a geometric sequence of $O(\left|\log h\right|)$ many time steps. The linear systems in each time step are solved iteratively by $O(\left|\log h\right|)$ GMRES iterations with a wavelet preconditioner. We prove that this algorithm gives an L2(Ω)-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 \in H^\varepsilon(\Omega)$ 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.
LA - eng
KW - Discontinuous Galerkin method; sparse grid; wavelets.; discontinuous Galerkin method; wavelets; parabolic partial differential equation; high dimension; finite elements; GMRES iterations; preconditioner; error estimates; algorithm; convergence; numerical results; heat equation
UR - http://eudml.org/doc/194210
ER -

References

top
  1. H. Amann, Linear and Quasilinear Parabolic Problems 1: Abstract Linear Theory. Birkhäuser, Basel (1995).  
  2. H.-J. Bungartz and M. Griebel, A note on the complexity of solving Poisson's equation for spaces of bounded mixed derivatives. J. Complexity15 (1999) 167–199.  
  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.  
  4. M. Griebel and S. Knapek, Optimized tensor product approximation spaces. Constr. Approx.16 (2000) 525–540.  
  5. M. Griebel, P. Oswald and T. Schiekofer, Sparse grids for boundary integral equations. Numer. Math.83 (1999) 279–312.  
  6. J.L. Lions and E. Magenes, Non-homogeneous boundary value problems and applications I. Springer-Verlag (1972).  
  7. P. Oswald, On best N-term approximation by Haar functions in Hs-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).  
  9. A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations. Appl. Math. Sci., Springer-Verlag, New York 44 (1983).  
  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.  
  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. Analysis38 (2000) 837–875.  
  13. D. Schötzau and C. Schwab, hp-Discontinuous Galerkin time-stepping for parabolic problems. C.R. Acad. Sci. Paris333 (2001) 1121–1126.  
  14. C. Schwab, p and hp Finite Element Methods. Oxford University Press (1998).  
  15. C. Schwab and R.A. Todor, Sparse finite elements for stochastic elliptic problems-higher order moments (in press in Computing 2003),  URIhttp://www.math.ethz.ch/research/groups/sam/reports/2003
  16. V. Thomee, Galerkin Finite Element Methods for Parabolic Problems. Springer-Verlag (1997).  
  17. T. von Petersdorff and C. Schwab, Wavelet-discretizations of parabolic integro-differential equations. SIAM J. Numer. Anal.41 (2003) 159–180.  
  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.  

Citations in EuDML Documents

top
  1. Ana-Maria Matache, Tobias Von Petersdorff, Christoph Schwab, Fast deterministic pricing of options on Lévy driven assets
  2. Ana-Maria Matache, Tobias von Petersdorff, Christoph Schwab, Fast deterministic pricing of options on Lévy driven assets
  3. Christoph Schwab, Endre Süli, Radu Alexandru Todor, Sparse finite element approximation of high-dimensional transport-dominated diffusion problems
  4. Kyoung-Sook Moon, Ricardo H. Nochetto, Tobias von Petersdorff, Chen-song Zhang, error analysis for parabolic variational inequalities
  5. Nils Reich, Wavelet compression of anisotropic integrodifferential operators on sparse tensor product spaces
  6. Andrea Bonito, Philippe Clément, Marco Picasso, Finite element analysis of a simplified stochastic Hookean dumbbells model arising from viscoelastic flows

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.