An Accelerated Greedy Missing Point Estimation Procedure

Ralf Zimmermann, Karen Willcox

Research output: Contribution to journalJournal articleResearchpeer-review

231 Downloads (Pure)

Abstract

Model reduction via Galerkin projection fails to provide considerable computational savings if applied to general nonlinear systems. This is because the reduced representation of the state vector appears as an argument to the nonlinear function, whose evaluation remains as costly as for the full model. Masked projection approaches, such as the missing point estimation and the (discrete) empirical interpolation method, alleviate this effect by evaluating only a small subset of the components of a given nonlinear term; however, the selection of the evaluated components is a combinatorial problem and is computationally intractable even for systems of small size. This has been addressed through greedy point selection algorithms, which minimize an error indicator by sequentially looping over all components. While doable, this is suboptimal and still costly. This paper introduces an approach to accelerate and improve the greedy search. The method is based on the observation that the greedy algorithm requires solving a sequence of symmetric rank-one modifications to an eigenvalue problem. For doing so, we develop fast approximations that sort the set of candidate vectors that induce the rank-one modifications, without requiring solution of the modified eigenvalue problem. Based on theoretical insights into symmetric rank-one eigenvalue modifications, we derive a variation of the greedy method that is faster than the standard approach and yields better results for the cases studied. The proposed approach is illustrated by numerical experiments, where we observe a speed-up by two orders of magnitude when c


Read More: http://epubs.siam.org/doi/abs/10.1137/15M1042899
Original languageEnglish
JournalSIAM Journal on Scientific Computing
Volume38
Issue number5
Pages (from-to)A2827-A2850
ISSN1064-8275
DOIs
Publication statusPublished - 7. Sep 2016

Fingerprint Dive into the research topics of 'An Accelerated Greedy Missing Point Estimation Procedure'. Together they form a unique fingerprint.

Cite this