AN ACCELERATED GREEDY MISSING POINT ESTIMATION PROCEDURE
AN ACCELERATED GREEDY MISSING POINT ESTIMATION PROCEDURE
复制标题
DOI：
10.1137/15m1042899
复制
发表时间：
2016-01-01
影响因子：
3.1
通讯作者：
Willcox, K.
中科院分区：
文献类型：
--
作者：
Zimmermann, R.;Willcox, K.
如果应用于一般的非线性系统，通过Galerkin投影模型简化不能提供相当大的计算节省。这是因为状态向量的简化表示作为非线性函数的参数出现，其评估与完整模型的评估一样昂贵。掩蔽投影方法，如缺失点估计和（离散）经验插值方法，通过仅评估给定非线性项的组件的一个小子集来减轻这种影响;然而，评估组件的选择是一个组合问题，即使对于小尺寸的系统也是计算上难以处理的。这已经通过贪婪点选择算法解决了，该算法通过顺序地循环所有组件来最小化错误指示符。虽然可行，但这是次优的，而且仍然昂贵。本文介绍了一种加速和改进贪婪搜索的方法。该方法是基于观察贪婪算法需要解决一个序列的对称秩一修改的特征值问题。为了做到这一点，我们开发了快速近似排序的候选向量，诱导秩一修改，而不需要修改的特征值问题的解决方案。基于对称秩一特征值修改的理论见解，我们推导出一种变化的贪婪方法，比标准方法更快，并产生更好的结果的情况下研究。所提出的方法说明了数值实验，在那里我们观察到的速度提高了两个数量级相比，标准的贪婪方法，同时达到一个更好的质量降低模型。
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 compared to the standard greedy method while arriving at a better quality reduced model.