Double greedy algorithms: Reduced basis methods for transport dominated problems
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 3, p. 623-663
The full text of recent articles is available to journal subscribers only. See the article on the journal's website

The central objective of this paper is to develop reduced basis methods for parameter dependent transport dominated problems that are rigorously proven to exhibit rate-optimal performance when compared with the Kolmogorov n-widths of the solution sets. The central ingredient is the construction of computationally feasible “tight” surrogates which in turn are based on deriving a suitable well-conditioned variational formulation for the parameter dependent problem. The theoretical results are illustrated by numerical experiments for convection-diffusion and pure transport equations. In particular, the latter example sheds some light on the smoothness of the dependence of the solutions on the parameters.

DOI : https://doi.org/10.1051/m2an/2013103
Classification:  65J10,  65N12,  65N15,  35B30
Keywords: tight surrogates, stable variational formulations, saddle point problems, double greedy schemes, greedy stabilization, rate-optimality, transport equations, convection-diffusion equations
@article{M2AN_2014__48_3_623_0,
author = {Dahmen, Wolfgang and Plesken, Christian and Welper, Gerrit},
title = {Double greedy algorithms: Reduced basis methods for transport dominated problems},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {48},
number = {3},
year = {2014},
pages = {623-663},
doi = {10.1051/m2an/2013103},
zbl = {1291.65339},
mrnumber = {3177860},
language = {en},
url = {http://www.numdam.org/item/M2AN_2014__48_3_623_0}
}

Dahmen, Wolfgang; Plesken, Christian; Welper, Gerrit. Double greedy algorithms: Reduced basis methods for transport dominated problems. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 3, pp. 623-663. doi : 10.1051/m2an/2013103. http://www.numdam.org/item/M2AN_2014__48_3_623_0/

[1] P. Binev, A. Cohen, W. Dahmen, R. Devore, G. Petrova and P. Wojtaszczyk, Convergence Rates for Greedy Algorithms in Reduced Basis Methods. SIAM J. Math. Anal. 43 (2011) 1457-1472. | MR 2821591 | Zbl 1229.65193

[2] F. Brezzi and M. Fortin, Mixed and Hybrid Finite Element Methods, in vol. 15 of Springer Ser. Comput. Math. Springer-Verlag (1991). | MR 1115205 | Zbl 0788.73002

[3] A. Buffa, Y. Maday, A.T. Patera, C. Prud'Homme and G. Turinici, A Priori convergence of the greedy algorithm for the parameterized reduced basis. ESAIM: M2AN 46 (2012) 595-603. | Numdam | MR 2877366 | Zbl 1272.65084

[4] J.M. Cascon, C. Kreuzer, R.H. Nochetto and K.G. Siebert, Quasi-optimal convergence rate for an adaptive finite element method. SIAM J. Numer. Anal. 46 (2008) 2524-2550. | MR 2421046 | Zbl 1176.65122

[5] A. Cohen, W. Dahmen and G. Welper, Adaptivity and Variational Stabilization for Convection-Diffusion Equations. ESAIM: M2AN 46 (2012) 1247-1273. | Numdam | MR 2916380 | Zbl 1270.65065

[6] W. Dahmen, Parameter dependent transport equations, in Workshop J.L.L.-SMP: Reduced Basis Methods in High Dimensions. Available at http://www.ljll.math.upmc.fr/fr/archives/actualites/2011/workshop˙ljll˙smp˙rbihd.html

[7] W. Dahmen, C. Huang, C. Schwab and G. Welper, Adaptive Petrov−Galerkin methods for first order transport equations. SIAM J. Numer. Anal. 50 (2012) 2420-2445. | MR 3022225 | Zbl 1260.65091

[8] L.F. Demkowicz and J. Gopalakrishnan, A class of discontinuous Petrov−Galerkin Methods I: The transport equation. Comput. Methods Appl. Mech. Engrg. 199 (2010) 1558-1572. | MR 2630162 | Zbl 1231.76142

[9] L. Demkowicz and J. Gopalakrishnan, A class of discontinuous Petrov−Galerkin methods. Part II: Optimal test functions. Numer. Methods for Partial Differ. Equ. 27 (2011) 70-105. | MR 2743600 | Zbl 1208.65164

[10] S. Deparis, Reduced basis error bound computation of parameter-dependent Navier-Stokes equations by the natural norm approach. SIAM J. Numer. Anal. 46 (2008) 2039-2067. | MR 2399407 | Zbl 1177.35148

[11] R. Devore, G. Petrova and P. Wojtaszczyk, Greedy algorithms for reduced bases in Banach spaces, Constructive Approximation 37 (2013) 455-466. | MR 3054611 | Zbl 1276.41021

[12] A. Ern and J.-L. Guermond, Theory and practice of finite elements. Springer (2004). | MR 2050138 | Zbl 1059.65103

[13] A. Gerner and K. Veroy-Grepl, Certified reduced basis methods for parametrized saddle point problems, preprint (2012). To appear in SIAM J. Sci. Comput. | MR 3023727 | Zbl 1255.76024

[14] A.-L. Gerner and K. Veroy, Reduced basis a posteriori error bounds for the Stokes equations in parameterized domains: A penalty approach. M3AS: Math. Models Methods Appl. Sci. 21 (2011) 2103-2134. | MR 2851708 | Zbl pre06045578

[15] M.A. Grepl, Certified Reduced Basis Methods for Nonaffine Linear Time-Varying and Nonlinear Parabolic Partial Differential Equations. M3AS: Math. Models Methods Appl. Sci. 22 (2012) 40. | MR 2890453 | Zbl 1241.35116

[16] M.A. Grepl and A.T. Patera, A Posteriori Error Bounds for Reduced-Basis Approximations of Parametrized Parabolic Partial Differential Equations. ESAIM: M2AN 39 (2005) 157-181. | Numdam | MR 2136204 | Zbl 1079.65096

[17] B. Haasdonk, Convergence rates for the POD-greedy method. ESAIM: M2AN 47 (2013) 859-873. | Numdam | MR 3056412 | Zbl 1277.65074

[18] T. Hughes and G. Sangalli, Variational Multiscale Analysis: the Fine-scale Green's Function, Projection, Optimization, Localization, and Stabilized Methods. SIAM J. Numer. Anal. 45 (2007) 539-557. | MR 2300286 | Zbl 1152.65111

[19] G. Kanschat, E. Meinköhn, R. Rannacher and R. Wehrse, Numerical methods in multidimensional radiative transfer, Springer (2009). | MR 2530844 | Zbl 1155.65004

[20] G.G. Lorentz, M. Von Golitschek and Yu. Makovoz, Constructive approximation: Advanced problems, vol. 304. Springer Grundlehren, Berlin (1996). | MR 1393437 | Zbl 0910.41001

[21] Y. Maday, A.T. Patera and G. Turinici, A priori convergence theory for reduced-basis approximations of single-parametric elliptic partial differential equations. J. Sci. Comput. 17 (2002) 437-446. | MR 1910581 | Zbl 1014.65115

[22] T. Manteuffel, S. Mccormick, J. Ruge and J.G. Schmidt, First-order system ℒℒ∗ (FOSLL)∗ for general scalar elliptic problems in the plane. SIAM J. Numer. Anal. 43 (2005) 2098-2120. | MR 2192333 | Zbl 1103.65117

[23] N.-C. Nguyen, G. Rozza and A.T. Patera, Reduced basis approximation for the time-dependent viscous Burgers' equation. Calcolo 46 (2009) 157-185. | MR 2533748 | Zbl 1178.65109

[24] T. Patera and K. Urban, An improved error bound for reduced basis approximation of linear parabolic problems, submitted to Mathematics of Computation (in press 2013). | Zbl pre06300438

[25] A.T. Patera and G. Rozza, Reduced Basis Approximation and a Posteriori Error Estimation for Parametrized Partial Differential Equations, Version 1.0, Copyright MIT 2006-2007, to appear in (tentative rubric) MIT Pappalardo Graduate Monographs in Mechanical Engineering. | Zbl pre05344486

[26] H.-J. Roos, M. Stynes and L. Tobiska, Robust Numerical Methods for Singularly Perturbed Differential Equations, in vol. 24 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, 2nd Edition (2008). | MR 2454024 | Zbl 1155.65087

[27] G. Rozza and D.B.P. Huynh and A. Manzoni, Reduced basis approximation and a posteriori error estiamtion for Stokes flows in parametrized geometries: roles of the inf-sup stability constants, Numer. Math. DOI: 10.1007/s00211-013-0534-8. | MR 3090657 | Zbl pre06210474

[28] 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. Arch. Comput. Methods Eng. 15 (2008) 229-275. | MR 2430350 | Zbl pre05344486

[29] G. Rozza and K. Veroy, On the stability of reduced basis techniques for Stokes equations in parametrized domains. Comput. Methods Appl. Mechanics Engrg. 196 (2007) 1244-1260. | MR 2281777 | Zbl 1173.76352

[30] G. Sangalli, A uniform analysis of non-symmetric and coercive linear operators. SIAM J. Math. Anal. 36 (2005) 2033-2048. | MR 2178232 | Zbl 1114.35060

[31] M. Schlottbom, On Forward and Inverse Models in Optical Tomography, Ph.D. Thesis. RWTH Aachen (2011).

[32] S. Sen, K. Veroy, D.B.P. Huynh, S. Deparis, N.C. Nguyn and A.T. Patera, Natural norm a posteriori error estimators for reduced basis approximations. J. Comput. Phys. 217 (2006) 37-62. | MR 2250524 | Zbl 1100.65094

[33] R. Verfürth, Robust a posteriori error estimates for stationary convection-diffusion equations. SIAM J. Numer. Anal. 43 (2005) 1766-1782. | MR 2182149 | Zbl 1099.65100

[34] G. Welper, Infinite dimensional stabilization of convection-dominated problems, Ph.D. Thesis. RWTH Aachen (2012).

[35] J. Zitelli, I. Muga, L. Demkowicz, J. Gopalakrishnan, D. Pardo and V. Calo, A class of discontinuous Petrov−Galerkin methods. Part IV: Wave propagation. J. Comput. Phys. 230 (2011) 2406-2432. | MR 2772923 | Zbl pre05909482