Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T12:40:10.421Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximation of high-dimensional parametric PDEs*

Published online by Cambridge University Press:  27 April 2015

Albert Cohen  and
Ronald DeVore
Albert Cohen
Affiliation:
Laboratoire Jacques-Louis Lions, Université Pierre et Marie Curie, 75005 Paris, France E-mail: [email protected]
Ronald DeVore
Affiliation:
Department of Mathematics, Texas A&M University, College Station, TX 77840, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Parametrized families of PDEs arise in various contexts such as inverse problems, control and optimization, risk assessment, and uncertainty quantification. In most of these applications, the number of parameters is large or perhaps even infinite. Thus, the development of numerical methods for these parametric problems is faced with the possible curse of dimensionality. This article is directed at (i) identifying and understanding which properties of parametric equations allow one to avoid this curse and (ii) developing and analysing effective numerical methods which fully exploit these properties and, in turn, are immune to the growth in dimensionality.

Part I of this article studies the smoothness and approximability of the solution map, that is, the map $a\mapsto u(a)$, where $a$ is the parameter value and $u(a)$ is the corresponding solution to the PDE. It is shown that for many relevant parametric PDEs, the parametric smoothness of this map is typically holomorphic and also highly anisotropic, in that the relevant parameters are of widely varying importance in describing the solution. These two properties are then exploited to establish convergence rates of $n$-term approximations to the solution map, for which each term is separable in the parametric and physical variables. These results reveal that, at least on a theoretical level, the solution map can be well approximated by discretizations of moderate complexity, thereby showing how the curse of dimensionality is broken. This theoretical analysis is carried out through concepts of approximation theory such as best $n$-term approximation, sparsity, and $n$-widths. These notions determine a priori the best possible performance of numerical methods and thus serve as a benchmark for concrete algorithms.

Part II of this article turns to the development of numerical algorithms based on the theoretically established sparse separable approximations. The numerical methods studied fall into two general categories. The first uses polynomial expansions in terms of the parameters to approximate the solution map. The second one searches for suitable low-dimensional spaces for simultaneously approximating all members of the parametric family. The numerical implementation of these approaches is carried out through adaptive and greedy algorithms. An a priori analysis of the performance of these algorithms establishes how well they meet the theoretical benchmarks.

Type
Research Article
Information
Acta Numerica , Volume 24 , 01 May 2015 , pp. 1 - 159
Copyright
© Cambridge University Press, 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Andreev, R., Bieri, M. and Schwab, C. (2006), ‘Sparse tensor discretization of elliptic SPDEs’, SIAM J. Sci. Comput. 31, 4281–4304.Google Scholar
Babuška, I., Nobile, F. and Tempone, R. (2007), ‘A stochastic collocation method for elliptic partial differential equations with random input data’, SIAM J. Numer. Anal. 45, 1005–1034.Google Scholar
Babuška, I., Tempone, R. and Zouraris, G. E. (2004), ‘Galerkin finite element approximations of stochastic elliptic partial differential equations’, SIAM J. Numer. Anal. 42, 800–825.Google Scholar
Beck, J., Nobile, F., Tamellini, L. and Tempone, R. (2012), ‘On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods’, Math. Models Methods Appl. Sci. 22, 1–33.Google Scholar
Beck, J., Nobile, F., Tamellini, L. and Tempone, R. (2014), ‘Convergence of quasi-optimal stochastic Galerkin methods for a class of PDEs with random coefficients’, Comput. Math. Appl. 67, 732–751.CrossRefGoogle Scholar
Bergmann, M. and Cordier, L. (2003), Proper Orthogonal Decomposition: An Overview; Post Processing of Experimental and Numerical Data, Lecture Series 2003/2004, von Karman Institut for Fluid Dynamics.Google Scholar
Binev, P., Cohen, A., Dahmen, W., DeVore, R., Petrova, G. and Wojtaszczyk, P. (2011), ‘Convergence rates for greedy algorithms in reduced basis methods’, SIAM J. Math. Anal. 43, 1457–1472.CrossRefGoogle Scholar
Binev, P., Dahmen, W. and DeVore, R. (2004), ‘Adaptive finite element methods with convergence rates’, Numer. Math. 97, 219–268.Google Scholar
de Boor, C. and Ron, A. (1992), ‘Computational aspects of polynomial interpolation in several variables’, Math. Comp. 58, 705–727.CrossRefGoogle Scholar
Brenner, S. and Scott, L. R. (2008), The Mathematical Theory of Finite Elements, second edition, Springer.Google Scholar
Buffa, A., Maday, Y., Patera, A. T., Prud’homme, C. and Turinici, G. (2012), ‘ A priori convergence of the greedy algorithm for the parameterized reduced basis’, Math. Model. Numer. Anal. 46, 595–603.CrossRefGoogle Scholar
Bungartz, H.-J. and Griebel, M. (2004), Sparse grids. In Acta Numerica, Vol. 13, Cambridge University Press, pp. 1–123.Google Scholar
Calvi, J. P. and Phung, V. M. (2011), ‘On the Lebesgue constant of Leja sequences for the unit disk and its applications to multivariate interpolation’, J. Approx. Theory 163, 608–622.CrossRefGoogle Scholar
Calvi, J. P. and Phung, V. M. (2012), ‘Lagrange interpolation at real projections of Leja sequences for the unit disk’, Proc. Amer. Math. Soc. 140, 4271–4284.Google Scholar
Canfield, E. R., Erdős, P. and Pomerance, C. (1983), ‘On a problem of Oppenheim concerning “factorisatio numerorum”’, J. Number Theory 17, 1–28.Google Scholar
Chkifa, A. (2013), ‘On the Lebesgue constant of Leja sequences for the complex unit disk and of their real projection’, J. Approx. Theory 166, 176–200.CrossRefGoogle Scholar
Chkifa, A. (2015), New bounds on the Lebesgue constant of Leja sequences on the unit disc and their projections $\mathfrak{R}$ -Leja sequences. arXiv:1503.01731 Google Scholar
Chkifa, A., Cohen, A., DeVore, R. and Schwab, C. (2013), ‘Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs’, Math. Model. Numer. Anal. 47, 253–280.Google Scholar
Chkifa, A., Cohen, A., Migliorati, G., Nobile, F. and Tempone, R. (2015a), ‘Discrete least squares polynomial approximation with random evaluations: Application to parametric and stochastic PDEs’, Math. Model. Numer. Anal. doi:10.1051/m2an/2014050 CrossRefGoogle Scholar
Chkifa, A., Cohen, A. and Schwab, C. (2014), ‘High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs’, Found. Comput. Math. 14, 601–633.CrossRefGoogle Scholar
Chkifa, A., Cohen, A. and Schwab, C. (2015b), ‘Breaking the curse of dimensionality in parametric PDEs’, J. Math. Pures Appliquées 102, 400–428.Google Scholar
Ciarlet, P. G. (1978), The Finite Element Method for Elliptic Problems, Elsevier.Google Scholar
Cohen, A. and DeVore, R. (2015), Kolmogorov widths under holomorphic mappings. IMA J. Numer. Anal. doi:10.1093/imanum/dru066 Google Scholar
Cohen, A., Dahmen, W. and DeVore, R. (2000), ‘Adaptive wavelet methods for elliptic operator equations: Convergence rates’, Math. Comp. 70, 27–75.CrossRefGoogle Scholar
Cohen, A., Dahmen, W. and DeVore, R. (2002), ‘Adaptive wavelet methods for operator equations: Beyond the elliptic case’, Found. Comput. Math. 2, 203–245.CrossRefGoogle Scholar
Cohen, A., DeVore, R. and Schwab, C. (2010), ‘Convergence rates of best $N$ -term Galerkin approximations for a class of elliptic sPDEs’, Found. Comput. Math. 10, 615–646.CrossRefGoogle Scholar
Cohen, A., DeVore, R. and Schwab, C. (2011), ‘Analytic regularity and polynomial approximation of parametric and stochastic PDEs’, Anal. Appl. 9, 11–47.CrossRefGoogle Scholar
Constantine, P., Eldred, M. and Phipps, E. (2012), ‘Sparse pseudospectral approximation method’, Comput. Methods Appl. Mech. Engrg 229–232, 1–12.Google Scholar
Dautray, R. and Lions, J.-L. (1992), Mathematical Analysis and Numerical Methods for Science and Technology, Springer.Google Scholar
Davis, P. J. (1963), Interpolation and Approximation, Blaisdell.Google Scholar
DeVore, R. (1998), Nonlinear approximation. In Acta Numerica, Vol. 7, Cambridge University Press, pp. 51–150.Google Scholar
DeVore, R., Petrova, G. and Wojtaszczyk, P. (2013), ‘Greedy algorithms for reduced bases in Banach spaces’, Constr. Approx. 37, 455–466.Google Scholar
Dieudonné, J. (1969), Treatise on Analysis, Vol. I, Academic Press.Google Scholar
Doostan, A. and Iaccarino, G. (2009), ‘A least-squares approximation of partial differential equations with high-dimensional random inputs’, J. Comput. Phys. 228, 4332–4345.CrossRefGoogle Scholar
Doostan, A. and Owadi, H. (2011), ‘A non-adapted sparse approximation of PDEs with stochastic inputs’, J. Comput. Phys. 230, 3015–3034.Google Scholar
Dörfler, W. (1996), ‘A convergent adaptive algorithm for Poisson’s equation’, SIAM J. Numer. Anal. 33, 1106–1124.Google Scholar
Frauenfelder, P., Schwab, C. and Todor, R. A. (2005), ‘Finite elements for elliptic problems with stochastic coefficients’, Comput. Methods Appl. Mech. Engrg 194, 205–228.Google Scholar
Gantumur, T., Harbrecht, H. and Stevenson, R. (2007), ‘An optimal adaptive wavelet method without coarsening of the iterands’, Math. Comp. 76, 615–629.Google Scholar
Gerstner, T. and Griebel, M. (2003), ‘Dimension-adaptive tensor-product quadrature’, Computing 71, 65–87.Google Scholar
Ghanem, R. and Spanos, P. (1991), Stochastic Finite Elements: A Spectral Approach, Springer.CrossRefGoogle Scholar
Ghanem, R. and Spanos, P. (1997), ‘Spectral techniques for stochastic finite elements’, Arch. Comput. Methods Engrg 4, 63–100.Google Scholar
Gittelson, G. J. (2010), ‘Stochastic Galerkin discretization of the log-normal isotropic diffusion problem’, Math. Models Methods Appl. Sci. 20, 237–263..Google Scholar
Gittelson, C. J. (2013), ‘An adaptive stochastic Galerkin method’, Math. Comp. 82, 1515–1541.Google Scholar
Gittelson, C. J. and Schwab, C. (2011), Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs. In Acta Numerica, Vol. 20, Cambridge University Press, pp. 291–467.Google Scholar
Graham, I., Kuo, F., Nichols, J., Scheichl, R., Schwab, C. and Sloan, I. (2015), ‘Quasi-Monte Carlo finite element methods for elliptic PDEs with log-normal random coefficient’, Numer. Math. doi:10.1007/s00211-014-0689-y Google Scholar
Gunzburger, M., Webster, C. and Zhang, G. (2014), Stochastic finite element methods for partial differential equations with random input data. In Acta Numerica, Vol. 23, Cambridge University Press, pp. 521–650.Google Scholar
Hansen, M. and Schwab, C. (2013a), ‘Analytic regularity and nonlinear approximation of a class of parametric semilinear elliptic PDEs’, Math. Nachr. 286, 832–860.Google Scholar
Hansen, M. and Schwab, C. (2013b), ‘Sparse adaptive approximation of high-dimensional parametric initial value problems’, Vietnam J. Math. 41, 181–215.Google Scholar
Hervé, M. (1989), Analyticity in Infinite Dimensional Spaces, De Gruyter.Google Scholar
Hoang, V. H. and Schwab, C. (2014), ‘ $n$ -term Wiener chaos approximation rates for elliptic PDEs with lognormal Gaussian random inputs’, Math. Models Methods Appl. Sci. 24, 797–826.Google Scholar
Jerison, D. and Kenig, C. E. (1995), ‘The inhomogeneous Dirichlet problem in Lipschitz domains’, J. Funct. Anal. 130, 161–219.Google Scholar
Kahlbacher, M. and Volkwein, S. (2007), ‘Galerkin proper orthogonal decomposition methods for parameter dependent elliptic systems’, Discuss. Math. Differ. Incl. Control Optim. 27, 95–117.Google Scholar
Karniadakis, G. E. and Xiu, D. B. (2002a), ‘The Wiener–Askey polynomial chaos for stochastic differential equations’, SIAM J. Sci. Comput. 24, 619–644.Google Scholar
Karniadakis, G. E. and Xiu, D. (2002b), ‘Modeling uncertainty in steady state diffusion problems via generalized polynomial chaos’, Comput. Methods Appl. Mech. Engrg 191, 4927–4948.Google Scholar
Kleiber, M. and Hien, T. D. (1992), The Stochastic Finite Element Methods, Wiley.Google Scholar
Knio, O. and Le Maitre, O. (2010), Spectral Methods for Uncertainty Quantication: With Applications to Computational Fluid Dynamics, Springer.Google Scholar
Kolmogorov, A. (1936), ‘Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse’, Ann. of Math. 37, 107–110.Google Scholar
Kunoth, A. and Schwab, C. (2013), ‘Analytic regularity and GPC approximation for control problems constrained by linear parametric elliptic and parabolic PDEs’, SIAM J. Control Optim. 51, 2442–2471.CrossRefGoogle Scholar
Kuntzman, J. (1959), Méthodes Numériques: Interpolation, Dérivées, Dunod.Google Scholar
Kuo, F. Y., Schwab, C. and Sloan, I. H. (2012), ‘Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients’, SIAM J. Numer. Anal. 50, 3351–3374.Google Scholar
Kuo, F. Y., Schwab, C. and Sloan, I. H. (2015), Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients’, Found. Comput. Math. doi:10.1007/s10208-014-9237-5 Google Scholar
Kuo, F. Y., Sloan, I. H., Wasilkowski, G. W. and Wozniakowski, H. (2010), ‘Liberating the dimension’, J. Complexity 26, 422–454.Google Scholar
Lorentz, G. G. and Lorentz, R. (1986), ‘Solvability problems of bivariate interpolation I’, Constr. Approx. 2, 153–169.CrossRefGoogle Scholar
Lorentz, G. G., von Golitschek, M. and Makovoz, Y. (1996), Constructive Approximation: Advanced Problems, Springer.CrossRefGoogle Scholar
Luca, F., Mukhopadhyay, A. and Srinivas, K. (2010), ‘On the Oppenheim’s “factorisatio numerorum” function’, Acta Arithmetica 142, 41–50.CrossRefGoogle Scholar
Machiels, L., Maday, Y, Oliveira, I. B., Patera, A. T. and Rovas, D. V. (2000), ‘Output bounds for reduced-basis approximations of symmetric positive definite eigenvalue problems’, C. R. Acad. Sci. Paris, Sér. I 331, 153–158.Google Scholar
Maday, Y., Patera, A. T. and Turinici, G. (2002a), ‘ A priori convergence theory for reduced-basis approximations of single-parametric elliptic partial differential equations’, J. Sci. Comput. 17, 437–446.CrossRefGoogle Scholar
Maday, Y., Patera, A. T. and Turinici, G. (2002b), ‘Global a priori convergence theory for reduced-basis approximations of single-parameter symmetric coercive elliptic partial differential equations’, C. R. Acad. Sci. Paris, Sér. I 335, 289–294.Google Scholar
Migliorati, G., Nobile, F., Tempone, R. and Von Schwerin, E. (2013), ‘Approximation of quantities of interest in stochastic PDEs by the random discrete $L^{2}$ projection on polynomial spaces’, SIAM J. Sci. Comput. 35, 1440–1460.Google Scholar
Morin, P., Nochetto, R. H. and Siebert, K. G. (2000), ‘Data oscillation and convergence of adaptive FEM’, SIAM J. Numer. Anal. 38, 466–488.Google Scholar
Nobile, F., Tempone, R. and Webster, C. G. (2008a), ‘A sparse grid stochastic collocation method for elliptic partial differential equations with random input data’, SIAM J. Numer. Anal. 46, 2309–2345.Google Scholar
Nobile, F., Tempone, R. and Webster, C. G. (2008b), ‘An anisotropic sparse grid stochastic collocation method for elliptic partial differential equations with random input data’, SIAM J. Numer. Anal. 46, 2411–2442.Google Scholar
Noor, A. K. and Peters, J. M. (1980), ‘Reduced basis technique for nonlinear analysis of structures’, AIAA J. 18, 455–462.Google Scholar
Pinkus, A. (1985), n-Widths in Approximation Theory, Springer.CrossRefGoogle Scholar
Pisier, G. (1989), The Volume of Convex Bodies and Banach Space Geometry, Cambridge University Press.Google Scholar
Rozza, G., Huynh, D. B. P. and Patera, A. T. (2008), ‘Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations: Application to transport and continuum mechanics’, Arch. Comput. Methods Engrg 15, 229–275.Google Scholar
Runst, T. and Sickel, W. (1996), Sobolev Spaces of Fractional Order, Nemytskij Operators, and Nonlinear Partial Differential Equations, De Gruyter Series in Nonlinear Analysis and Applications, De Gruyter.Google Scholar
Schillings, C. and Schwab, C. (2013), ‘Sparse, adaptive Smolyak quadratures for Bayesian inverse problems’, Inverse Problems 29, 065011.Google Scholar
Schillings, C. and Schwab, C. (2014), ‘Sparsity in Bayesian inversion of parametric operator equations’, Inverse Problems 30, 065007.Google Scholar
Sen, S. (2008), ‘Reduced-basis approximation and a posteriori error estimation for many-parameter heat conduction problems’, Numerical Heat Transfer B 54, 369–389.Google Scholar
Schwab, C. and Stevenson, R. (2009), ‘Space–time adaptive wavelet methods for parabolic evolution equations’, Math. Comp. 78, 1293–1318.Google Scholar
Schwab, C. and Stuart, A. M. (2012), ‘Sparse deterministic approximation of Bayesian inverse problems’, Inverse Problems 28, 045003.CrossRefGoogle Scholar
Schwab, C. and Todor, R. (2003), ‘Sparse finite elements for elliptic problems with stochastic loading’, Numer. Math. 95, 707–734.Google Scholar
Schwab, C. and Todor, R. (2007), ‘Convergence rates of sparse chaos approximations of elliptic problems with stochastic coefficients’, IMA J. Numer. Anal. 44, 232–261.Google Scholar
Smolyak, S. (1963), ‘Quadrature and interpolation formulas for tensor products of certain classes of functions’, Doklady Akademii Nauk SSSR 4, 240–243.Google Scholar
Stevenson, R. (2007), ‘Optimality of a standard adaptive finite element method’, Found. Comput. Math. 7, 245–269.Google Scholar
Stuart, A. M. (2010), Inverse problems: A Bayesian perspective. In Acta Numerica, Vol. 19, Cambridge University Press, pp. 451–559.Google Scholar
Veroy, K., Prud’homme, C., Rovas, D. V. and Patera, A. T. (2003), A posteriori error bounds for reduced-basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations. In Proc. 16th AIAA Computational Fluid Dynamics Conference, paper 2003-3847.Google Scholar
Xiu, D. (2007), ‘Efficient collocational approach for parametric uncertainty analysis’, Commun. Comput. Phys. 2, 293–309.Google Scholar
Xiu, D. (2010), Numerical Methods for Stochastic Computations: A Spectral Method Approach, Princeton University Press.Google Scholar