以動態代理曲面輔助搜尋特徵值求解程式之最佳效能參數

Performance Tuning of Eigensolver via Dynamic Surrogate

蔡松峰(Sung-feng Tsai)

指導教授 ： 王偉仲

國立臺灣大學/理學院/數學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.10557

摘要

在大型矩陣的特徵值求解程式中，適當地選擇參數將使得特徵值求解程式的效能明顯提升。特徵值求解程式的執行時間與其參數之間並沒有明確的函數關係，故採用直接搜尋法為其最佳化工具。然而，在許多直接搜尋法中，大量的函數計算往往耗費許多時間。為了提升效能，我們提出一個想法：若在某點上其函數值已不可能是最佳值，則暫停該函數值之計算。在特徵值求解程式的疊代過程中，我們獲取資訊：根據資訊以動態地決定是否暫停或繼續特徵值求解程式的執行。然後我們根據低準確度以及高準確度之函數值，分別對應於暫停點以及收斂點，以建構代理曲面。而在我們的計算機實驗中，的確顯示了以動態代理曲面輔助搜尋法，可以降低傳統代理曲面輔助搜尋法的執行時間，並以其搜尋到的最佳化參數提升特徵值求解程式的效能。

關鍵字

特徵值求解程式 ； 動態代理曲面 ； 最佳化 ； 直接搜尋法 ； DACE

並列摘要

For using an iterative eigensolver to solve an eigenvalue problem with a large-scale matrix, adaptively choosing parameters will significantly improve its performance. Since there is no obvious relation between the execution time and parameters of an eigensolver, it is reasonable that using direct search method to optimize the parameters. In many direct search methods, however, it is likely that evaluating much number of function values is limited by time or cost. For reducing time or cost, one idea we present here is that we pause some function evaluations that have no chance to be optimal ones. During iterative process of an eigensolver, we monitor the information produced after each iteration to decide how we control iterative process dynamically: we determine whether iterations should be kept paused or restarted. We then construct a surrogate by using the function values with low accuracy and high one corresponding to paused points and convergent points, respectively. In our computer experiments, we show that the Dynamic Surrogate-Assisted Search (DSAS) Algorithm reduces the cost significantly. Hence, then we can tune the performance of an eigensolver efficiently.

並列關鍵字

optimization ； direct search method ； dynamic surrogate ； eigensolver ； DACE

參考文獻

[1] W.C. Davidon. Variable metric method for minimization. SIAM Journal on Optimization, 1(1):1–17, 1991.

[2] R. Hooke and T.A. Jeeves. “direct search”solution of numerical and statistical problems. Journal of the ACM (JACM), 8(2):212–229, 1961.

[3] T.M. Huang, W. Wang, and C.T. Lee. An efficiency study of polynomial eigenvalue problem solvers for quantum dot simulations. Taiwanese Journal of Mathematics, 14(3A):pp–999, 2010.

[4] T.G. Kolda, R.M. Lewis, and V. Torczon. Optimization by direct search: New perspectives on some classical and modern methods. SIAM review, pages 385–482, 2003.

[5] G.L.G. Sleijpen and H.A. Van der Vorst. A jacobi-davidson iteration method for linear eigenvalue problems. SIAM Review, pages 267–293, 2000.