兩種Krylov子空間算法的并行性能改進研究.pdf

1、尋求大型稀疏線性方程組的高效并行解法是當(dāng)前大規(guī)模科學(xué)計算中亟待解決的熱點問題。Krylov子空間算法是求解大型稀疏線性方程組最流行和最有效的迭代方法之一，其并行計算主要考慮矩陣向量乘和內(nèi)積計算。目前通過適當(dāng)編碼，矩陣向量乘在并行計算時不會造成嚴(yán)重性能降低的通信問題。但內(nèi)積計算并非如此，由于內(nèi)積計算需要全局通信，在分布式并行計算環(huán)境下其成為高效并行計算的瓶頸。
　　 ORTHOMIN(m)算法和GCR(k)算法是兩種Krylov子

2、空間算法，為減少兩算法內(nèi)積計算引起的全局通信以提高并行性能，本文以油藏數(shù)值模擬問題為應(yīng)用背景分別對兩算法做了如下工作：
　　 首先利用ORTHOMIN(m)算法的固有性質(zhì)改變其計算次序，給出了該算法的改進形式，其次對算法進行了并行設(shè)計、理論分析，最后通過求解油藏數(shù)值模擬問題給出數(shù)值實驗。同ORTHOMIN(m)算法相比，改進算法與ORTHOMIN(m)算法具有相同的收斂性，在分布式并行計算環(huán)境下進行并行計算時改進算法用連續(xù)內(nèi)積計

3、算代替了ORTHOMIN(m)算法分離的內(nèi)積計算，消除了ORTHOMIN(m)算法兩次內(nèi)積計算的數(shù)據(jù)相關(guān)性，使同步開銷次數(shù)減少為ORTHOMIN(m)算法的一半進而加大了計算時間相對通信時間的比重，提高了并行效率。理論分析表明當(dāng)處理機臺數(shù)較多時改進算法比ORTHOMIN(m)算法的并行計算時間要快，有更好的加速比及可擴展性。數(shù)值實驗結(jié)果也表明改進算法的并行性能要優(yōu)于ORTHOMIN(m)算法，更利于油藏數(shù)值模擬問題的并行求解。
　

4、　 對于GCR(k)算法，利用同樣的方法給出了該算法的改進形式，并給出算法的并行設(shè)計、理論分析，且通過求解油藏數(shù)值模擬問題給出數(shù)值實驗。與ORTHOMIN(m)算法類似，改進算法與GCR(k)算法具有相同的收斂性，在分布式并行計算環(huán)境下進行并行計算時改進算法使同步開銷次數(shù)減少為GCR(k)算法的一半，提高了并行效率。理論分析同樣表明當(dāng)處理機臺數(shù)較多時改進算法比GCR(k)算法的并行計算時間要快，有更好的加速比及可擴展性。數(shù)值實驗結(jié)果也