求解三對角線性方程組兩類並行算法的特點

一、概述

三對角線性方程組的求解是許多科學和工程計算中最重要也是最基本的問題之一。在核物理、流體力學、油藏工程、石油地震數據處理及數值天氣預報等許多領域的大規模科學工程和數值處理中都會遇到三對角系統的求解問題。很多三對角線性方程組的算法可以直接推廣到求解塊三對角及帶狀線性方程組。由於在理論和實際應用上的重要性，近20年來三對角方程組的並行算法研究十分活躍。

大規模科學計算需要高性能的並行計算機。隨着軟硬件技術的發展，高性能的並行計算機日新月異。現今，smp可構成每秒幾十億次運算的系統，pvp和cow可構成每秒幾百億次運算的系統，而mpp和dsm可構成每秒萬億次運算或更高的系統。

高性能並行計算機只是給大型科學計算提供了計算工具。如何發揮並行計算機的潛在性能和對三對角系統進行有效求解，其關鍵在於抓住並行計算的特點進行並行算法的研究和程序的設計與實現。另外，對處理機個數較多的並行計算系統，在設計並行算法時必須解決算法的可擴展性，並對可擴展性進行研究和分析。

二、問題的提出

設三對角線性方程組為

ax=y （1）

式中：a∈rn×n非奇異，αij=0， 。x=(x1，x2，…xn)t y=(y1，y2，…yn）t。

此係統在許多算法中被提出，因此研究其高性能並行算法是很有理論和實際意義的。

三、並行求解三對角系統的直接解法

關於三對角線性方程組的直接求解已經有大量並行算法，其中wang的分裂法是最早針對實際硬件環境，基於分治策略提出的並行算法。它不僅通信結構簡單，容易推廣到一般帶狀線性方程組的並行求解，而且為相繼出現的許多其它並行算法提供了可行的局部分解策略。

近20年來求解三對角方程組的並行算法都是基於分治策略，即通過將三對角方程組分解成p個小規模問題，求解這p個小規模問題，再將這些解結合起來得到原三對角方程組的解。一般求解三對角方程組的分治方法的計算過程可分為3個階段：一是消去，每台處理機對子系統消元；二是求解縮減系統（需要通信）；三是回代，將縮減系統的解回代到每個子系統，求出最終結果。具體可分為以下幾類：

（一）遞推耦合算法（recursive doubling）

由stone於1975年提出，算法巧妙地把lu分解方法的時序性很強的遞推計算轉化為遞推倍增並行計算。s對此方法做了大量研究。is和igue的研究表明stone算法是不穩定的。

（二）循環約化方法（cyclic reduction）

循環約化方法由hockey和b在1965年提出，其基本思想是每次迭代將偶數編號方程中的奇變量消去，只剩下偶變量，問題轉變成求解僅由偶變量組成的規模減半的新三對角方程組。求解該新方程組，得到所有的偶變量後，再回代求解所有的奇變量。即約化和回代過程。由於其基本的算術操作可以向量化，適合於向量機。此方法有大量學者進行研究，提出了許多改進的方法。例如，heller針對最後幾步的短向量操作提出了不完全循環約化方法；ter結合ibm3090vf向量機的特點提出了局部循環約化法；io針對分佈式系統的特點改進了循環約化方法；最近針對此方法又提出對三對角方程組進行更大約化步的交替迭代策略。

（三）基於矩陣乘分解算法

將係數矩陣a分解成a=ft，方程ax=b化為fy=b和tx=y兩個方程組的並行求解。這種算法又可以分為兩類：

1.重疊分解。如wang的分裂法及其改進算法就屬於這一類。io在1993年對這類算法進行了很好的總結，用本地lu、本地lud和本地循環約化法求解，並在1995年提出基於矩陣乘分解的並行qr算法。ielse和 der vorst改變wang算法的消元次序，提出了通信量減少的算法。李曉梅等將ielse和 der vorst算法中的通信模式從單向串行改為雙向並行，提出dpp算法，是目前最好的三對角方程組分佈式算法之一。XX年駱志剛等中依據dpp算法，利用計算與通信重疊技術，減少處理機空閒時間取得了更好的並行效果。此類算法要求解p-1階縮減系統。

2.不重疊分解。例如lawrie & sameh算法、johsoon算法、baron算法、chawla在1991年提出的wz分解算法以及mattor在1995年提出的算法都屬於這一類。此類算法要求解2p-2階縮減系統。

（四）基於矩陣和分解算法

將係數矩陣分解成a=ao+△a，這類算法的共同特點是利用sherman & morrison公式將和的逆化為子矩陣逆的和。按矩陣分解方法，這種算法又可分為兩類：

1.重疊分解。這類算法首先由mehrmann在1990年提出，通過選擇好的分解在計算過程中保持原方程組係數矩陣的結構特性，具有好的數值穩定性，需要求解p-1階縮減系統。

2.不重疊分解。sun等在1992年提出的並行劃分lu算法ppt算法和並行對角佔優算法pdd算法均屬於這一類。需要求解2p-2階縮減系統。其中pdd算法的通訊時間不隨處理機的變化而變化，具有很好的可擴展性。和g在XX年提出了兩層混合並行方法pth ，其基本思想是在pdd中嵌入一個內層三對角解法以形成一個兩層的並行，基本算法是pdd，三對角系統首先基於pdd分解。pth算法也具有很好的可擴展性。

四、並行求解三對角系統的迭代解法

當稀疏線性方程組的係數矩陣不規則時，直接法在求解過程中會帶來大量非零元素，增加了計算量、通信量和存儲量，並且直接法不易並行，不能滿足求解大規模問題的需要。因此通常使用迭代法來求解一般係數線性方程組和含零元素較多三對角線性方程組。迭代法包括古典迭代法和krylov子空間迭代法。

古典迭代法包括jacobi、gauss-seidel、sor、ssor等方法。通常採用紅黑排序、多色排序和多分裂等技術進行並行計算。

由於古典迭代法有收斂速度慢、並行效果不好等缺點，目前已較少用於直接求解大型稀疏線性方程組，而是作為預條件子和其它方法（如krylov子空間方法）相結合使用。 　krylov子空間方法具有存儲量小，計算量小且易於並行等優點，非常適合於並行求解大型稀疏線性方程組。結合預條件子的krylov子空間迭代法是目前並行求解大型稀疏線性方程組的最主要方法。

給定初值x0，求解稀疏線性方程組ax=y。設km為維子空間，一般投影方法是從m維仿射子空間x0+km中尋找近似解xm使之滿足petrov-galerkin條件

y-axm┻lm

其中lm為另一個維子空間。如果km是krylov子空間，則上述投影方法稱為krylov子空間方法。krylov子空間km(a，r0)定義為：

km(a，r0)=span{r0，ar0，a2r0，…，am-1r0}

選取不同的km和lm就得到不同的krylov子空間方法。主要算法包括四類：基於正交投影方法、基於正交化方法、基於雙正交化方法、基於正規方程方法。

krylov子空間迭代法的收斂速度依賴於係數矩陣特徵值的分佈，對於很多問題，直接使用迭代法的收斂速度特別慢，或者根本不收斂。因此使用預條件改變其收斂性，使中斷問題可解，並加速收斂速度是需要的。目前人們研究的預條件技術可分為四類：採用基於矩陣分裂的古典迭代法作為預條件子、採用不完全lu分解作預條件子、基於係數矩陣近似逆的預條件子、結合實際問題用多重網格或區域分解作預條件子。對krylov子空間和預條件krylov子空間方法有詳細的討論。

預條件krylov子空間方法的並行計算問題一直是研究熱點，已提出了一系列好的並行算法。目前預條件krylov子空間方法的計算量主要集中在矩陣向量乘上。雖然學者們做了大量的研究工作，但是還沒找到效果好，又易於並行的預條件子。

需要特別指出的是，對於一般線性代數方程組的並行求解，其可擴展並行計算的研究已相對成熟，並已形成相應的並行軟件庫，如美國田納西亞州立大學和橡樹嶺國家實驗室研製的基於消息傳遞計算平台的可擴展線性代數程序庫scalapack和得克薩斯大學開發的界面更加友好的並行線性代數庫plapack。我們借鑑其研究成果和研究方法，對三對角線性方程組並行算法的研究是有幫助的。

五、結語

三對角線性方程組的直接解法，算法豐富，程序較容易實現。但計算過程要增加計算量，並且大部分算法都對係數矩陣的要求比較高。迭代解法適合於非零元素較多的情況，特別是結合預條件子的krylov子空間迭代法已成為當前研究的熱點。

儘管三對角系統並行算法的研究取得了很多成果。但是還存在一些問題：直接法中，分治策略帶來計算量和通信量的增加，如何減少計算量和通信量有待於進一步的研究；目前直接算法均基於分治策略，如何把其它並行算法設計技術，如平衡樹和流水線等技術應用到三對角系統的並行求解中也是需要引起重視的方向；對於非對稱系統還沒找到一種通用的krylov子空間方法；krylov子空間方法的並行實現時僅考慮係數矩陣與向量乘，對其它問題考慮不夠；以往設計的並行算法缺乏對算法可擴展性的考慮和分析。