Abstract
解大型線性方程組因需大量的數值計算，故需時甚久。以直接法解的時間復雜度(Time Complexity) 為O(N), 其中n為方程組的維度(dimension)。如何縮短求解時間，已有許多前人作了詳細的研究。近年由於多處理機系統(Multiprocessor Systems)的問世，使此問題能以較短的時間求得解。然而不同的問題在不同架構下須採不同的演算法，以達成不同的需求。超立方體(hypercube) 架構因能包容其他許多架構，例如環(ring)、網(mesh)、樹(tree)，并且許多形式的通訊在超立方體中需較少的時間，因而許多多處理機系統採用了超立方體架構，例如InteliPSC、NCUBE及Floating Point Systems T-series 。本文探討在超立方體架構下，求解緊密(dense)及稀疏(sparse) 線性方程組的演算法。我們探討以超立方體架構多處理機系統解緊密聯立方程組的演算法。在此採用高斯消去法(Gaussian Elimination)予以并行化。在高斯消去法中，消去一行的動作可分為三步驟(詳見附錄)，其中一步驟需將一列由一個處理機經過廣播(broadcast) 傳送給其他處理機，其他步驟為算術運算。故此廣播速度影響整個消去法的快慢。在此所考慮的廣播演算法有recursive doubling及pipeline。Resursive doubling法雖能很快的完成廣播動作，但因所有的處理機要等到廣播動作結束後才能作算術運算，結果所較pipeline方式差。在許多應用中，所需要解的線性聯立方程組常為稀疏(sparse)的，即維度很大，但其中非零項所佔的比例很少。由一些問題( 例如有限元素法) 所產生的矩陣更具有對稱(symmetrical),正定(Positive definite) 等特性，針對此種線性聯立方程組，常採用Cholesky factorization求解，本章討論在應用超立方體計算機以平行演算法求解稀殊矩陣時，不同的任務分配(task assignment) 演算法方法及結果比較。實驗結果告訴我們，既使超立方體架構一般具有良好的通訊能力，然而在某此計算/通訊交錯的問題上, 採用超立方體架構不一定得到很大的好處, 反而採用其他形式的架構會較好。解衡疏線性聯立方程組則除要使各處理機負荷盡量接近之外，尚須考慮彼此間的通訊次數。