解線性聯立方程式是一個需要大量且密集資料運算的問題, 一般傳統式計算機利用高

斯消去法來解 N個線性聯立方程式時, 需要O(N ) 的時間來做順向消去(Forward eli

-mination)處理, 以及O(N ) 的時間來做反向替換(Backward substitution) 處理。

一個基本的方格連接計算機(Mesh-connected computer,MCC) 則分別需要O(N ) 及O(

N)來做順向消去及反向替換的處理。若考慮Pivoting操作, 不論是Maximal Pivotng

或Partial Pivoting, 傳統式計算機和基本的方格連接計算機則需要更多的時間。

基本的方格連接計算機因沒有傳播(Brodcasting) 資料的功能, 所以在做順向消去及

反向替換時都需要將必要的元素一行行或一列列地傳送。在使用Pivoting時亦同。方

格連接和多全通匯流排計算機(MCC with mutiple global bus) 上因具備有單一傳播

及行列傳播的功能, 所以上述的動作均能在一個步驟中完成。因此, 用方格連接和多

全通匯流排計算機(MCC with multiple global buses)來解線性聯立方程式可以比使

用方格連接計算機節省很多時間。我們使用這種增強型平行架構, 來提出Gauss 消去

法、Gauss-Jordan法、Crout 法等三種沒有Pivoting的演算法以及一種有Pivoting且

可求得線性聯立方程式的系統Condition Number的演算法; 而這兩類演算法其時間復

雜度則分別為O(N)和O(NlogN)。

none