The numerical approximation of parametric partial differential equations is a computational challenge, in particular when the number of involved parameter is large. This paper considers a model class of second order, linear, parametric, elliptic PDEs on a bounded domain D with diffusion coefficients depending on the parameters in an affine manner. For such models, it was shown in [9, 10] that under very weak assumptions on the diffusion coefficients, the entire family of solutions to such equations can be simultaneously approximated in the Hilbert space V = H01(D) by multivariate sparse polynomials in the parameter vector y with a controlled number N of terms. The convergence rate in terms of N does not depend on the number of parameters in V, which may be arbitrarily large or countably infinite, thereby breaking the curse of dimensionality. However, these approximation results do not describe the concrete construction of these polynomial expansions, and should therefore rather be viewed as benchmark for the convergence analysis of numerical methods. The present paper presents an adaptive numerical algorithm for constructing a sequence of sparse polynomials that is proved to converge toward the solution with the optimal benchmark rate. Numerical experiments are presented in large parameter dimension, which confirm the effectiveness of the adaptive approach.

Classification: 65N35, 65L10, 35J25

Keywords: parametric and stochastic PDE's, sparse polynomial approximation, high dimensional problems, adaptive algorithms

@article{M2AN_2013__47_1_253_0, author = {Chkifa, Abdellah and Cohen, Albert and DeVore, Ronald and Schwab, Christoph}, title = {Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs}, journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique}, publisher = {EDP-Sciences}, volume = {47}, number = {1}, year = {2013}, pages = {253-280}, doi = {10.1051/m2an/2012027}, zbl = {1273.65009}, language = {en}, url = {http://www.numdam.org/item/M2AN_2013__47_1_253_0} }

Chkifa, Abdellah; Cohen, Albert; DeVore, Ronald; Schwab, Christoph. Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 47 (2013) no. 1, pp. 253-280. doi : 10.1051/m2an/2012027. http://www.numdam.org/item/M2AN_2013__47_1_253_0/

[1] Galerkin finite element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal. 42 (2004) 800−825. | MR 2084236 | Zbl 1080.65003

, and ,[2] A stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 45 (2007) 1005−1034. | MR 2318799 | Zbl 1151.65008

, and ,[3] Adaptive finite element methods for elliptic equations with non-smooth coefficients. Numer. Math. 85 (2000) 579−608. | MR 1771781 | Zbl 0962.65096

and ,[4] Adaptive finite element methods with convergence rates. Numer. Math. 97 (2004) 219−268. | MR 2050077 | Zbl 1063.65120

, , and ,[5] A priori convergence of the greedy algorithm for the parameterized reduced basis. ESAIM : M2AN 3 (2012) 595-603. | Numdam | MR 2877366 | Zbl 1272.65084

, , , and ,[6] Numerical analysis of wavelet methods. Elsevier, Amsterdam (2003). | MR 1990555 | Zbl 1038.65151

,[7] Adaptive wavelet methods for elliptic operator equations - Convergence rates. Math. Comput. 70 (2000) 27−75. | MR 1803124 | Zbl 0980.65130

, and ,[8] Adaptive wavelet methods for operator equations - Beyond the elliptic case. J. FoCM 2 (2002) 203−245. | MR 1907380 | Zbl 1025.65056

, and ,[9] Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs. Found. Comput. Math. 10 (2010) 615-646. | MR 2728424 | Zbl 1206.60064

, and ,[10] Analytic regularity and polynomial approximation of parametric and stochastic PDE's. Anal. Appl. 9 (2011) 11-47. | MR 2763359 | Zbl 1219.35379

, and ,[11] Nonlinear approximation. Acta Numer. 7 (1998) 51-150. | MR 1689432 | Zbl 0931.65007

,[12] A convergent adaptive algorithm for Poisson's equation. SIAM J. Numer. Anal. 33 (1996) 1106-1124. | MR 1393904 | Zbl 0854.65090

,[13] Finite elements for elliptic problems with stochastic coefficients. Comput. Methods Appl. Mech. Eng. 194 (2005) 205-228. | MR 2105161 | Zbl 1143.65392

, and ,[14] An optimal adaptive wavelet method without coarsening of the iterands. Math. Comput. 76 (2007) 615-629. | MR 2291830 | Zbl 1115.41023

, and ,[15] Spectral techniques for stochastic finite elements. Arch. Comput. Methods Eng. 4 (1997) 63-100. | MR 1437889 | Zbl 0722.73080

and ,[16] Elliptic problems on non-smooth domains. Pitman (1983). | Zbl 0695.35060

,[17] Sparse tensor Galerkin discretizations for parametric and random parabolic PDEs I : Analytic regularity and gpc-approximation. Report 2010-11, Seminar for Applied Mathematics, ETH Zürich (in review). | Zbl 1285.35137

and ,[18] Analytic regularity and gpc approximation for parametric and random 2nd order hyperbolic PDEs. Report 2010-19, Seminar for Applied Mathematics, ETH Zürich (to appear in Anal. Appl. (2011)).

and ,[19] The stochastic finite element methods. John Wiley & Sons, Chichester (1992). | MR 1198887 | Zbl 0902.73004

and ,[20] Reduced basis methods in linear elasticity with many parameters. Comput. Methods Appl. Mech. Eng. 197 (2008) 4812-4829. | MR 2467002 | Zbl 1194.74445

, and ,[21] Data oscillation and convergence of adaptive FEM. SIAM J. Numer. Anal. 38 (2000) 466-488. | MR 1770058 | Zbl 0970.65113

, and ,[22] A sparse grid stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 46 (2008) 2309-2345. | MR 2421037 | Zbl 1176.65137

, and ,[23] An anisotropic sparse grid stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 46 (2008) 2411-2442. | MR 2421041 | Zbl 1176.65007

, and ,[24] Sparse deterministic approximation of Bayesian inverse problems. Report 2011-16, Seminar for Applied Mathematics, ETH Zürich (to appear in Inverse Probl.). | MR 2903278 | Zbl 1236.62014

and[25] Karhúnen-Loève, Approximation of random fields by generalized fast multipole methods. J. Comput. Phys. 217 (2000) 100-122. | MR 2250527 | Zbl 1104.65008

and ,[26] Optimality of a standard adaptive finite element method. Found. Comput. Math. 7 (2007) 245-269. | MR 2324418 | Zbl 1136.65109

,