圖形上點消去演算法

Abstract

在使用高斯消去法解其係數矩陣呈正對稱且稀疏之聯立方程式中，因矩陣在消去過程 裡有一些為零之元素變成了非零之元素，我們稱為「塞滿」。為了使高斯消去法更有 效地執行，一個重要之目標是將「塞滿」 減到最小限度。 本篇論文利用圖形理論中之「三角圖形」之性質，給了二個演算法，其一為「辭典編 纂的搜尋法則」，其一為「最大數量搜尋法」，它們不但可以找到一組予到有效地減 少「塞滿」，而且假如存在，還可以找到沒有「塞滿」之序列。此外我們提出一個新 法則，它能將所有給之任意予列計算出「塞滿」之位置及個數。另外我們也概略地觀 察幾個其他則，用來比較。結果顯示「最大數量搜尋法則」對尋找一組好序列是一個 好的演算法則。