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

¹ Division of Applied Mathematics, Box F, Brown University, 182 George St., Providence, RI 02912, USA
Jan.Hesthaven@Brown.edu
² CNRS, UMR 7598, Laboratoire Jacques-Louis Lions, F-75005, Paris, France
stamm@ann.jussieu.fr
³ UPMC Univ Paris 06, UMR 7598, Laboratoire Jacques-Louis Lions, F-75005, Paris, France
⁴ Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong, China
shun.zhang@cityu.edu.hk

Received: 4 August 2011

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.