兩種Krylov子空間算法的并行性能改進(jìn)研究.pdf

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

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

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

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