Abstract
在科學與工程上，有許多問題必須花費很多的計算時間。因此為縮短計算時間，許多並行計算方法，已經廣泛地發展及研究。當然這些並行方法是在能並行計算的機器上執行，例如陣列多處理機（Mesh）及樹狀多處理機（Tree Machine），而這些機器是由許多個處理器所組合成的。近年來，多立方體結構的機器（Hypercube ）逐漸引起重視及研究，並且已有多架商品化的機器（如美國Intel 公司的iPSC-VX ），可以真正地測試程式的好與壞。Hypercube 有許多優點，例如很容易做Broadcasting，以及可將其對應成一Mesh或Tree Machine，亦即可隨問題的特性而來應用Hypercube 。線性代數的問題，通常需要很多的計算時間，因此我們希望能在Hypercube 上解這類問題，以加速計算。線性系統（Linear System ）是線性代數常見的問題，而一般是採用高斯消法來求解，但為了減少計算的誤差，高斯消去法通常要加上Piwoting。因此我們首先探討加上Pivoting後的高斯法如何在Hypercube 上求解。我們同時比較兩種不同切割資料的方法，可發現循環式（Cyclic）所需時間約只為連續式（Consecutive ）的1/3 。帶狀系統（Banded System ）是線性系統的特例，我們必須重新研究切割資料的方法，以減少處理器的個數及執行時間。對於帶狀系統，我們另外提出一種方法（Flow-Through），此方法可減少每一處理器所需的記憶空間。高斯－約旦法（Gauss-Jordan）是另一種可用來解線性系統的方法，有人認為其比高斯法好，此乃因其不必有後向代入法（Back Substitution ）。但我們發現只在使用連續式切割方法時，高斯－約旦法才較好。而且若系統是帶狀則高斯－約旦法效率皆不高，同時亦無法應用Flow-Through的方法。另外我們再探討一些線性代數問題，如LU-Decomposition、行列式求值、反矩陣、線性規劃，這一類問題的解法皆相似於高斯消去法，因此原先的討論皆可應用。論文後半段，乃研究如何求對稱矩陣的特徵值（Eigenvalue），我們採用並行的亞可比法（Jacobi Method ），此方法是屬於疊代法（Iterative Method）。我們提出二種方法，一種是利用Hypercube 的Broadcasting特性，另一種則利用Pipelined 的方法。當問題大小與Hypercube 大小相近時，Pipelined 的方法較佳，但若是在較小的Hypercube 上，此兩方法相差不大。