Abstract
We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.
Similar content being viewed by others
References
R. Andreev, M. Bieri, Ch. Schwab, Sparse tensor discretization of elliptic sPDEs, SIAM J. Sci. Comput. 31, 4281–4304 (2009).
R. Andreev, Ch. Schwab, Sparse Tensor Approximation of Parametric Eigenvalue Problems in Numerical Analysis of Multiscale Problems. Lecture Notes in Comp. Sci. Eng., vol. 83, ed. by I.G. Graham, T.Y. Hou, O. Lakkis, R. Scheichl (Springer, Berlin, 2011), pp. 203–242.
I. Babuška, F. Nobile, R. Tempone, A stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 45, 1005–1034 (2007).
I. Babuska, R. Tempone, G.E. Zouraris, Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. Numer. Anal. 42, 800–825 (2004).
J. Bäck, F. Nobile, L. Tamellini, R. Tempone, On the optimal polynomial approximation of stochastic PDEs by Galerkin and Collocation methods, MOX Report 23/2011, Math. Mod. Methods Appl. Sci. 22(9), 1250023 (2012).
V. Barthelmann, E. Novak, K. Ritter, High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12(4), 273–288 (2000).
A. Buffa, Y. Maday, A.T. Patera, C. Prudhomme, G. Turinici, A priori convergence of the greedy algorithm for the parameterized reduced basis, Modél. Math. Anal. Numér. 46(3), 595–603 (2012).
J.P. Calvi, V.M. Phung, On the Lebesgue constant of Leja sequences for the unit disk and its applications to multivariate interpolation, J. Approx. Theory 163(5), 608–622 (2011).
J.P. Calvi, V.M. Phung, Lagrange interpolation at real projections of Leja sequences for the unit disk, Proc. Amer. Math. Soc. 140, 4271–4284 (2012).
A. Chkifa, On the Lebesgue constant of Leja sequences for the complex unit disk and of their real projection. Preprint Laboratoire Jacques-Louis Lions, J. Approx. Theory 166, 176–200 (2013).
A. Chkifa, A. Cohen, R. DeVore, Ch. Schwab, Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs, Modél. Math. Anal. Numér. 47(1), 253–280 (2013).
A. Cohen, R. DeVore, Ch. Schwab, Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs, J. Found. Comput. Math. 10(6), 615–646 (2010).
A. Cohen, R. DeVore, Ch. Schwab, Analytic regularity and polynomial approximation of parametric and stochastic PDE’s, Anal. Appl. 9, 1–37 (2011).
D. Coppersmith, T.J. Rivlin, The growth of polynomials bounded at equally spaced points, SIAM J. Math. Anal. 23(4), 970–983 (1992).
C. de Boor, A. Ron, Computational aspects of polynomial interpolation in several variables, Math. Comput. 58, 705–727 (1992).
N. Dyn, M. Floater, Multivariate polynomial interpolation on monotone sets, preprint, University of Oslo (2013).
Ph. Frauenfelder, Ch. Schwab, R.A. Todor, Finite elements for elliptic problems with stochastic coefficients, Comput. Methods Appl. Mech. Eng. 194, 205–228 (2005).
C.J. Gittelson, An adaptive stochastic Galerkin method for random elliptic operators, Math. Comp. 82, 1515–1541 (2013).
T. Gerster, M. Griebel, Dimension-adaptive tensor-product quadrature, Computing 71(1), 65–87 (2003).
M. Hansen, Ch. Schwab, Analytic regularity and nonlinear approximation of a class of parametric semilinear elliptic PDEs, Mathematische Nachrichten (2013).
M. Hansen, Ch. Schwab, Analytic regularity and best N-term approximation of high dimensional parametric initial value problems, Vietnam J. Math. (2013, to appear).
V.H. Hoang, Ch. Schwab, 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).
V.H. Hoang, Ch. Schwab, Analytic regularity and gpc approximation for parametric and random 2nd order hyperbolic PDEs, Analysis and Applications (Singapore) 10(3) (2012). doi:10.1142/S0219530512500145.
M. Kleiber, T.D. Hien, The Stochastic Finite Element Methods (Wiley, Chichester, 1992).
J. Kuntzman, Méthodes numériques—Interpolation, dérivées (Dunod, Paris, 1959).
G. Lorentz, R. Lorentz, Solvability problems of bivariate interpolation I, Constr. Approx. 2, 153–169 (1986).
G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Analysis of the discrete L 2 projection on polynomial spaces with random evaluations. Report 46/2011, MOX, Politechnico di Milano.
R. Milani, A. Quarteroni, G. Rozza, Reduced basis methods in linear elasticity with many parameters, Comput. Methods Appl. Mech. Eng. 197, 4812–4829 (2008).
V. Nistor, Ch. Schwab, High order Galerkin approximations for parametric, second order elliptic partial differential equations. Report 2012-22, Seminar for Applied Mathematics, ETH Zürich (to appear in Math. Models Methods Appl. Sci. 2013).
F. Nobile, R. Tempone, C.G. Webster, A sparse grid stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 46, 2309–2345 (2008).
F. Nobile, R. Tempone, C.G. Webster, An anisotropic sparse grid stochastic collocation method for elliptic partial differential equations with random input data, SIAM J. Numer. Anal. 46, 2411–2442 (2008).
S. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR 4, 240–243 (1963).
Acknowledgements
Research supported by the Swiss National Science Foundation under Grant SNF 200021-120290/1 and by the European Research Council under grant ERC AdG247277.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Wolfgang Dahmen.
Rights and permissions
About this article
Cite this article
Chkifa, A., Cohen, A. & Schwab, C. High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs. Found Comput Math 14, 601–633 (2014). https://doi.org/10.1007/s10208-013-9154-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-013-9154-z
Keywords
- Parametric and stochastic PDEs
- Sparse polynomial approximation
- High-dimensional problems
- Adaptive algorithms
- Lebesgue constants
- Leja points