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

Jan S. Hesthaven; Benjamin Stamm; Shun Zhang

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

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

Abstract

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

How to cite

top

Hesthaven, 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. [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. [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. [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. [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. [5] T. Bui-Thanh, Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems, MIT Thesis (2007). 
  6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23] S. Repin, A Posteriori Estimates for Partial Differential Equations, Walter de Gruyter, Berlin (2008). Zbl1162.65001MR2458008
  24. [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. [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. [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. [27] V.N. Temlyakov, Greedy Approximation. Acta Numerica (2008) 235–409. Zbl1178.65050MR2436013
  28. [28] K. Veroy, Reduced-Basis Methods Applied to Problems in Elasticity: Analysis and Applications, MIT Thesis (2003). 
  29. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.