Smart Linear Algebraic Operations for Efficient Gaussian Markov Improvement Algorithm
Smart Linear Algebraic Operations for Efficient Gaussian Markov Improvement Algorithm
复制标题
DOI：
10.1109/wsc48552.2020.9384017
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Xinru Li;Eunhye Song
中科院分区：
文献类型：
--
作者：
Xinru Li;Eunhye Song
研究了基于高斯马尔可夫随机场（GMRF）响应面模型的高斯马尔可夫改进算法（GMIA）的计算改进。GMIA的计算瓶颈在于采样决策，这需要在每次迭代时对GMRF的稀疏但大精度的矩阵进行因式分解和求逆。我们提出了智能GMIA（sGMIA），间歇性地执行昂贵的线性代数运算，同时递归地更新必要的向量和矩阵，使采样决策之间的几次迭代。后者的迭代在开始时比前者便宜得多，但随着递归的继续，它们的成本会增加，最终超过前者的成本。sGMIA通过最小化每次迭代的平均代价来自适应地决定递归的持续时间。我们进行浮点运算分析，以证明sGMIA的计算效益。实验结果表明，sGMIA算法在获得与GMIA算法相同搜索效果的同时，具有较高的计算效率.
This paper studies computational improvement of the Gaussian Markov improvement algorithm (GMIA) whose underlying response surface model is a Gaussian Markov random field (GMRF). GMIA’s computational bottleneck lies in the sampling decision, which requires factorizing and inverting a sparse, but large precision matrix of the GMRF at every iteration. We propose smart GMIA (sGMIA) that performs expensive linear algebraic operations intermittently, while recursively updating the vectors and matrices necessary to make sampling decisions for several iterations in between. The latter iterations are much cheaper than the former at the beginning, but their costs increase as the recursion continues and ultimately surpass the cost of the former. sGMIA adaptively decides how long to continue the recursion by minimizing the average per-iteration cost. We perform a floating-point operation analysis to demonstrate the computational benefit of sGMIA. Experiment results show that sGMIA enjoys computational efficiency while achieving the same search effectiveness as GMIA.