求解三對角線性方程組兩類并行算法的特點
（三）基于矩陣乘分解算法
將系數矩陣a分解成a=ft，方程ax=b化為fy=b和tx=y兩個方程組的并行求解。這種算法又可以分為兩類：
1.重疊分解。如wang的分裂法及其改進算法就屬于這一類。p.amodio在1993年對這類算法進行了很好的總結，用本地lu、本地lud和本地循環約化法求解，并在1995年提出基于矩陣乘分解的并行qr算法。h.michielse和a.van der vorst改變wang算法的消元次序，提出了通信量減少的算法。李曉梅等將h.michielse和a.van 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算法的通訊時間不隨處理機的變化而變化，具有很好的可擴展性。x.h.sun和w.zhang在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)定義為：