三對角線性方程組兩類并行算法的特點(diǎn)

1、對角線性方程組兩類并行算法的特點(diǎn)、概述三對角線性方程組的求解是許多科學(xué)和工程計算中最重要 也是最基本的問題之一。在核物理、流體力學(xué)、油藏工程、 石油地震數(shù)據(jù)處理及數(shù)值天氣預(yù)報等許多領(lǐng)域的大規(guī)?？?學(xué)工程和數(shù)值處理中都會遇到三對角系統(tǒng)的求解問題。很多三對角線性方程組的算法可以直接推廣到求解塊三對角及帶狀線性方程組。由于在理論和實(shí)際應(yīng)用上的重要性,近 20第 4 頁年來三對角方程組的并行算法研究十分活躍。大規(guī)?？茖W(xué)計算需要高性能的并行計算機(jī)。隨著軟硬件技術(shù)的發(fā)展，高性能的并行計算機(jī)日新月異?，F(xiàn)今，SMP可構(gòu)成每秒幾十億次運(yùn)算的系統(tǒng)，PVP和COV可構(gòu)成每秒幾百億次運(yùn)算 的系統(tǒng)，而MPF和DSM可構(gòu)

2、成每秒萬億次運(yùn)算或更高的系統(tǒng)。高性能并行計算機(jī)只是給大型科學(xué)計算提供了計算工具。如 何發(fā)揮并行計算機(jī)的潛在性能和對三對角系統(tǒng)進(jìn)行有效求解, 其關(guān)鍵在于抓住并行計算的特點(diǎn)進(jìn)行并行算法的研究和 統(tǒng), 在設(shè)計并行算法時必須解決算法的可擴(kuò)展性 , 并對可擴(kuò) 展性進(jìn)行研究和分析。程序的設(shè)計與實(shí)現(xiàn)。另外, 對處理機(jī)個數(shù)較多的并行計算系二、問題的提出 設(shè)三對角線性方程組為AX=Y (1)中:A RnXn非奇異,a ij=0,。X=(x1,x2,xn)T丫=(y1,y2,yn)T。此系統(tǒng)在許多算法中被提出 , 因此研究其高性能并行算法是 很有理論和實(shí)際意義的。三、并行求解三對角系統(tǒng)的直接解法關(guān)于三對角線性方程

3、組的直接求解已經(jīng)有大量并行算法,其Wang的分裂法是最早針對實(shí)際硬件環(huán)境，基于分治策略提出的并行算法。它不僅通信結(jié)構(gòu)簡單 , 容易推廣到一般帶狀 線性方程組的并行求解 , 而且為相繼出現(xiàn)的許多其它并行算 法提供了可行的局部分解策略。近 20 年來求解三對角方程組的并行算法都是基于分治策略即通過將三對角方程組分解成P 個小規(guī)模問題 , 求解這 P 個 小規(guī)模問題 , 再將這些解結(jié)合起來得到原三對角方程組的 解。一般求解三對角方程組的分治方法的計算過程可分為 個階段 : 一是消去 , 每臺處理機(jī)對子系統(tǒng)消元 ; 二是求解縮減 系統(tǒng)（需要通信 ）; 三是回代 , 將縮減系統(tǒng)的解回代到每個子 系統(tǒng) ,

4、 求出最終結(jié)果。具體可分為以下幾類( 一) 遞推耦合算法 (Recursive Doubling)由Stone于1975年提出，算法巧妙地把LU分解方法的時序性很強(qiáng)的遞推計算轉(zhuǎn)化為遞推倍增并行計算。D.J.Evans 對此方法做了大量研究。 P.Dubois 和 G.Rodrigue 的研究表明Stone 算法是不穩(wěn)定的。(二)循環(huán)約化方法 (Cyclic Reduction)循環(huán)約化方法由 Hockey 和 G.Golub 在 1965 年提出 , 其基本 思想是每次迭代將偶數(shù)編號方程中的奇變量消去 , 只剩下偶 變量, 問題轉(zhuǎn)變成求解僅由偶變量組成的規(guī)模減半的新三對 角方程組。求解該新方程

5、組 , 得到所有的偶變量后 ,再回代求解所有的奇變量。即約化和回代過程。由于其基本的算術(shù)操 作可以向量化 , 適合于向量機(jī)。此方法有大量學(xué)者進(jìn)行研究 提出了許多改進(jìn)的方法。例如 ,Heller 針對最后幾步的短向 量操作提出了不完全循環(huán)約化方法 ;R.Reulter 結(jié)合IBM3090VF向量機(jī)的特點(diǎn)提出了局部循環(huán)約化法;P .Amodio針對分布式系統(tǒng)的特點(diǎn)改進(jìn)了循環(huán)約化方法 ; 最近針對此方 法又提出對三對角方程組進(jìn)行更大約化步的交替迭代策略。（三） 基于矩陣乘分解算法 將系數(shù)矩陣A分解成A=FT，方程Ax=b化為Fy=b和Tx=y兩個 方程組的并行求解。 這種算法又可以分為兩類1.重疊分

6、解。如 Wang的分裂法及其改進(jìn)算法就屬于這一類。P.Amodio 在 1993年對這類算法進(jìn)行了很好的總結(jié) , 用本地LU、本地LUD和本地循環(huán)約化法求解，并在2019年提出基于矩陣乘分解的并行 QR算法。H.Michielse 和A.Van der Vorst改變Wang算法的消元次序，提出了通信量減少的算法。李曉梅等將 H.Michielse 和 A.Van der Vorst 算法中的通信模式從單向串行改為雙向并行，提出DPP算法，是目前最好的三對角方程組分布式算法之一。2019年駱志剛等中依據(jù) DPP算法,利用計算與通信重疊技術(shù) , 減少處理機(jī)空閑時間取得了更好 的并行效果。 此類算

7、法要求解 P-1 階縮減系統(tǒng)。2.不重疊分解。例如Lawrie Sameh算法、Johsoon算法、Baron算法、Chawla在1991年提出的 WZ分解算法以及 Mattor在 2019 年提出的算法都屬于這一類。此類算法要求解 2P-2 階 縮減系統(tǒng)。（ 四） 基于矩陣和分解算法 將系數(shù)矩陣分解成 A=Ao A,這類算法的共同特點(diǎn)是利用Sherman Morrison 公式將和的逆化為子矩陣逆的和。按矩陣 分解方法 , 這種算法又可分為兩類 :1.重疊分解。這類算法首先由Mehrmann在1990年提出，通過選擇好的分解在計算過程中保持原方程組系數(shù)矩陣的結(jié) 構(gòu)特性 , 具有好的數(shù)值穩(wěn)定性

8、 , 需要求解 P-1 階縮減系統(tǒng)。2.不重疊分解。Sun等在1992年提出的并行劃分 LU算法PPT算法和并行對角占優(yōu)算法 PDD算法均屬于這一類。需要求解 2P-2階縮減系統(tǒng)。其中PDD算法的通訊時間不隨處理機(jī)的變化而變化，具有很好的可擴(kuò)展性。X.H.Sun和W.Zhang在2019年提出了兩層混合并行方法PTH ,其基本思想是在 PDD中嵌入一個內(nèi)層三對角解法以形成一個兩層的并行 , 基本算法是PDD,三對角系統(tǒng)首先基于 PDD分解。PTH算法也具有很好的可擴(kuò)展性。四、并行求解三對角系統(tǒng)的迭代解法 當(dāng)稀疏線性方程組的系數(shù)矩陣不規(guī)則時 , 直接法在求解過程,并中會帶來大量非零元素 , 增加

9、了計算量、通信量和存儲量 且直接法不易并行 , 不能滿足求解大規(guī)模問題的需要。因此通常使用迭代法來求解一般系數(shù)線性方程組和含零元素較多三對角線性方程組。迭代法包括古典迭代法和Krylov 子第 7 頁空間迭代法。古典迭代法包括 Jacobi、Gauss-Seidel、SOR SSOF等方法。通常采用紅黑排序、多色排序和多分裂等技術(shù)進(jìn)行并行計算。由于古典迭代法有收斂速度慢、并行效果不好等缺點(diǎn), 目前已較少用于直接求解大型稀疏線性方程組 , 而是作為預(yù)條件 子和其它方法 （如 Krylov 子空間方法 ）相結(jié)合使用。Krylov 子空間方法具有存儲量小 , 計算量小且易于并行等優(yōu) 點(diǎn) , 非常適合

10、于并行求解大型稀疏線性方程組。結(jié)合預(yù)條件 子的 Krylov 子空間迭代法是目前并行求解大型稀疏線性方 程組的最主要方法。給定初值X0,求解稀疏線性方程組 AX=Y設(shè)Km為維子空間，般投影方法是從 m維仿射子空間XO+Km中尋找近似解 Xm第5頁使之滿足 Petrov-Galerkin 條件丫-AXm Lm其中Lm為另一個維子空間。如果Km是 Krylov子空間，則上述投影方法稱為 Krylov 子空間方法。 Krylov 子空間 Km(A,r0)定義為 :Km(A,rO)=spanrO,ArO,A2rO,Am -1r0選取不同的Km和Lm就得到不同的 Krylov子空間方法。主要算法包括四類

11、 : 基于正交投影方法、基于正交化方法、基 于雙正交化方法、基于正規(guī)方程方法。Krylov 子空間迭代法的收斂速度依賴于系數(shù)矩陣特征值的 分布, 對于很多問題 , 直接使用迭代法的收斂速度特別慢 , 或 者根本不收斂。因此使用預(yù)條件改變其收斂性 , 使中斷問題 可解, 并加速收斂速度是需要的。目前人們研究的預(yù)條件技 術(shù)可分為四類 : 采用基于矩陣分裂的古典迭代法作為預(yù)條件 子、采用不完全 LU 分解作預(yù)條件子、基于系數(shù)矩陣近似逆 的預(yù)條件子、結(jié)合實(shí)際問題用多重網(wǎng)格或區(qū)域分解作預(yù)條件 子。對 Krylov 子空間和預(yù)條件 Krylov 子空間方法有詳細(xì)的 討論。預(yù)條件 Krylov 子空間方法的

12、并行計算問題一直是研究熱點(diǎn) 已提出了一系列好的并行算法。目前預(yù)條件 Krylov 子空間 方法的計算量主要集中在矩陣向量乘上。雖然學(xué)者們做了大 量的研究工作 , 但是還沒找到效果好 , 又易于并行的預(yù)條件子。需要特別指出的是 , 對于一般線性代數(shù)方程組的并行求解 其可擴(kuò)展并行計算的研究已相對成熟 , 并已形成相應(yīng)的并行 軟件庫 , 如美國田納西亞州立大學(xué)和橡樹嶺國家實(shí)驗(yàn)室研制 的基于消息傳遞計算平臺的可擴(kuò)展線性代數(shù)程序庫ScaLA PAC爾得克薩斯大學(xué)開發(fā)的界面更加友好的并行線性代數(shù)庫PLAPACK我們借鑒其研究成果和研究方法，對三對角 線性方程組并行算法的研究是有幫助的。五、結(jié)語 三對角線性方程組的直接解法 ,算法豐富 ,程序較容易實(shí)現(xiàn)。但計算過程要增加計算量 , 并且大部分算法都對系數(shù)矩陣的 要求比較高。迭代解法適合于非零元素較多的情況 , 特別是 結(jié)合預(yù)條件子的 Krylov 子空間迭代法已成為當(dāng)前研究的熱 點(diǎn)。盡管三對角系統(tǒng)并行算法的研究取得了很多成果。但是還存在一些問題 : 直接法中, 分治策略帶來計算量和通信量的增加, 如