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

Schwab, Christoph; Süli, Endre; Todor, Radu Alexandru

Schwab, Christoph ; Süli, Endre ; Todor, Radu Alexandru

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 42 (2008), p. 777-819 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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 + c u = f (x)$ , $x \in Ω = {(0, 1)}^{d} \subset ℝ^{d}$ , where $a \in ℝ^{d \times d}$ is a symmetric positive semidefinite matrix, using piecewise polynomials of degree $p \geq 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 $u_{h}$ on a partition of $Ω$ of mesh size $h = h_{L} = 2^{- L}$ satisfies the following bound in the streamline-diffusion norm $| | | \cdot {| | |}_{SD}$ , provided $u$ belongs to the space $ℋ^{k + 1} (Ω)$ of functions with square-integrable mixed $(k + 1)$ st derivatives: $| | | u - u_{h} {| | |}_{SD} \leq C_{p, t} d^{2} max {{(2 - p)}_{+}, κ_{0}^{d - 1}, κ_{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 |}_{ℋ^{t + 1} (Ω)},$ where $κ_{i} = κ_{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 $κ_{0}, κ_{1} \in (0, 1)$ , and hence for $p \geq 2$ the ‘error constant’ $C_{p, t} d^{2} max {{(2 - p)}_{+}, κ_{0}^{d - 1}, κ_{1}^{d}}$ exhibits exponential decay as $d \to \infty$ ; in the case of a general symmetric positive semidefinite matrix $a$ , the error constant is shown to grow no faster than $𝒪 (d^{2})$ . In any case, in the absence of assumptions that relate $L$ , $p$ and $d$ , the error $| | | u - u_{h} {| | |}_{SD}$ is still bounded by $κ_{*}^{d - 1} | {log}_{2} h_{L} |^{d - 1} 𝒪 (| \sqrt{a} | h_{L}^{t} + {| b |}^{\frac{1}{2}} h_{L}^{t + \frac{1}{2}} + c^{\frac{1}{2}} h_{L}^{t + 1})$ , where $κ_{*} \in (0, 1)$ for all $L, p, d \geq 2$ .

Publié le : 2008-01-01

MR 2454623 | Zbl 1159.65094 | 1 citation dans Numdam

DOI : https://doi.org/10.1051/m2an:2008027
Classification: 65N30

@article{M2AN_2008__42_5_777_0,
     author = {Schwab, Christoph and S\"uli, Endre and Todor, Radu Alexandru},
     title = {Sparse finite element approximation of high-dimensional transport-dominated diffusion problems},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     volume = {42},
     year = {2008},
     pages = {777-819},
     doi = {10.1051/m2an:2008027},
     mrnumber = {2454623},
     zbl = {1159.65094},
     language = {en},
     url = {http://dml.mathdoc.fr/item/M2AN_2008__42_5_777_0}
}

Schwab, Christoph; Süli, Endre; Todor, Radu Alexandru. Sparse finite element approximation of high-dimensional transport-dominated diffusion problems. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 42 (2008) pp. 777-819. doi : 10.1051/m2an:2008027. http://gdmltest.u-ga.fr/item/M2AN_2008__42_5_777_0/

Bibliographie

[1] 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 SSSR 132 (1960) 982-985. | MR 121607 | Zbl 0102.05301

[2] 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. | MR 2338493 | Zbl pre05286335

[3] 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. | MR 2149930 | Zbl pre02203969

[4] R.F. Bass, Diffusion and Elliptic Operators. Springer-Verlag, New York (1997). | MR 1483890 | Zbl 0914.60009

[5] T.S. Blyth and E.F. Robertson, Further Linear Algebra. Springer-Verlag, London (2002). | MR 1864441 | Zbl 0986.15001

[6] H.-J. Bungartz, Finite elements of higher order on sparse grids. Habilitation thesis, Informatik, TU München, Aachen: Shaker Verlag (1998).

[7] H.-J. Bungartz and M. Griebel, Sparse grids. Acta Numer. 13 (2004) 1-123. | MR 2249147 | Zbl 1118.65388

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

[9] 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. | MR 2207615 | Zbl 1097.65004

[10] 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.

[11] 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. | MR 2277104 | Zbl 1106.65332

[12] V.H. Hoang and C. Schwab, High dimensional finite elements for elliptic problems with multiple scales. Multiscale Model. Simul. 3 (2005) 168-194. | MR 2123115 | Zbl 1074.65135

[13] 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). | MR 705278 | Zbl 0521.35002

[14] P. Houston and E. Süli, Stabilized $h p$ -finite element approximation of partial differential equations with non-negative characteristic form. Computing 66 (2001) 99-119. | Zbl 0985.65136

[15] P. Houston, C. Schwab and E. Süli, Discontinuous $h p$ -finite element methods for advection-diffusion-reaction problems. SIAM J. Numer. Anal. 39 (2002) 2133-2163. | MR 1897953 | Zbl 1015.65067

[16] 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). | MR 2186059 | Zbl 1136.65133

[17] P. Laurençot and S. Mischler, The continuous coagulation fragmentation equations with diffusion. Arch. Rational Mech. Anal. 162 (2002) 45-99. | MR 1892231 | Zbl 0997.45005

[18] C. Le Bris and P.-L. Lions, Renormalized solutions of some transport equations with $W^{1, 1}$ velocities and applications. Annali di Matematica 183 (2004) 97-130. | MR 2044334 | Zbl pre05058532

[19] 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. | MR 1485004 | Zbl 0889.65016

[20] O.A. Oleĭnik and E.V. Radkevič, Second Order Equations with Nonnegative Characteristic Form. American Mathematical Society, Providence, RI (1973). | MR 457908

[21] H.-C. Öttinger, Stochastic Processes in Polymeric Fluids. Springer-Verlag, New York (1996). | MR 1383323 | Zbl 0995.60098

[22] H.-G. Roos, M. Stynes and L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations. Convection-Diffusion and Flow Problems, Springer Series in Computational Mathematics 24. Springer-Verlag, New York (1996). | MR 1477665 | Zbl 1155.65087

[23] C. Schwab, $p$ - and $h p$ -Finite Element Methods: Theory and Applications in Solid and Fluid Mechanics, Numerical Methods and Scientific Computation. Clarendon Press, Oxford (1998). | MR 1695813 | Zbl 0910.73003

[24] 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 SSSR 148 (1963) 1042-1045. | MR 147825 | Zbl 0202.39901

[25] 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 | MR 2277111 | Zbl 1106.65331

[26] 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 | MR 2275728 | Zbl 1100.65103

[27] V. Temlyakov, Approximation of functions with bounded mixed derivative, in Proc. Steklov Inst. of Math. 178, American Mathematical Society, Providence, RI (1989). | MR 1005898 | Zbl 0668.41024

[28] N.G. Van Kampen, Stochastic Processes in Physics and Chemistry. Elsevier, Amsterdam (1992). | Zbl 0511.60038

[29] T. Von Petersdorff and C. Schwab, Numerical solution of parabolic equations in high dimensions. ESAIM: M2AN 38 (2004) 93-128. | Numdam | MR 2073932 | Zbl 1083.65095

[30] G. Wasilkowski and H. Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems. J. Complexity 11 (1995) 1-56. | MR 1319049 | Zbl 0819.65082

[31] C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations, W. Hackbusch Ed., Notes on Numerical Fluid Mechanics 31, Vieweg, Braunschweig/Wiesbaden (1991). | MR 1167863 | Zbl 0763.65091

[32] 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 Engineering 10, Springer, Berlin (Proceedings SciTools '98) (2000) 133-177. | Zbl 0943.65111