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

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.