Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: application to random elliptic PDEs

F. Nobile, L. Tamellini, Raul Tempone

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


In this work we provide a convergence analysis for the quasi-optimal version of the sparse-grids stochastic collocation method we presented in a previous work: “On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods” (Beck et al., Math Models Methods Appl Sci 22(09), 2012). The construction of a sparse grid is recast into a knapsack problem: a profit is assigned to each hierarchical surplus and only the most profitable ones are added to the sparse grid. The convergence rate of the sparse grid approximation error with respect to the number of points in the grid is then shown to depend on weighted summability properties of the sequence of profits. This is a very general argument that can be applied to sparse grids built with any uni-variate family of points, both nested and non-nested. As an example, we apply such quasi-optimal sparse grids to the solution of a particular elliptic PDE with stochastic diffusion coefficients, namely the “inclusions problem”: we detail the convergence estimates obtained in this case using polynomial interpolation on either nested (Clenshaw–Curtis) or non-nested (Gauss–Legendre) abscissas, verify their sharpness numerically, and compare the performance of the resulting quasi-optimal grids with a few alternative sparse-grid construction schemes recently proposed in the literature.
Original languageEnglish (US)
Pages (from-to)343-388
Number of pages46
JournalNumerische Mathematik
Issue number2
StatePublished - Oct 30 2015

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The authors would like to recognize the support of King Abdullah University of Science and Technology (KAUST) AEA project "Predictability and Uncertainty Quantification for Models of Porous Media" and University of Texas at Austin AEA Rnd 3 "Uncertainty quantification for predictive mobdeling of the dissolution of porous and fractured media". F. Nobile and L. Tamellini have been partially supported by the Italian grant FIRB-IDEAS (Project n. RBID08223Z) "Advanced numerical techniques for uncertainty quantification in engineering and life science problems" and by the Swiss National Science Foundation under the Project No. 140574 "Efficient numerical methods for flow and transport phenomena in heterogeneous random porous media". They also received partial support from the Center for ADvanced MOdeling Science (CADMOS). R. Tempone is a member of the KAUST SRI Center for Uncertainty Quantification in Computational Science and Engineering. We acknowledge the usage of the Matlab (R) functions patterson_rule.m by J. Burkardt ( to jburkardt/m_src/patterson_rule/patterson_rule.html) for the computation of Gauss-Patterson points and lejapoints. m by M. Caliari ( to caliari/software/lejapoints.m) for the computation of symmetrized Leja points.


Dive into the research topics of 'Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-valued functions: application to random elliptic PDEs'. Together they form a unique fingerprint.

Cite this