一、概述
三對角線性方程組的求解是許多科學和工程計算中最重要也是最基本的問題之一。在核物理、流體力學、油藏工程、石油地震數據處理及數值天氣預報等許多領域的大規模科學工程和數值處理中都會遇到三對角系統的求解問題。很多三對角線性方程組的算法可以直接推廣到求解塊三對角及帶狀線性方程組。由於在理論和實際套用上的重要性，近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分解方法的時序性很強的遞推計算轉化為遞推倍增並行計算。d.j.evans對此方法做了大量研究。p.dubois和g.rodrigue的研究表明stone算法是不穩定的。
（二）循環約化方法（cyclic reduction）
循環約化方法由hockey和g.golub在1965年提出，其基本思想是每次疊代將偶數編號方程中的奇變數消去，只剩下偶變數，問題轉變成求解僅由偶變數組成的規模減半的新三對角方程組。求解該新方程組，得到所有的偶變數後，再回代求解所有的奇變數。即約化和回代過程。由於其基本的算術操作可以向量化，適合於向量機。此方法有大量學者進行研究，提出了許多改進的方法。例如，heller針對最後幾步的短向量操作提出了不完全循環約化方法；r.reulter結合ibm3090vf向量機的特點提出了局部循環約化法；p.amodio針對分散式系統的特點改進了循環約化方法；最近針對此方法又提出對三對角方程組進行更大約化步的交替疊代策略。