Kolmogorov widths and low-rank approximations of parametric elliptic PDEs
Authors:
Markus Bachmayr and Albert Cohen
Journal:
Math. Comp. 86 (2017), 701-724
MSC (2010):
Primary 35C10, 41A46; Secondary 41A63, 65Nxx
DOI:
https://doi.org/10.1090/mcom/3132
Published electronically:
July 20, 2016
MathSciNet review:
3584545
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: Kolmogorov $n$-widths and low-rank approximations are studied for families of elliptic diffusion PDEs parametrized by the diffusion coefficients. The decay of the $n$-widths can be controlled by that of the error achieved by best $n$-term approximations using polynomials in the parametric variable. However, we prove that in certain relevant instances where the diffusion coefficients are piecewise constant over a partition of the physical domain, the $n$-widths exhibit significantly faster decay. This, in turn, yields a theoretical justification of the fast convergence of reduced basis or POD methods when treating such parametric PDEs. Our results are confirmed by numerical experiments, which also reveal the influence of the partition geometry on the decay of the $n$-widths.
- Roman Andreev and Christoph Schwab, Sparse tensor approximation of parametric eigenvalue problems, Numerical analysis of multiscale problems, Lect. Notes Comput. Sci. Eng., vol. 83, Springer, Heidelberg, 2012, pp. 203–241. MR 3050915, DOI https://doi.org/10.1007/978-3-642-22061-6_7
- Markus Bachmayr and Wolfgang Dahmen, Adaptive near-optimal rank tensor approximation for high-dimensional operator equations, Found. Comput. Math. 15 (2015), no. 4, 839–898. MR 3371372, DOI https://doi.org/10.1007/s10208-013-9187-3
- Jonas Ballani and Lars Grasedyck, Hierarchical tensor approximation of output quantities of parameter-dependent PDEs, SIAM/ASA J. Uncertain. Quantif. 3 (2015), no. 1, 852–872. MR 3400031, DOI https://doi.org/10.1137/140960980
- Joakim Beck, Raul Tempone, Fabio Nobile, and Lorenzo Tamellini, On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods, Math. Models Methods Appl. Sci. 22 (2012), no. 9, 1250023, 33. MR 2974161, DOI https://doi.org/10.1142/S0218202512500236
- Joakim Beck, Fabio Nobile, Lorenzo Tamellini, and Raúl Tempone, Convergence of quasi-optimal stochastic Galerkin methods for a class of PDES with random coefficients, Comput. Math. Appl. 67 (2014), no. 4, 732–751. MR 3163876, DOI https://doi.org/10.1016/j.camwa.2013.03.004
- Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods, SIAM J. Math. Anal. 43 (2011), no. 3, 1457–1472. MR 2821591, DOI https://doi.org/10.1137/100795772
- A. Chkifa, A. Cohen, R. DeVore and C. Schwab, Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs, M2AN 47 (2013), 253–283.
- Albert Cohen and Ronald DeVore, Kolmogorov widths under holomorphic mappings, IMA J. Numer. Anal. 36 (2016), no. 1, 1–12. MR 3463432, DOI https://doi.org/10.1093/imanum/dru066
- Albert Cohen and Ronald DeVore, Approximation of high-dimensional parametric PDEs, Acta Numer. 24 (2015), 1–159. MR 3349307, DOI https://doi.org/10.1017/S0962492915000033
- Albert Cohen, Ronald DeVore, and Christoph Schwab, Convergence rates of best $N$-term Galerkin approximations for a class of elliptic sPDEs, Found. Comput. Math. 10 (2010), no. 6, 615–646. MR 2728424, DOI https://doi.org/10.1007/s10208-010-9072-2
- Albert Cohen, Ronald Devore, and Christoph Schwab, Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s, Anal. Appl. (Singap.) 9 (2011), no. 1, 11–47. MR 2763359, DOI https://doi.org/10.1142/S0219530511001728
- Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI https://doi.org/10.1017/S0962492900002816
- Ronald DeVore, Guergana Petrova, and Przemyslaw Wojtaszczyk, Greedy algorithms for reduced bases in Banach spaces, Constr. Approx. 37 (2013), no. 3, 455–466. MR 3054611, DOI https://doi.org/10.1007/s00365-013-9186-2
- Christoph Schwab and Claude Jeffrey Gittelson, Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs, Acta Numer. 20 (2011), 291–467. MR 2805155, DOI https://doi.org/10.1017/S0962492911000055
- Martin Kahlbacher and Stefan Volkwein, Galerkin proper orthogonal decomposition methods for parameter dependent elliptic systems, Discuss. Math. Differ. Incl. Control Optim. 27 (2007), no. 1, 95–117. MR 2413807, DOI https://doi.org/10.7151/dmdico.1078
- Boris N. Khoromskij and Christoph Schwab, Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs, SIAM J. Sci. Comput. 33 (2011), no. 1, 364–385. MR 2783199, DOI https://doi.org/10.1137/100785715
- Daniel Kressner and Christine Tobler, Low-rank tensor Krylov subspace methods for parametrized linear systems, SIAM J. Matrix Anal. Appl. 32 (2011), no. 4, 1288–1316. MR 2854614, DOI https://doi.org/10.1137/100799010
- Toni Lassila, Andrea Manzoni, Alfio Quarteroni, and Gianluigi Rozza, Generalized reduced basis methods and $n$-width estimates for the approximation of the solution manifold of parametric PDEs, Analysis and numerics of partial differential equations, Springer INdAM Ser., vol. 4, Springer, Milan, 2013, pp. 307–329. MR 3051406, DOI https://doi.org/10.1007/978-88-470-2592-9_16
- G. Rozza, D. B. P. Huynh, and A. T. Patera, 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 Eng. 15 (2008), no. 3, 229–275. MR 2430350, DOI https://doi.org/10.1007/s11831-008-9019-9
Retrieve articles in Mathematics of Computation with MSC (2010): 35C10, 41A46, 41A63, 65Nxx
Retrieve articles in all journals with MSC (2010): 35C10, 41A46, 41A63, 65Nxx
Additional Information
Markus Bachmayr
Affiliation:
Sorbonne Universités, UPMC Université Paris 06, CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, 4, place Jussieu, 75005 Paris, France
MR Author ID:
881952
Email:
bachmayr@ljll.math.upmc.fr
Albert Cohen
Affiliation:
Sorbonne Universités, UPMC Université Paris 06, CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, 4, place Jussieu, 75005 Paris, France
MR Author ID:
308419
Email:
cohen@ann.jussieu.fr
Received by editor(s):
February 10, 2015
Received by editor(s) in revised form:
September 22, 2015
Published electronically:
July 20, 2016
Additional Notes:
This research was supported by the European Research Council under grant ERC AdG BREAD
Article copyright:
© Copyright 2016
American Mathematical Society