# Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods

Jan S. Hesthaven; Benjamin Stamm; Shun Zhang

- Volume: 48, Issue: 1, page 259-283
- ISSN: 0764-583X

## Access Full Article

top## Abstract

top## How to cite

topHesthaven, Jan S., Stamm, Benjamin, and 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 48.1 (2014): 259-283. <http://eudml.org/doc/273156>.

@article{Hesthaven2014,

abstract = {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.},

author = {Hesthaven, Jan S., Stamm, Benjamin, Zhang, Shun},

journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},

keywords = {greedy algorithm; reduced basis method; empirical interpolation method},

language = {eng},

number = {1},

pages = {259-283},

publisher = {EDP-Sciences},

title = {Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods},

url = {http://eudml.org/doc/273156},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Hesthaven, Jan S.

AU - Stamm, Benjamin

AU - Zhang, Shun

TI - Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods

JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 1

SP - 259

EP - 283

AB - 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.

LA - eng

KW - greedy algorithm; reduced basis method; empirical interpolation method

UR - http://eudml.org/doc/273156

ER -

## References

top- [1] R.E. Bank and A. Weiser, Some a posteriori error estimators for elliptic partial differential equations. Math. Comput.44 (1985) 303–320. Zbl0569.65079MR777265
- [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. Zbl1061.65118MR2103208
- [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. Zbl1229.65193MR2821591
- [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. Zbl1272.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. Zbl1196.37127MR2452388
- [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. Zbl1152.65109MR2473311
- [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. Zbl1181.78019MR2588434
- [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. Zbl1213.78011MR2639602
- [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. Zbl1228.35097MR2746617
- [11] J.L. Eftang and B. Stamm, Parameter multi-domain hp empirical interpolation. Int. J. Numer. Meth. Engng.90 (2012) 412–428. Zbl1242.65255MR2911317
- [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. Zbl1220.78045MR2799523
- [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. Zbl1142.65078MR2355712
- [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. Zbl1079.65096MR2136204
- [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. Zbl1302.65221MR2823471
- [16] B. Haasdonk and M. Ohlberger, Basis construction for reduced basis methods by adaptive parameter grids, in Proc. International Conference on Adaptive Modeling and Simulation2007 (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. Zbl1127.65086MR2367928
- [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. Zbl1184.65020MR2449115
- [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. Zbl1285.65009MR3123826
- [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. Zbl1304.65251
- [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. Zbl1273.65148MR2824231
- [23] S. Repin, A Posteriori Estimates for Partial Differential Equations, Walter de Gruyter, Berlin (2008). Zbl1162.65001MR2458008
- [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. Zbl1173.76352MR2281777
- [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. Zbl1304.65251MR2430350
- [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. Zbl1178.65050MR2436013
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.