Abstract
Chordal graph 與相當多的問題有很大的關連，尤其是有關解疏散式線性方程組的問題。在本篇博士論文裹，我們提出若干快速平行計算方法來解一些與 Chordal graph有關的問題。這些問題可分成兩個部分。第一個部分是直接與Chordal graph 有關的問題。這部分的問題包括認定Chordal graph 的問題及在Chordal graph 上找一些特定的事物，這些事物包括maximal clique，clique true ，minimum coloring，及perfect elimination scheme。我們的做法比起以前人的做法有很大的改進。我們把解這些問題所需的處理器個數從０（ n□）或０（ n□）降到０（ n□），並且把所需的計算時間從０（log□n）降到０（logn），其中n 是代表頂點的個數。我們第二部分解的問題是解疏散式三角線性方程組。我們提出兩個平行計算方法來解這個問題。這兩個方法都比前人的解法快很多。第一個方法是解一般的疏散式三角線性方程組。一些模擬的結果顯示這個方法的執行時間隨給定方程組的疏散性而改變。第二個方法，利用第一個方法當副程式，是用來解一些特定的疏散線性方程組，這些方程組的係數矩陣是得自某一對稱矩陣的LU分解。我們應用很多Chordal graph 的特性來設計第二個計算方法並分析這兩個計算方法的執行效率。