稀疏線性方程式求解改良及分析

Abstract

對於許多工程上的問題，例如電子電路的分析，求解稀疏線性方程式是很 重要的過程。若能掌握稀疏矩陣的特性而適當排列其行與列的順序，則可 明顯改善求解的效率。本論文提出一種基於矩陣切割的重排法 -- 矩陣切 割重排法；由矩陣的切割，我們定義了外部變數與內部變數。應用內部變 數與外部變數的概念，矩陣可以重新排列成一種新的特殊型式。而演算高 斯消去法於具有此種特殊型式的矩陣時，填充數產生的數目與位置能夠被 有效地控制，使得演算消去法時僅需較少的浮點運算次數，而達到求解效 率提昇的目的。在數值測試中，矩陣切割重排法求解的效率比其他兩種既 有的重排法好，而驗證了本論文所提出的重排演算法是相當可行的。 Solving sparse linear equations is a very important process for many applications in engineering problems, e.g. the analysis of electronic networks. It can be shown that using the sparsity of the linear system and properly permuting the associated matrix can result in efficient performance for solving the system. For this purpose, this thesis has proposed a reordering algorithm with a matrix partition process. The internal variables and external ones are discriminated during the matrix partition process. By using the discriminated internal and external variables, the matrices are reordered to a compressed form so that the numbers of fill-ins and floating point operations can be abruptly reduced in the Gaussian elimination process. By this way, the efficiency for the solving process is improved. In our test cases, experiments have shown that the performance of the proposed algorithm is better than two other algorithms, Markowitz reordering and RCM reordering.