# Sparse finite element approximation of high-dimensional transport-dominated diffusion problems

Christoph Schwab; Endre Süli; Radu Alexandru Todor

ESAIM: Mathematical Modelling and Numerical Analysis (2008)

- Volume: 42, Issue: 5, page 777-819
- ISSN: 0764-583X

## Access Full Article

top## Abstract

top## How to cite

topSchwab, Christoph, Süli, Endre, and Todor, Radu Alexandru. "Sparse finite element approximation of high-dimensional transport-dominated diffusion problems." ESAIM: Mathematical Modelling and Numerical Analysis 42.5 (2008): 777-819. <http://eudml.org/doc/250411>.

@article{Schwab2008,

abstract = {
We develop the analysis of stabilized sparse tensor-product
finite element methods for high-dimensional,
non-self-adjoint and possibly degenerate second-order partial
differential equations of the form
$-a:\nabla\nabla u + b \cdot \nabla u + cu = f(x)$, $x \in
\Omega = (0,1)^d \subset \mathbb\{R\}^d$,
where $a \in \mathbb\{R\}^\{d\times d\}$ is a symmetric positive semidefinite matrix,
using piecewise polynomials of
degree p ≥ 1. Our convergence analysis is based on new
high-dimensional approximation results in sparse tensor-product
spaces. We show that the error between the analytical solution u and its stabilized
sparse finite element approximation uh on a partition of
Ω of mesh size h = hL = 2-L satisfies the
following bound in the streamline-diffusion norm $|||\cdot|||_\{\rm SD\}$,
provided u belongs to the space $\mathcal\{H\}^\{k+1\}(\Omega)$ of functions
with square-integrable mixed (k+1)st derivatives:
\[
|||u-u\_h|||\_\{\rm SD\}\leq C\_\{p,t\} d^2 \max\\{(2-p)\_+,\kappa\_0^\{d-1\},\kappa\_1^d\\} (|\sqrt\{a\}| h\_L^t
+ |b|^\{\frac\{1\}\{2\}\} h\_L^\{t+\frac\{1\}\{2\}\} + c^\{\frac\{1\}\{2\}\} h\_L^\{t+1\} \!)|u|\_\{\mathcal\{H\}^\{t+1\}(\Omega)\}, \qquad \qquad \qquad
\]
where $\kappa_i=\kappa_i(p,t,L)$, i=0,1, and $1 \leq t \leq \min(k,p)$.
We show, under various mild conditions
relating L to p, L to d, or p to d,
that in the case of elliptic transport-dominated
diffusion problems $\kappa_0, \kappa_1 \in (0,1)$, and hence for p ≥ 1 the
'error constant' $C_\{p,t\} d^2 \max\\{(2-p)_+,\kappa_0^\{d-1\},\kappa_1^d\\}$
exhibits exponential decay as d → ∞; in the case of a
general symmetric positive semidefinite matrix a,
the error constant is shown to grow no faster than $\mathcal\{O\}(d^2)$.
In any case, in the absence of assumptions that relate L, p and d,
the error $|||u - u_h|||_\{\rm SD\}$ is still bounded by $\kappa_\ast^\{d-1\}
|\log_2 h_L|^\{d-1\}\mathcal\{O\}(|\sqrt\{a\}| h_L^t
+ |b|^\{\frac\{1\}\{2\}\} h_L^\{t+\frac\{1\}\{2\}\}
+ c^\{\frac\{1\}\{2\}\} h_L^\{t+1\})$, where $\kappa_\ast \in (0,1)$ for all L, p, d ≥ 2.
},

author = {Schwab, Christoph, Süli, Endre, Todor, Radu Alexandru},

journal = {ESAIM: Mathematical Modelling and Numerical Analysis},

keywords = {High-dimensional Fokker-Planck equations; partial differential
equations with nonnegative characteristic form; sparse finite
element method.; high-dimensional Fokker-Planck equations; non-negative characteristic form; sparse finite element method; error bounds; convergence; sparse tensor-product spaces},

language = {eng},

month = {7},

number = {5},

pages = {777-819},

publisher = {EDP Sciences},

title = {Sparse finite element approximation of high-dimensional transport-dominated diffusion problems},

url = {http://eudml.org/doc/250411},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Schwab, Christoph

AU - Süli, Endre

AU - Todor, Radu Alexandru

TI - Sparse finite element approximation of high-dimensional transport-dominated diffusion problems

JO - ESAIM: Mathematical Modelling and Numerical Analysis

DA - 2008/7//

PB - EDP Sciences

VL - 42

IS - 5

SP - 777

EP - 819

AB -
We develop the analysis of stabilized sparse tensor-product
finite element methods for high-dimensional,
non-self-adjoint and possibly degenerate second-order partial
differential equations of the form
$-a:\nabla\nabla u + b \cdot \nabla u + cu = f(x)$, $x \in
\Omega = (0,1)^d \subset \mathbb{R}^d$,
where $a \in \mathbb{R}^{d\times d}$ is a symmetric positive semidefinite matrix,
using piecewise polynomials of
degree p ≥ 1. Our convergence analysis is based on new
high-dimensional approximation results in sparse tensor-product
spaces. We show that the error between the analytical solution u and its stabilized
sparse finite element approximation uh on a partition of
Ω of mesh size h = hL = 2-L satisfies the
following bound in the streamline-diffusion norm $|||\cdot|||_{\rm SD}$,
provided u belongs to the space $\mathcal{H}^{k+1}(\Omega)$ of functions
with square-integrable mixed (k+1)st derivatives:
\[
|||u-u_h|||_{\rm SD}\leq C_{p,t} d^2 \max\{(2-p)_+,\kappa_0^{d-1},\kappa_1^d\} (|\sqrt{a}| h_L^t
+ |b|^{\frac{1}{2}} h_L^{t+\frac{1}{2}} + c^{\frac{1}{2}} h_L^{t+1} \!)|u|_{\mathcal{H}^{t+1}(\Omega)}, \qquad \qquad \qquad
\]
where $\kappa_i=\kappa_i(p,t,L)$, i=0,1, and $1 \leq t \leq \min(k,p)$.
We show, under various mild conditions
relating L to p, L to d, or p to d,
that in the case of elliptic transport-dominated
diffusion problems $\kappa_0, \kappa_1 \in (0,1)$, and hence for p ≥ 1 the
'error constant' $C_{p,t} d^2 \max\{(2-p)_+,\kappa_0^{d-1},\kappa_1^d\}$
exhibits exponential decay as d → ∞; in the case of a
general symmetric positive semidefinite matrix a,
the error constant is shown to grow no faster than $\mathcal{O}(d^2)$.
In any case, in the absence of assumptions that relate L, p and d,
the error $|||u - u_h|||_{\rm SD}$ is still bounded by $\kappa_\ast^{d-1}
|\log_2 h_L|^{d-1}\mathcal{O}(|\sqrt{a}| h_L^t
+ |b|^{\frac{1}{2}} h_L^{t+\frac{1}{2}}
+ c^{\frac{1}{2}} h_L^{t+1})$, where $\kappa_\ast \in (0,1)$ for all L, p, d ≥ 2.

LA - eng

KW - High-dimensional Fokker-Planck equations; partial differential
equations with nonnegative characteristic form; sparse finite
element method.; high-dimensional Fokker-Planck equations; non-negative characteristic form; sparse finite element method; error bounds; convergence; sparse tensor-product spaces

UR - http://eudml.org/doc/250411

ER -

## References

top- K. Babenko, Approximation by trigonometric polynomials is a certain class of periodic functions of several variables. Soviet Math. Dokl.1 (1960) 672–675. Russian original in Dokl. Akad. Nauk SSSR132 (1960) 982–985.
- J.W. Barrett and E. Süli, Existence of global weak solutions to kinetic models of dilute polymers. Multiscale Model. Simul.6 (2007) 506–546.
- J.W. Barrett, C. Schwab and E. Süli, Existence of global weak solutions for some polymeric flow models. Math. Models Methods Appl. Sci.15 (2005) 939–983.
- R.F. Bass, Diffusion and Elliptic Operators. Springer-Verlag, New York (1997).
- T.S. Blyth and E.F. Robertson, Further Linear Algebra. Springer-Verlag, London (2002).
- H.-J. Bungartz, Finite elements of higher order on sparse grids. Habilitation thesis, Informatik, TU München, Aachen: Shaker Verlag (1998).
- H.-J. Bungartz and M. Griebel, Sparse grids. Acta Numer.13 (2004) 1–123.
- R. DeVore, S. Konyagin and V. Temlyakov, Hyperbolic wavelet approximation. Constr. Approx.14 (1998) 1–26.
- J. Dick, I.H. Sloan, X. Wang and H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights. Numer. Math.103 (2006) 63–97.
- J. Elf, P. Lötstedt and P. Sjöberg, Problems of high dimension in molecular biology, in Proceedings of the 19th GAMM-Seminar Leipzig, W. Hackbusch Ed. (2003) 21–30.
- M. Griebel, Sparse grids and related approximation schemes for higher dimensional problems, in Foundations of Computational Mathematics 2005, L.-M. Pardo, A. Pinkus, E. Süli, M. Todd Eds., Cambridge University Press (2006) 106–161.
- V.H. Hoang and C. Schwab, High dimensional finite elements for elliptic problems with multiple scales. Multiscale Model. Simul.3 (2005) 168–194.
- L. Hörmander, The Analysis of Linear Partial Differential Operators II: Differential Operators with Constant Coefficients. Springer-Verlag, Berlin, Reprint of the 1983 edition (2005).
- P. Houston and E. Süli, Stabilized hp-finite element approximation of partial differential equations with non-negative characteristic form. Computing66 (2001) 99–119.
- P. Houston, C. Schwab and E. Süli, Discontinuous hp-finite element methods for advection-diffusion-reaction problems. SIAM J. Numer. Anal.39 (2002) 2133–2163.
- B. Lapeyre, É. Pardoux and R. Sentis, Introduction to Monte-Carlo Methods for Transport and Diffusion Equations, Oxford Texts in Applied and Engineering Mathematics. Oxford University Press, Oxford (2003).
- P. Laurençot and S. Mischler, The continuous coagulation fragmentation equations with diffusion. Arch. Rational Mech. Anal.162 (2002) 45–99.
- C. Le Bris and P.-L. Lions, Renormalized solutions of some transport equations with W1,1 velocities and applications. Annali di Matematica183 (2004) 97–130.
- E. Novak and K. Ritter, The curse of dimension and a universal method for numerical integration, in Multivariate Approximation and Splines, G. Nürnberger, J. Schmidt and G. Walz Eds., International Series in Numerical Mathematics, Birkhäuser, Basel (1998) 177–188.
- O.A. Oleĭnik and E.V. Radkevič, Second Order Equations with Nonnegative Characteristic Form. American Mathematical Society, Providence, RI (1973).
- H.-C. Öttinger, Stochastic Processes in Polymeric Fluids. Springer-Verlag, New York (1996).
- H.-G. Roos, M. Stynes and L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations. Convection-Diffusion and Flow Problems, Springer Series in Computational Mathematics24. Springer-Verlag, New York (1996).
- C. Schwab, p- and hp-Finite Element Methods: Theory and Applications in Solid and Fluid Mechanics, Numerical Methods and Scientific Computation. Clarendon Press, Oxford (1998).
- S. Smolyak, Quadrature and interpolation formulas for products of certain classes of functions. Soviet Math. Dokl.4 (1963) 240–243. Russian original in Dokl. Akad. Nauk SSSR148 (1963) 1042–1045.
- E. Süli, Finite element approximation of high-dimensional transport-dominated diffusion problems, in Foundations of Computational Mathematics 2005, L.-M. Pardo, A. Pinkus, E. Süli, M. Todd Eds., Cambridge University Press (2006) 343–370. Available at: http://web.comlab.ox.ac.uk/oucl/publications/natr/index.html
- E. Süli, Finite element algorithms for transport-diffusion problems: stability, adaptivity, tractability, in Invited Lecture at the International Congress of Mathematicians, Madrid, 22–30 August 2006. Available at: http://web.comlab.ox.ac.uk/work/endre.suli/Suli-ICM2006.pdf
- V. Temlyakov, Approximation of functions with bounded mixed derivative, in Proc. Steklov Inst. of Math.178, American Mathematical Society, Providence, RI (1989).
- N.G. van Kampen, Stochastic Processes in Physics and Chemistry. Elsevier, Amsterdam (1992).
- T. von Petersdorff and C. Schwab, Numerical solution of parabolic equations in high dimensions. ESAIM: M2AN38 (2004) 93–128.
- G. Wasilkowski and H. Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems. J. Complexity11 (1995) 1–56.
- C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations, W. Hackbusch Ed., Notes on Numerical Fluid Mechanics31, Vieweg, Braunschweig/Wiesbaden (1991).
- G.W. Zumbusch, A sparse grid PDE solver, in Advances in Software Tools for Scientific Computing, H.P. Langtangen, A.M. Bruaset and E. Quak Eds., Lecture Notes in Computational Science and Engineering10, Springer, Berlin (Proceedings SciTools '98) (2000) 133–177.

## Citations in EuDML Documents

top## NotesEmbed ?

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