Numerical solution of parabolic equations in high dimensions

Tobias Von Petersdorff; Christoph Schwab

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2004)

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

Abstract

top
We consider the numerical solution of diffusion problems in ( 0 , T ) × Ω for Ω ⊂ ℝ d and for T > 0 in dimension d ≥ 1 . We use a wavelet based sparse grid space discretization with mesh-width h and order p ≥ 1 , and h p 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 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.

How to cite

top

Petersdorff, Tobias Von, and Schwab, Christoph. "Numerical solution of parabolic equations in high dimensions." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 38.1 (2004): 93-127. <http://eudml.org/doc/246004>.

@article{Petersdorff2004,
abstract = {We consider the numerical solution of diffusion problems in $(0,T) \times \Omega $ for $\Omega \subset \mathbb \{R\}^d$ and for $T &gt; 0$ in dimension $d \ge 1$. We use a wavelet based sparse grid space discretization with mesh-width $h$ and order $p \ge 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 $L^2(\Omega )$-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^\epsilon (\Omega )$ with $\epsilon &gt;0$ and that $u(x,t)$ is smooth in $x$ for $t&gt;0$. Numerical experiments in dimension $d$ up to $25$ confirm the theory.},
author = {Petersdorff, Tobias Von, Schwab, Christoph},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {discontinuous Galerkin method; sparse grid; wavelets; parabolic partial differential equation; high dimension; finite elements; GMRES iterations; preconditioner; error estimates; algorithm; convergence; numerical results; heat equation},
language = {eng},
number = {1},
pages = {93-127},
publisher = {EDP-Sciences},
title = {Numerical solution of parabolic equations in high dimensions},
url = {http://eudml.org/doc/246004},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Petersdorff, Tobias Von
AU - Schwab, Christoph
TI - Numerical solution of parabolic equations in high dimensions
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 1
SP - 93
EP - 127
AB - We consider the numerical solution of diffusion problems in $(0,T) \times \Omega $ for $\Omega \subset \mathbb {R}^d$ and for $T &gt; 0$ in dimension $d \ge 1$. We use a wavelet based sparse grid space discretization with mesh-width $h$ and order $p \ge 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 $L^2(\Omega )$-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^\epsilon (\Omega )$ with $\epsilon &gt;0$ and that $u(x,t)$ is smooth in $x$ for $t&gt;0$. Numerical experiments in dimension $d$ up to $25$ confirm the theory.
LA - eng
KW - discontinuous Galerkin method; sparse grid; 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/246004
ER -

References

top
  1. [1] H. Amann, Linear and Quasilinear Parabolic Problems 1: Abstract Linear Theory. Birkhäuser, Basel (1995). Zbl0819.35001MR1345385
  2. [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. Zbl0954.65078
  3. [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. Zbl0524.65019
  4. [4] M. Griebel and S. Knapek, Optimized tensor product approximation spaces. Constr. Approx. 16 (2000) 525–540. Zbl0969.65107
  5. [5] M. Griebel, P. Oswald and T. Schiekofer, Sparse grids for boundary integral equations. Numer. Math. 83 (1999) 279–312. Zbl0935.65131
  6. [6] J.L. Lions and E. Magenes, Non-homogeneous boundary value problems and applications I. Springer-Verlag (1972). Zbl0223.35039
  7. [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. [8] H.C. Öttinger, Stochastic Processes in polymeric fluids. Springer-Verlag (1998). Zbl0995.60098MR1383323
  9. [9] A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations. Appl. Math. Sci., Springer-Verlag, New York 44 (1983). Zbl0516.47023MR710486
  10. [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. Zbl1038.65129
  11. [11] D. Schötzau, hp-DGFEM for Parabolic Evolution Problems. Dissertation ETH Zurich (1999). 
  12. [12] D. Schötzau and C. Schwab, Time discretization of parabolic problems by the h p -version of the discontinuous Galerkin finite element method. SIAM J. Numer. Analysis 38 (2000) 837–875. Zbl0978.65091
  13. [13] D. Schötzau and C. Schwab, h p -Discontinuous Galerkin time-stepping for parabolic problems. C.R. Acad. Sci. Paris 333 (2001) 1121–1126. Zbl0993.65108
  14. [14] C. Schwab, p and h p Finite Element Methods. Oxford University Press (1998). Zbl0910.73003MR1695813
  15. [15] C. Schwab and R.A. Todor, Sparse finite elements for stochastic elliptic problems-higher order moments (in press in Computing 2003), http://www.math.ethz.ch/research/groups/sam/reports/2003 Zbl1044.65006MR2009650
  16. [16] V. Thomee, Galerkin Finite Element Methods for Parabolic Problems. Springer-Verlag (1997). Zbl0884.65097MR1479170
  17. [17] T. von Petersdorff and C. Schwab, Wavelet-discretizations of parabolic integro-differential equations. SIAM J. Numer. Anal. 41 (2003) 159–180. Zbl1050.65134
  18. [18] T. Werder, D. Schötzau, K. Gerdes and C. Schwab, h p -Discontinuous Galerkin time-stepping for parabolic problems. Comput. Methods Appl. Mech. Eng. 190 (2001) 6685–6708. Zbl0992.65103

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.