1、三對角線性方程組兩類并行算法的特點         您正在瀏覽的數(shù)學(xué)論文是三對角線性方程組兩類并行算法的特點                    一、概述        三對角線性方程組的求解是許多科學(xué)和工程計算中最重要也是最基本的問題之

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

3、        高性能并行計算機只是給大型科學(xué)計算提供了計算工具。如何發(fā)揮并行計算機的潛在性能和對三對角系統(tǒng)進行有效求解,其關(guān)鍵在于抓住并行計算的特點進行并行算法的研究和程序的設(shè)計與實現(xiàn)。另外,對處理機個數(shù)較多的并行計算系統(tǒng),在設(shè)計并行算法時必須解決算法的可擴展性,并對可擴展性進行研究和分析。        二、問題的提出        設(shè)三對角線性方程組為

4、        AX=Y (1)        式中:ARn×n非奇異,ij=0, 。X=(x1,x2,xn)T Y=(y1,y2,yn)T。        此系統(tǒng)在許多算法中被提出,因此研究其高性能并行算法是很有理論和實際意義的。        三、并行求解三對角系統(tǒng)

5、的直接解法        關(guān)于三對角線性方程組的直接求解已經(jīng)有大量并行算法,其中Wang的分裂法是最早針對實際硬件環(huán)境,基于分治策略提出的并行算法。它不僅通信結(jié)構(gòu)簡單,容易推廣到一般帶狀線性方程組的并行求解,而且為相繼出現(xiàn)的許多其它并行算法提供了可行的局部分解策略。        近20年來求解三對角方程組的并行算法都是基于分治策略,即通過將三對角方程組分解成P個小規(guī)模問題,求解這P個小規(guī)模問題,再將這些解結(jié)合起來得到原三對角方程組的解

6、。一般求解三對角方程組的分治方法的計算過程可分為3個階段:一是消去,每臺處理機對子系統(tǒng)消元;二是求解縮減系統(tǒng)(需要通信);三是回代,將縮減系統(tǒng)的解回代到每個子系統(tǒng),求出最終結(jié)果。具體可分為以下幾類:        (一)遞推耦合算法(Recursive Doubling)        (二)循環(huán)約化方法(Cyclic Reduction)        循

7、環(huán)約化方法由Hockey和G.Golub在1965年提出,其基本思想是每次迭代將偶數(shù)編號方程中的奇變量消去,只剩下偶變量,問題轉(zhuǎn)變成求解僅由偶變量組成的規(guī)模減半的新三對角方程組。求解該新方程組,得到所有的偶變量后,再回代求解所有的奇變量。即約化和回代過程。由于其基本的算術(shù)操作可以向量化,適合于向量機。此方法有大量學(xué)者進行研究,提出了許多改進的方法。例如,Heller針對最后幾步的短向量操作提出了不完全循環(huán)約化方法;R.Reulter結(jié)合IBM3090VF向量機的特點提出了局部循環(huán)約化法;P.Amodio針對分布式系統(tǒng)的特點改進了循環(huán)約化方法;最近針對此方法又提出對三對角方程組進行更大約化步的交

8、替迭代策略。        (三)基于矩陣乘分解算法        將系數(shù)矩陣A分解成A=FT,方程Ax=b化為Fy=b和Tx=y兩個方程組的并行求解。這種算法又可以分為兩類:        2.不重疊分解。例如Lawrie & Sameh算法、Johsoon算法、Baron算法、Chawla在1991年提出的WZ分解算法以及Mattor在1995年

9、提出的算法都屬于這一類。此類算法要求解2P-2階縮減系統(tǒng)。        (四)基于矩陣和分解算法        將系數(shù)矩陣分解成A=Ao+A,這類算法的共同特點是利用Sherman & Morrison公式將和的逆化為子矩陣逆的和。按矩陣分解方法,這種算法又可分為兩類:        1.重疊分解。這類算法首先由Mehrmann在1990年提出,通

10、過選擇好的分解在計算過程中保持原方程組系數(shù)矩陣的結(jié)構(gòu)特性,具有好的數(shù)值穩(wěn)定性,需要求解P-1階縮減系統(tǒng)。        四、并行求解三對角系統(tǒng)的迭代解法        當稀疏線性方程組的系數(shù)矩陣不規(guī)則時,直接法在求解過程中會帶來大量非零元素,增加了計算量、通信量和存儲量,并且直接法不易并行,不能滿足求解大規(guī)模問題的需要。因此通常使用迭代法來求解一般系數(shù)線性方程組和含零元素較多三對角線性方程組。迭代法包括古典迭代法和Krylov子空間迭代

11、法。        古典迭代法包括Jacobi、Gauss-Seidel、SOR、SSOR等方法。通常采用紅黑排序、多色排序和多分裂等技術(shù)進行并行計算。        由于古典迭代法有收斂速度慢、并行效果不好等缺點,目前已較少用于直接求解大型稀疏線性方程組,而是作為預(yù)條件子和其它方法(如Krylov子空間方法)相結(jié)合使用。        Krylov子空間方

12、法具有存儲量小,計算量小且易于并行等優(yōu)點,非常適合于并行求解大型稀疏線性方程組。結(jié)合預(yù)條件子的Krylov子空間迭代法是目前并行求解大型稀疏線性方程組的最主要方法。        給定初值X0,求解稀疏線性方程組AX=Y。設(shè)Km為維子空間,一般投影方法是從m維仿射子空間X0+Km中尋找近似解Xm使之滿足Petrov-Galerkin條件        Y-AXmLm      

13、  其中Lm為另一個維子空間。如果Km是Krylov子空間,則上述投影方法稱為Krylov子空間方法。Krylov子空間Km(A,r0)定義為:        Km(A,r0)=spanr0,Ar0,A2r0,Am-1r0        選取不同的Km和Lm就得到不同的Krylov子空間方法。主要算法包括四類:基于正交投影方法、基于正交化方法、基于雙正交化方法、基于正規(guī)方程方法。   &

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

15、rylov子空間方法的并行計算問題一直是研究熱點,已提出了一系列好的并行算法。目前預(yù)條件Krylov子空間方法的計算量主要集中在矩陣向量乘上。雖然學(xué)者們做了大量的研究工作,但是還沒找到效果好,又易于并行的預(yù)條件子。        需要特別指出的是,對于一般線性代數(shù)方程組的并行求解,其可擴展并行計算的研究已相對成熟,并已形成相應(yīng)的并行軟件庫,如美國田納西亞州立大學(xué)和橡樹嶺國家實驗室研制的基于消息傳遞計算平臺的可擴展線性代數(shù)程序庫ScaLAPACK和得克薩斯大學(xué)開發(fā)的界面更加友好的并行線性代數(shù)庫PLAPACK。我們借鑒

16、其研究成果和研究方法,對三對角線性方程組并行算法的研究是有幫助的。        五、結(jié)語        三對角線性方程組的直接解法,算法豐富,程序較容易實現(xiàn)。但計算過程要增加計算量,并且大部分算法都對系數(shù)矩陣的要求比較高。迭代解法適合于非零元素較多的情況,特別是結(jié)合預(yù)條件子的Krylov子空間迭代法已成為當前研究的熱點。        盡管三對角系統(tǒng)并行算法的研究取得了很多成果。但是還存在一些問題:直接法中,分治策略帶來計算量和通信量的增加,如何減少計算量和通信量有待于進一步的研究;目前直接算法均基于分治策略,如何把其它并行算法設(shè)計技術(shù),如平衡樹和流水線等技術(shù)應(yīng)用到三對角系統(tǒng)的并行求解中也是需要引起重視的方向;對于非對稱系統(tǒng)還沒找