Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 1, p. 259-283
The full text of recent articles is available to journal subscribers only. See the article on the journal's website

We propose two new algorithms to improve greedy sampling of high-dimensional functions. While the techniques have a substantial degree of generality, we frame the discussion in the context of methods for empirical interpolation and the development of reduced basis techniques for high-dimensional parametrized functions. The first algorithm, based on a saturation assumption of the error in the greedy algorithm, is shown to result in a significant reduction of the workload over the standard greedy algorithm. In a further improved approach, this is combined with an algorithm in which the train set for the greedy approach is adaptively sparsified and enriched. A safety check step is added at the end of the algorithm to certify the quality of the sampling. Both these techniques are applicable to high-dimensional problems and we shall demonstrate their performance on a number of numerical examples.

DOI : https://doi.org/10.1051/m2an/2013100
Classification:  41A05,  41A46,  65N15,  65N30
Keywords: greedy algorithm, reduced basis method, empirical interpolation method
@article{M2AN_2014__48_1_259_0,
     author = {Hesthaven, Jan S. and Stamm, Benjamin and Zhang, Shun},
     title = {Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     pages = {259-283},
     doi = {10.1051/m2an/2013100},
     zbl = {1292.41001},
     mrnumber = {3177844},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2014__48_1_259_0}
}
Hesthaven, Jan S.; Stamm, Benjamin; Zhang, Shun. Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 1, pp. 259-283. doi : 10.1051/m2an/2013100. http://www.numdam.org/item/M2AN_2014__48_1_259_0/

[1] R.E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations. Math. Comput. 44 (1985) 303-320. | MR 777265 | Zbl 0569.65079

[2] M. Barrault, N.C. Nguyen, Y. Maday and A.T. Patera, An empirical interpolation method: Application to efficient reduced-basis discretization of partial differential equations. C.R. Acad. Sci. Paris, Ser. I 339 (2004) 667-672. | MR 2103208 | Zbl 1061.65118

[3] 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

[4] A. Buffa, Y. Maday, A. Patera, C. Prud'Homme and G. Turinici, A priori convergence of the greedy algorithm for the parametrized reduced basis. M2AN 46 (2012) 595-603. Special Issue in honor of David Gottlieb. | Numdam | Zbl 1272.65084

[5] T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems, MIT Thesis (2007).

[6] T. Bui-Thanh, K. Willcox and O. Ghattas, Model reduction for large-scale systems with high-dimensional parametric input space. SIAM J. Sci. Comput. 30 (2008) 3270-3288. | MR 2452388 | Zbl 1196.37127

[7] Y. Chen, J.S. Hesthaven, Y. Maday and J. Rodriguez, A monotonic evaluation of lower bounds for inf-sup stability constants in the frame of reduced basis approximations. C.R. Acad. Sci. Paris, Ser. I 346 (2008) 1295-1300. | MR 2473311 | Zbl 1152.65109

[8] Y. Chen, J.S. Hesthaven, Y. Maday and J. Rodriguez, Improved successive constraint method based a posteriori error estimate for reduced basis approximation of 2d Maxwells problem. ESAIM: M2AN 43 (2009) 1099-1116. | Numdam | MR 2588434 | Zbl 1181.78019

[9] Y. Chen, J.S. Hesthaven, Y. Maday and J. Rodriguez, Certified reduced basis methods and output bounds for the harmonic maxwell equations. SIAM J. Sci. Comput. 32 (2010) 970-996. | MR 2639602 | Zbl 1213.78011

[10] J.L. Eftang, A.T. Patera and E.M. Ronquist, An “hp” certified reduced basis method for parametrized elliptic partial differential equations. SIAM J. Sci. Comput. 32 (2010) 3170-3200. | MR 2746617 | Zbl 1228.35097

[11] J.L. Eftang and B. Stamm, Parameter multi-domain hp empirical interpolation. Int. J. Numer. Meth. Engng. 90 (2012) 412-428. | MR 2911317 | Zbl 1242.65255

[12] B. Fares, J.S. Hesthaven, Y. Maday and B. Stamm, The reduced basis method for the electric field integral equation. J. Comput. Phys. 230 (2011) 5532-5555. | MR 2799523 | Zbl 1220.78045

[13] M.A. Grepl, Y. Maday, N. C. Nguyen and A.T. Patera, Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations. Math. Model. Numer. Anal. 41 (2007) 575-605. | Numdam | MR 2355712 | Zbl 1142.65078

[14] M.A. Grepl and A.T. Patera, A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations. M2AN 39 (2005) 157-181. | Numdam | MR 2136204 | Zbl 1079.65096

[15] B. Haasdonk, M. Dihlmann and M. Ohlberger, A training set and multiple basis functions generation approach for parametrized model reduction based on adaptive grids in parameter space. Math. Comput. Modell. Dyn. Syst. 17 (2011) 423-442. | MR 2823471 | Zbl pre06287795

[16] B. Haasdonk and M. Ohlberger, Basis construction for reduced basis methods by adaptive parameter grids, in Proc. International Conference on Adaptive Modeling and Simulation 2007 (2007) 116-119.

[17] J.S. Hesthaven and S. Zhang, On the use of ANOVA expansions in reduced basis methods for high-dimensional parametric partial differential equations, Brown Division of Applied Math Scientific Computing Tech Report 2011-31.

[18] D.B.P. Huynh, G. Rozza, S. Sen and A.T. Patera, A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants. C.R. Acad. Sci. Paris, Ser. I 345 (2007) 473-478. | MR 2367928 | Zbl 1127.65086

[19] Y. Maday, N.C. Nguyen, A.T. Patera and G.S.H. Pau, A general multipurpose interpolation procedure: the magic points. Commun. Pure Appl. Anal. 8 (2009) 383-404. | MR 2449115 | Zbl 1184.65020

[20] Y. Maday and B. Stamm, Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces, arXiv: math.NA, Apr 2012, accepted in SIAM Journal on Scientific Computing. | MR 3123826 | Zbl 1285.65009

[21] 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, to appear in (tentative rubric) MIT Pappalardo Graduate Monographs in Mechanical Engineering. | Zbl pre05344486

[22] A. Quarteroni, G. Rozza and A. Manzoni, Certified reduced basis approximation for parametrized partial differential equations and applications. J. Math. Ind. 1 (2011) 3. | MR 2824231 | Zbl 1273.65148

[23] S. Repin, A Posteriori Estimates for Partial Differential Equations, Walter de Gruyter, Berlin (2008). | MR 2458008 | Zbl 1162.65001

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

[25] 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. Archives Comput. Methods Engrg. 15 (2008) 229-275. | MR 2430350 | Zbl pre05344486

[26] S. Sen, Reduced-basis approximation and a posteriori error estimation for many-parameter heat conduction problems. Numerical Heat Transfer, Part B: Fundamentals 54 (2008) 369-389.

[27] V.N. Temlyakov, Greedy Approximation. Acta Numerica (2008) 235-409. | MR 2436013 | Zbl 1178.65050

[28] K. Veroy, Reduced-Basis Methods Applied to Problems in Elasticity: Analysis and Applications, MIT Thesis (2003).

[29] K. Veroy, C. Prudhomme, D.V. Rovas and A. Patera, A posteriori error bounds for reduced basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations, in Proc. 16th AIAA Comput. Fluid Dynamics Conf. (2003). Paper 2003-3847.

[30] S. Zhang, Efficient greedy algorithms for successive constraints methods with high-dimensional parameters, Brown Division of Applied Math Scientific Computing Tech Report 2011-23.