三對(duì)角系統(tǒng)并行算法的研究概況

1、三對(duì)角系統(tǒng)并行算法的研究概況      【摘   要】在科學(xué)和工程計(jì)算中，許多問題往往歸結(jié)為三對(duì)角線性方程組的求解，其并行算法的研究具有重要意義。文章全面總結(jié)了當(dāng)前求解三對(duì)角線性方程組的兩類并行算法：直接解法和迭代解法，并介紹了其特點(diǎn)。 【關(guān)鍵詞】三對(duì)角線性方程組；分治策略；并行算法；算法可擴(kuò)展性      一、概述三對(duì)角線性方程組的求解是許多科學(xué)和工程計(jì)算中最重要也是最基本的問題之一。在核物理、流體力學(xué)、油藏工程、石油地震數(shù)據(jù)處理及數(shù)值天氣預(yù)報(bào)等許多領(lǐng)域的大規(guī)?？茖W(xué)工程和數(shù)值處理中都

2、會(huì)遇到三對(duì)角系統(tǒng)的求解問題。很多三對(duì)角線性方程組的算法可以直接推廣到求解塊三對(duì)角及帶狀線性方程組。由于在理論和實(shí)際應(yīng)用上的重要性，近20年來三對(duì)角方程組的并行算法研究十分活躍。大規(guī)?？茖W(xué)計(jì)算需要高性能的并行計(jì)算機(jī)。隨著軟硬件技術(shù)的發(fā)展，高性能的并行計(jì)算機(jī)日新月異?，F(xiàn)今，smp可構(gòu)成每秒幾十億次運(yùn)算的系統(tǒng)，pvp和cow可構(gòu)成每秒幾百億次運(yùn)算的系統(tǒng)，而mpp和dsm可構(gòu)成每秒萬億次運(yùn)算或更高的系統(tǒng)。高性能并行計(jì)算機(jī)只是給大型科學(xué)計(jì)算提供了計(jì)算工具。如何發(fā)揮并行計(jì)算機(jī)的潛在性能和對(duì)三對(duì)角系統(tǒng)進(jìn)行有效求解，其關(guān)鍵在于抓住并行計(jì)算的特點(diǎn)進(jìn)行并行算法的研究和程序的設(shè)計(jì)與實(shí)現(xiàn)。另外，對(duì)處理機(jī)個(gè)數(shù)較多的并行

3、計(jì)算系統(tǒng)，在設(shè)計(jì)并行算法時(shí)必須解決算法的可擴(kuò)展性，并對(duì)可擴(kuò)展性進(jìn)行研究和分析。二、問題的提出設(shè)三對(duì)角線性方程組為               ax=y                          

4、;                          （1）      式中：a∈rn×n非奇異，αij=0，           。x=(x1，x2，&hellip

5、;xn)t y=(y1，y2，…yn）t。此系統(tǒng)在許多算法中被提出，因此研究其高性能并行算法是很有理論和實(shí)際意義的。三、并行求解三對(duì)角系統(tǒng)的直接解法關(guān)于三對(duì)角線性方程組的直接求解已經(jīng)有大量并行算法，其中wang的分裂法是最早針對(duì)實(shí)際硬件環(huán)境，基于分治策略提出的并行算法。它不僅通信結(jié)構(gòu)簡單，容易推廣到一般帶狀線性方程組的并行求解，而且為相繼出現(xiàn)的許多其它并行算法提供了可行的局部分解策略。近20年來求解三對(duì)角方程組的并行算法都是基于分治策略，即通過將三對(duì)角方程組分解成p個(gè)小規(guī)模問題，求解這p個(gè)小規(guī)模問題，再將這些解結(jié)合起來得到原三對(duì)角方程組的解。一般求解三對(duì)角方程組的分治方法的計(jì)算過

6、程可分為3個(gè)階段：一是消去，每臺(tái)處理機(jī)對(duì)子系統(tǒng)消元；二是求解縮減系統(tǒng)（需要通信）；三是回代，將縮減系統(tǒng)的解回代到每個(gè)子系統(tǒng)，求出最終結(jié)果。具體可分為以下幾類：（一）遞推耦合算法（recursive doubling）由stone于1975年提出，算法巧妙地把lu分解方法的時(shí)序性很強(qiáng)的遞推計(jì)算轉(zhuǎn)化為遞推倍增并行計(jì)算。d.j.evans對(duì)此方法做了大量研究。p.dubois和g.rodrigue的研究表明stone算法是不穩(wěn)定的。（二）循環(huán)約化方法（cyclic reduction）循環(huán)約化方法由hockey和g.golub在1965年提出，其基本思想是每次迭代將偶數(shù)編號(hào)方程中的奇變量消去，只剩下

7、偶變量，問題轉(zhuǎn)變成求解僅由偶變量組成的規(guī)模減半的新三對(duì)角方程組。求解該新方程組，得到所有的偶變量后，再回代求解所有的奇變量。即約化和回代過程。由于其基本的算術(shù)操作可以向量化，適合于向量機(jī)。此方法有大量學(xué)者進(jìn)行研究，提出了許多改進(jìn)的方法。例如，heller針對(duì)最后幾步的短向量操作提出了不完全循環(huán)約化方法；r.reulter結(jié)合ibm3090vf向量機(jī)的特點(diǎn)提出了局部循環(huán)約化法；p.amodio針對(duì)分布式系統(tǒng)的特點(diǎn)改進(jìn)了循環(huán)約化方法；最近針對(duì)此方法又提出對(duì)三對(duì)角方程組進(jìn)行更大約化步的交替迭代策略。（三）基于矩陣乘分解算法將系數(shù)矩陣a分解成a=ft，方程ax=b化為fy=b和tx=y兩個(gè)方程組的并行

8、求解。這種算法又可以分為兩類：1.重疊分解。如wang的分裂法及其改進(jìn)算法就屬于這一類。p.amodio在1993年對(duì)這類算法進(jìn)行了很好的總結(jié)，用本地lu、本地lud和本地循環(huán)約化法求解，并在1995年提出基于矩陣乘分解的并行qr算法。h.michielse和a.van der vorst改變wang算法的消元次序，提出了通信量減少的算法。李曉梅等將h.michielse和a.van der vorst算法中的通信模式從單向串行改為雙向并行，提出dpp算法，是目前最好的三對(duì)角方程組分布式算法之一。2000年駱志剛等中依據(jù)dpp算法，利用計(jì)算與通信重疊技術(shù)，減少處理機(jī)空閑時(shí)間取得了更好的并行效果。此類算法要求解p-1階縮減系