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.
Mots-clés : 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 },
pages = {259--283},
publisher = {EDP-Sciences},
volume = {48},
number = {1},
year = {2014},
doi = {10.1051/m2an/2013100},
mrnumber = {3177844},
zbl = {1292.41001},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an/2013100/}
}
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 PY - 2014 SP - 259 EP - 283 VL - 48 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2013100/ DO - 10.1051/m2an/2013100 LA - en ID - M2AN_2014__48_1_259_0 ER -
%0 Journal Article %A Hesthaven, Jan S. %A Stamm, Benjamin %A Zhang, Shun %T Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2014 %P 259-283 %V 48 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2013100/ %R 10.1051/m2an/2013100 %G en %F 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 , Tome 48 (2014) no. 1, pp. 259-283. doi : 10.1051/m2an/2013100. http://www.numdam.org/articles/10.1051/m2an/2013100/
[1] and , Some a posteriori error estimators for elliptic partial differential equations. Math. Comput. 44 (1985) 303-320. | MR | Zbl
[2] , , and , 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 | Zbl
[3] , , , , and , Convergence rates for greedy algorithms in reduced basis methods. SIAM J. Math. Anal. 43 (2011) 1457-1472. | MR | Zbl
[4] , , , and , 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
[5] , Model-Constrained Optimization Methods for Reduction of Parameterized Large-Scale Systems, MIT Thesis (2007).
[6] , and , Model reduction for large-scale systems with high-dimensional parametric input space. SIAM J. Sci. Comput. 30 (2008) 3270-3288. | MR | Zbl
[7] , , and , 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 | Zbl
[8] , , and , 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 | Zbl
[9] , , and , Certified reduced basis methods and output bounds for the harmonic maxwell equations. SIAM J. Sci. Comput. 32 (2010) 970-996. | MR | Zbl
[10] , and , An “hp” certified reduced basis method for parametrized elliptic partial differential equations. SIAM J. Sci. Comput. 32 (2010) 3170-3200. | MR | Zbl
[11] and , Parameter multi-domain hp empirical interpolation. Int. J. Numer. Meth. Engng. 90 (2012) 412-428. | MR | Zbl
[12] , , and , The reduced basis method for the electric field integral equation. J. Comput. Phys. 230 (2011) 5532-5555. | MR | Zbl
[13] , , and , Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations. Math. Model. Numer. Anal. 41 (2007) 575-605. | Numdam | MR | Zbl
[14] and , A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations. M2AN 39 (2005) 157-181. | Numdam | MR | Zbl
[15] , and , 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
[16] and , Basis construction for reduced basis methods by adaptive parameter grids, in Proc. International Conference on Adaptive Modeling and Simulation 2007 (2007) 116-119.
[17] and , 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] , , and , 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 | Zbl
[19] , , and , A general multipurpose interpolation procedure: the magic points. Commun. Pure Appl. Anal. 8 (2009) 383-404. | MR | Zbl
[20] and , Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces, arXiv: math.NA, Apr 2012, accepted in SIAM Journal on Scientific Computing. | MR | Zbl
[21] and , 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.
[22] , and , Certified reduced basis approximation for parametrized partial differential equations and applications. J. Math. Ind. 1 (2011) 3. | MR | Zbl
[23] , A Posteriori Estimates for Partial Differential Equations, Walter de Gruyter, Berlin (2008). | MR | Zbl
[24] and , On the stability of the reduced basis method for Stokes equations in parametrized domains. Comput. Methods Appl. Mech. Eng. 196 (2007) 1244-1260. | MR | Zbl
[25] , and , 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
[26] , 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] , Greedy Approximation. Acta Numerica (2008) 235-409. | MR | Zbl
[28] , Reduced-Basis Methods Applied to Problems in Elasticity: Analysis and Applications, MIT Thesis (2003).
[29] , , and , 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] , Efficient greedy algorithms for successive constraints methods with high-dimensional parameters, Brown Division of Applied Math Scientific Computing Tech Report 2011-23.
Cité par Sources :
