簡易檢索 / 詳目顯示
| 研究生： |
林伯勳 Lin, Frank |
|---|---|
| 論文名稱： |
線性三對角方程組之平行解法 Parallel Algorithm for Linear Tridiagonal System Solver |
| 指導教授： |
施東河
Shih, Dong Ho |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 1993 |
| 畢業學年度： | 82 |
| 語文別： | 中文 |
| 論文頁數： | 35 |
| 中文關鍵詞： | 線性三對角方程組 、超立方體網路 、平行演算法 |
| 外文關鍵詞： | Linear Tridiagonal System, hypercube network, parallel algorithm |
| 相關次數： | 點閱：288 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本論文對線性三對角方程組之解法提出平行演算法於超立方體網路 (
hypercube network), 並且此平行演算法能達到最佳費用 (optimal
cost ) O(N). 討論的解法包含 (1)循環消減法 (cyclic reduction
method)及 (2)高斯消去法 (Gaussian elimination method), 基於
(1)法之平行演算法當使用處理器個數為 O(N/logN)時, 其執行時間為 O(
logN); 基於 (2) 法之平行演算法當使用處理器個數為 O(N/(logN)^2)
時, 其執行時間為 O((logN)^2); 費用 (cost) 等於處理器個數乘以執行
時間.
第一章 簡介﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒2
第二章 循環消減法之平行演算法
2﹒1 方法介紹﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒6
2﹒2 循環消減法之平行演算法於超立方體網路﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒10
2﹒3 循環消減法之平行演算法於縮減之超立方體網路﹒﹒﹒﹒﹒﹒﹒﹒﹒16
2﹒4 費用最佳化及時間分析﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒19
第三章 高斯消去法之平行演算法
3﹒1 方法介紹﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒21
3﹒2 計算尾數值﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒25
3﹒3 三階演算法(Three-phase algorithm)於縮減之超立方體網路﹒﹒﹒﹒﹒﹒28
3﹒4 費用最佳化及時間分析﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒32
第四章 結論﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒33
參考文獻﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒34
(1) A. H. Samen and D. J. Kuck, A parallel QR algorithm for symmetric tridiagonal matrices, IEEE Trans. Comp. Vol c-26(2), (1977):147-155.
(2) Buzbee B. L., Golub G. H., and Nielson C. W., On direct methods for solving poisson’s equations, SIAM J. Number. Anal. 7, 4(dec, 1970): 627-656.
(3) C. D. Thompson, Area-time complexity for VLSI, Proc. Of the llth ACM symposium on the theory of computing, ACM, (1979):81-88.
(4) C. D. Thompson, A complexity theory for VLSI, Technical Report, Dept. Of computer science, Carnegie-Mellon University, Pittsburgh, pA,,1980.
(5) Ferng-Ching Lin and Kuo-Liang Chung, A cost-optimal parallel tridiagonal system solver, Parallel Computing 15 (1990)189-199.
(6) Ferng-Ching Lin, Kuo-Liang Chung and Yeong-Nan Yeh, A linear recurrence solver, Proceedings of International Computer Symposium (1990) December 17-19, Hsinchu, Taiwan, R.O.C.
(7) M. J. Flynn, Very high-speed computing systems, proc. Of the IEEE 12:1901-1909 (1966)
(8) G.H. Golub and C. F. Van Loan, Matrix Computations (North Oxford Academic, Oxford, 1983)
(9) H. H. Wang , A parallel method for tridiagonal equations, ACM Trans. Math. Software 7(2) (1981):170-283.
(10) H. S. Stone, parallel tridiagonal equation solvers, ACM Trans. Math. Software, 1, NO.4,(1975):289-307.
(11) Programming, vol 16, No.2 (1987):127-136.
(12) J. Lambiotte and R. Voigt, The solution of tridiagonal linear systems on the CDC STAR-100 computer, ACM Trans. Math. Software.,1, 4(Dec. 1975):308-329.
(13) S. A. Browning, The tree machine : A highly concurrent computing environment, Technical Report, (1980):TR:3760, Computer science, California Institute of Technology, Passdena, CA, January, 1980.
(14) S. Lakshmivarahan and Sudarshan K. Dhall, Analysis and Design of Parallel Algorithms, (MacGraw-Hill Publishing Company, New York, International edition, 1990)
(15) SANJAY RANKA and SARTAJ SAHNI, odd Even Shifts in SIMD Hypercubes, IEEE TRANS. Parallel and distributed systems, vol. 1, No.1, Jan(1990)
(16) C. L. Seitz, The cosmic cube, CACM(1984)
(17) P. N. Swarztrauber, A parallel algorithm for solving general tridiagonal equations, Math. Comp., vol. 33. (1979):185-199.
(限達賢圖書館四樓資訊教室A單機使用)