(3.230.76.48) 您好!臺灣時間:2021/04/15 01:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:何錦文
研究生(外文):HE, JIN-WEN
論文名稱:與CHORDAL-GRAPH有關的一些快速平行計算方法
論文名稱(外文):Fast parallel algorithms related to chordal graph
指導教授:李家同李家同引用關係
指導教授(外文):LI, JIA-TONG
學位類別:博士
校院名稱:國立清華大學
系所名稱:計算機管理決策研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:1988
畢業學年度:76
語文別:中文
論文頁數:140
中文關鍵詞:平行計算線性方程式
相關次數:
  • 被引用被引用:0
  • 點閱點閱:145
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
Chordal graph 與相當多的問題有很大的關連,尤其是有關解疏散式線性方程組的問
題。在本篇博士論文裹,我們提出若干快速平行計算方法來解一些與 Chordal graph
有關的問題。這些問題可分成兩個部分。第一個部分是直接與Chordal graph 有關的
問題。這部分的問題包括認定Chordal graph 的問題及在Chordal graph 上找一些特
定的事物,這些事物包括maximal clique,clique true ,minimum coloring,及pe
rfect elimination scheme。我們的做法比起以前人的做法有很大的改進。我們把解
這些問題所需的處理器個數從0( n)或0( n)降到0( n),並且把所需
的計算時間從0(logn)降到0(logn),其中n 是代表頂點的個數。我們第二部
分解的問題是解疏散式三角線性方程組。我們提出兩個平行計算方法來解這個問題。
這兩個方法都比前人的解法快很多。第一個方法是解一般的疏散式三角線性方程組。
一些模擬的結果顯示這個方法的執行時間隨給定方程組的疏散性而改變。第二個方法
,利用第一個方法當副程式,是用來解一些特定的疏散線性方程組,這些方程組的係
數矩陣是得自某一對稱矩陣的LU分解。我們應用很多Chordal graph 的特性來設計第
二個計算方法並分析這兩個計算方法的執行效率。
目錄
摘要
誌謝
Chapter 1. Introduction
2.1 Basic Definitions and Notations
2.2 Characterizing Chordal Graphs
2.3 Sequential Algorithms for Recognizing Chordal Graphs
2.4 Chordal Graphs as Intersection Graphs
2.5 Chordal Graphs Are Perfect
2.6 Sequential Algorithms for Computing Maximum Cliques and Minimum Colorings on Chordal Graphs
2.7 Chordal Graphs and Gaussian Elimination for Solving Sparse Symmetric Linear Systems of Equations
Chapter 3. Parallel Algorithms for Finding Maximal Cliques and Clique Trees on Chordal Graphs
3.1 Introduction
3.2 Parallel Recognition Algorithms for Chordal Graphs
3.3 Parallel Computation for Maximal Cliques on Chordal Graphs
3.4 Parallel Computation for Constructing Clique Trees
3.5 Summary
Chapter 4. Parallel Computation of Minimum Colorings and Perfect Elimination Schemes on Chordal Graphs
4.1 Introduction
4.2 Basic Parallel Implementations
4.3 A Fast Parallel Algorithm for Finding Minimum Colorings on Chordal Graphs
4.4 A Fast Parallel Algorithm for Computing Perfect Elimination Schemes
Chapter 5. Two Parallel Algorithms for Solving Sparse Triangular Systems
5.1 Introduction
5.2 Previous Results
5.3 The Graph-Theoretic Approach to Solve the Sparse Triangular System of Equations
5.4 Elimination Trees of Chordal Graphs
5.5 A Parallel Algorithm for Solving Some Special Sparse Triangular Systems
Chapter 6. Concluding Remarks
References
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔