Abstract
許多科學及工程上的數值方法都必須耗費大理的時間在解疏松線性方程組(sparse linear system)，因此如何快速地求解這種線性方程組成為一個重要的課題。很自然地，我們會想到用平行處理(Parallel processing) 以便快速地解。本論文使用兩種覺的多重計算機：Transputer array和NCUBE 3200。解線性方程組的方法可分為兩類：直接消去法和疊代法，在解疏松線性方程組時以詁代法較佳。本篇論文使用共軛梯度演算法(the conjugate gradient algorithm)是解對稱正字(symmetric and positive definite) 線性方程組最佳的疊代演算法。如果沒有浮點運算的誤差，共軛梯度演算法保證最多ｎ步就可以求得正確解，其中ｎ為線性方程組的尺寸。如欲求解非對稱正定線性方程組，可以用該線性方程組的正交型式(nomal form)求解。在某些情形下共軛梯度演算法將很快收斂到正確解，例如：條件數(condition number)很小、對角線元素(diagonal entry)比非對角線元素(off-diagonal entry)大得多、該線性方程組是帶狀的(banded)... 等等，因此我們可以經過適當的轉換將欲求解線性方程組變成收斂較快形式來求解。此類技術稱為前狀態化(preconditioning) 。我們選用較適合多重計算機的一種一一比例前狀態化(scaled preconditioning)。在多重計算機上實作最重要的是使各個處理單元(processing element)被分配到的工作量相同和盡量減少處理單元間的通訊量(communication overhead)。按照本論文的分割方就可以達到這兩項要求。實驗數據顯示大部分的疏松線性方程組用我們方法都可以很有效率地解出，而那些無法很有效率地解出的疏松線性方程組本論文提出一個兩階段的方法來解決：首先重新安排各列(row) 的順序使帶寬減到最小，然後再調整各列的順序使得各個處理單元的負載平衡。此外，將計算與通訊的時間重疊可以使多重計算機的效率大增。