子空間方法求解大型特徵值問題之平行效能比較

Parallel Efficiency of Lanczos/Arnoldi and Jacobi-Davidson Type Methods on Large-scale Standard Eigenvalue Problem

王聖毅(Sheng-Yi Wang)

指導教授 ： 王偉仲

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

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

摘要

特徵值問題是近代計算科學領域裡面算是非常重要的問題。這些問題可從一些工程或者物理中的偏微分方程經由離散方法所得到。而隨著歷史的演進，特徵值解法主要可以分為兩大類。第一種是直接解法，直接解法中心思想法就是變換，利用一系列特殊的變換矩陣像是初等下三角矩陣、Householder矩陣、平面旋轉矩陣等，從矩陣A 出發逐次進行相似變換，使變換後的矩陣轉成容易求得特徵值的特殊矩陣像對角矩陣、上三角矩陣等。此方法多用於求解全部特徵值，其優點是收斂速度快，計算結果可靠，但由於原矩陣A 被破壞，當A 是稀疏(sparse)矩陣時，在計算過程中很難保持它的稀疏性，因此在程式上會耗費大量計算資源和記憶體。因而大多數變換方法只適於求解中小規模稠密(dense)矩陣的全部特徵值問題。Jacobi法、QR法以及高斯消去法等都屬此類。
然而現今的問題為了精確度，離散以後的矩陣會變得非常龐大，矩陣的維度有可能從數十萬到上千萬，而我們要的特徵值往往就是其中的幾個而已，用直接解法變的不實際。在這種情況下，疊代法變成了解決大型特徵值問題的有效工具。疊代法的主要精神就是希望透過子空間投影把大型的稀疏矩陣變成小的稠密矩陣，再用直接法解出特徵值。然而如何找到好的子空間卻是一個重要的問題。疊代法裡面最有名的就是Arnoldi/Lanczos法和Jacobi-Davidson法。Arnoldi/Lanczos法主要是利用Krylov子空間把矩陣投影成一個小的矩陣(維度大約是數十乘以數十的矩陣)，此方法在數學上也已經證明了其收斂性與計算穩定性。Arnoldi/Lanczos法大的特徵值會先收斂，如果要求小的特徵值或者想要找接近某個數字的特徵值。我們就必須用到shift-invert的技巧。但是天下沒有白吃的午餐，用了shift-invert雖然可以讓自己想要的特徵值率先收斂，但是必須付出代價。其代價就是要解一個大型的線性系統。同樣的線性系統我們不可能直接去解它，我們只能用數值疊代的方式讓它慢慢收斂到正確值。
Jacobi-Davidson法而是另外一種截然不同的子空間方法，此演算法以空間生成的方式是透過解一個線性系統叫 correction equation來產生。然而Jacobi-Davidson法到目前為止並沒有數學嚴謹證明其收斂性(截至目前為止也找不到反例)，主要困難在於Jacobi-Davidson法用了太多的近似。更有趣的是，在經過一些測試發現，就算Correction equation解的不準確他還是會收斂。
至於解線性系統常用的疊代法有三種共軛梯度法(CG) 、廣義最小殘量方法(GMRES)以及穩定雙共軛梯度法(BICGSTAB)。三種方法也都具有其特性和優缺點。有時候我們要加速它的收斂速率，我們會希望找到一個叫做預條件子(preconditioner)的矩陣把它乘到線性系統裡面，藉由它改善矩陣的結構性(此概念就像想辦法讓矩陣更接近單位矩陣)。如何找到好的預條件子，這也是一個目前仍在持續研究的課題。

除了演算法的改進，隨著時代的演進，我們常用的電腦從單核心已經到了多核心的時代，這也衍伸出許多不同的軟硬體架構和計算理論，更讓計算科學進入的高效能計算的時代。叢集計算是高效能運算的呈現方式之一，但叢集電腦相對於大型主機而言，具有相當優異的價格性能比。從近期世界五百大電腦排名統計來看，五百大電腦內就有80%的電腦即是採用叢集架構，由此可知發展叢集電腦架構已是世界高速計算的新趨勢。
本著結合軟體(演算法)和硬體(大型叢集電腦)的想法，想要解決一個問題:究竟在平行電腦架構上，哪一種特徵值解法會擁有最好的表現?畢竟在單核心時代，這些方法的測試都行之有年，但是在單核心表現不好的演算法，在平行架構上並不一定表現不好。在這麼多的選擇性裡面(特徵值+線性系統+預條件子)，哪一種組合會最適合現在的平行架構中?一般的經驗裡解線性系統的平行效能都非常差，我們到底是要解線性系統還是不要解，或者是有限度利用(解不準)?
本論文從物理量子點模擬找一個大型的特徵值問題，並且利用三種不同形狀的量子點再用有線方法離散，其矩陣有百萬乘以百萬到最大千萬乘以千萬，並且剛好有機會使用目前全台灣跑最快的電腦-御風者(ALPS)來進行測試，結果得到Jacobi-Davidson法在運用合適的預條件子之後，可以得到最好的表現，縱使他的平行效能不是最好，但是解線性系統可以解不準，只要有好的預條件子可以壓過平行效能不錯的Arnoldi/Lanczos法。

關鍵字

平行計算 ； Jacobi-Davidson 法 ； Krylov-Schur 法 ； 線性系統 ； 預條件子

並列摘要

With the development of cluster and hardware, parallel processing in scienti c computing has become more and more important. Many algorithms must be reconsidered in a parallel architecture. The algorithm has good performance in the sequential architecture may not have good performance in parallel architecture. Eigenvalue problem is one of the most important problem in scienti c computing. It can be obtained from the discretization of some partial di erential equations in many engineering and scienti c applications. Arnoldi
and Lanczos with Krylov-Schur restart, also called Krylov-Schur method (KS)
and Jacobi-Davidson (JD) are popular techniques to solve these problems. In this thesis, we target the standard eigenvalue problem solved by these two algorithms arising in quantum dot simulations. We use two powerful scienti csoftware libraries, namely Portable, Extensible Toolkit for Scienti c Computation (PETSc) and Scalable Library for Eigenvalue Problem Computations
(SLEPc). We compare the speed-up and execution time of the two algorithms
in parallel architecture, and show that Jacobi-David has the best performance
in parallel architecture if we choose appropriate preconditioner.

並列關鍵字

parallel computing ； Krylov-Schur method ； Jacobi-Davidson ； preconditioner ； linear system

參考文獻

[1] P. Arbenz and R. Geus. A comparison of solvers for large eigenvalue problems

[2] Z. Bai and J. W. Demmel. On swapping diagonal blocks in real schur form.

Linear Algebra Appl., 186:73–79, 1993.

[3] G.L.G. Sleijpen D.R. Fokkema and H.A. van der Vorst. Jacobi-davidson style

QR and QZ algorithms for the reduction of matrix pencils. SIAM J. Sci.