臺灣博碩士論文加值系統

矩陣的運算是工程上及科學上的重要核心，而稀疏矩陣更是佔了這些矩陣的絕大部分，然而沒有經過處理的稀疏矩陣在計算上和儲存上會造成很大的浪費，所以稀疏矩陣如何有效的計算和儲存就成為一個被研究的問題。本論文針對稀疏矩陣的準確及有效運算問題，我們使用選擇部分樞紐方法和動態記憶體分配方式對稀疏矩陣做平行高斯消去法分解，使工程上及科學上所產生的稀疏矩陣能夠準確及快速的求解；在論文中我們使用CCS壓縮、block-cyclic(k)分佈、動態記憶體分配、及選擇部分樞紐的方法平行處理稀疏矩陣做高斯消去法分解的問題，我們的作法使得像b1_ss、bcsstm19…這種原來有對角元素為零或分解過程會產生對角元素為零的矩陣在平行的情況下也能快速及準確的分解，並且使矩陣分解後所得的解有良好的準確性。
關鍵字：稀疏矩陣、高斯消去法、部分樞紐、block-cyclic(k)分佈

Matrix computation is at the core of many engineering and scientific. Sparse matrices are the most part of those matrices. If sparse matrices aren’t been compressed, it will cause much overhead in computation and storage. So efficient compute and store sparse matrices been a researching topic. In this thesis we use partial pivoting method and dynamic memory allocate method factorize sparse matrix in parallel, and suppose a precise and efficient computing sparse matrix system. In this thesis we compressed sparse matrix with CCS compressed scheme, distributed matrix data with column block-cyclic(k) distribution, maintained computation stability with partial pivoting, and did Gaussian Elimination with matrix in parallel. Our method can avoid diagonal-zero matrices such as b1_ss, and bcsstm19, and can factorized matrices efficiently and precisely in parallel.
Keyword: sparse matrix, Gaussian Elimination, partial pivoting, block-cyclic(k)

第一章 概論………………………………………………………………………….1
1.1簡介…………………………………………………………………………….1
1.2研究動機及方向……………………………………………………………….6
第二章 相關研究…………………………………………………………………….8
第三章 稀疏矩陣的壓縮和平行處理的資料分佈…………………………………18
3.1 稀疏矩陣的壓縮方法………………………………………………………...18
3.2 平行處理矩陣資料的分佈方法……………………………………………...22
3.3 使用的壓縮和分佈方法……………………………………………………...25
第四章 使用部份樞紐的高斯消去法………………………………………………26
4.1 高斯消去法簡介……………………………………………………………….26
4.2 高斯消去法的運算和演算法………………………………………………….26
4.3 部份樞紐方法………………………………………………………………….28
4.4 稀疏矩陣使用部份疏紐的高斯消去法……………………………………….31
第五章效能評估和比較………………………..……………………………………35
5.1 測試環境……………………………………………………………………….35
5.2 測試資料……………………………………………………………………….35
5.3 實驗結果……………………………………………………………………….36
5.3.1稀疏矩陣採用壓縮和不採用壓縮的效能比較…………………………………………..36
5.3.2稀疏矩陣計算是否使用選擇樞紐的方法的比較………………………………………..38
5.3.3與SuperLU比較…………………………………………………………………………..42
第六章 結論和未來工作…………………………………………………………..46
參考文獻……………………………………………………………………………48

[1] Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June M. Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, and Henk Van der Vorst, ”Templates for the Solution of Linear Systems:Building Blocks for Iterative Methods” http://www.netlib.org/templates/Templates.html
[2]Gerardo Bandera and Emilio L. Zapata, “Sparse Matrix Block-Cyclic Redistribution,” In Proceedings of IEEE International Parallel Processing Symposium, April 1999.
[3] Aart J.C. Bik and Harry A.G. Wijshoff, “Compilation Techniques for Sparse Matrix Computations,” In Proceedings of Supercomputing, pages 430-439, 1993.
[4] Tyng-Ruey Chung, Rong-Guey Chang, and Jenq Kuen Lee, “Sampling and Analytical Techniques for Data Distribution of Parallel Sparse Computation,” In SIAM Conference on Parallel Processing for Scientific Computing, March 1997.
[5] Tyng-Ruey Chung, Rong-Guey Chang, and Jenq Kuen Lee, “Efficient Support of Parallel Sparse Computation for Array Intrinsic Functions of Fortran 90,” In the 12th ACM International Conference on Supercomputing, July 1998.
[6] Iain S. Duff, ”Direct Method,” Tech. Rep. Rutherford Appleton Laboratory, Oxford University Press,1989
[7] T. A. Davis, “User’s guide for the unsymmetric-pattern multifrontal package (UMFPACK), Tech. Rep.,Computer and Sciences Department, University of Florida, June 1993.
[8] I. S. Duff, and J. K. Reid, “MA48,a Fortran code for direct solution of sparse unsymmetric linear systems of equations.” Tech. Rep.,Rutherford Appleton Laboratory, Oxan, UK, 1993.
[9] J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, and J.W. Liu,” A Supernodal Approach to Sparse Partial Pivoting,” SIAM J. Matrix Anal. Appl.
[10] James W. Demmel, John R. Gilbert, Xiaoye S. Li, “An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination,” Tech Rep. September 27, 1997
[11]Cong Fu and Tao Yang, “Efficient Run-time Support for Irregular Task Computations with Mixed Granularities,” In Proceedings of IEEE International Parallel Processing Symposium, Hawaii, April 1996.
[12]Cong Fu and Tao Yang, “Run-time Compilation for Parallel Sparse Matrix Computations,” In Proceedings of International Conference on Supercomputing, May 1996.
[13]A. George, M. T. Heath, J. W. H. Liu, and E. G.-Y.Ng,”Sparse Chlesky
Factorization on a Local Memory Multiprocessor”,SIAM J. Scientific and Statistical Computing, vol 9, pp. 327-340,May 1989.
[14] Anshul Gupta, George Karypis, and Vipin Kumar, ”Highly Scalable Parallel Algorithms for Sparse Matrix Factorization,” IEEE Trans. on Parallel and Distributed Systems,vol 8, no 5,pp. 502-519, May, 1997
[15] A. George, J. W. H. Liu, and E. G.-Y. Ng,”Communication Results for Parallel Sparse Chlesky Factorization on a Hypercube,”Parallel Computing, vol. 10, no. 3, pp.287-298,May 1989.
[16] A. Gupta and E. Rothberg,”An Efficient Block-oriented Approach to Parallel Sparse Chlesky Fcatorization,”Proc. Supercomputing 93,1993
[17] M. T. Heath, E. G.-Y. Ng, and B. W. Peyton,”Parallel Algorithms for Sparse Linear Systems,”SIAM Rev.,vol.33,pp.420-460,1991.
[18] Vladimir Kotlyar, Keshav Pingali, and Paul Stodghill, “Compiling Parallel Sparse Code for User-Defined Data Structures,” In Proceedings of 8th SIAM Conference on Parallel Processing for Scientific Computing, March 1997.
[19] Vladimir Kotlyar, Keshav Pingali, and Paul Stodghill, “A Relation Approach to the Compilation of Sparse Matrix Programs,” In Euro Par, August 1997.
[20]Young Won Lim, Prashanth B. Bhat, and Viktor K. Prasanna, Efficient Algorithms for Block-Cyclic Redistribution of Arrays, IEEE conference, pp. 74-83, 1996
[21] X. S. Li, and J. W. Demmel, “Making Sparse Gaussian Elimination Scalable by Static Pivoting,” Proceedings of SC 98,1998
[22] Loic Prylli,” Block Cyclic Array Redistribution,” Tech. Rep., Ecole Normale Supérieure de Lyon Octobre 1995
[23] E. Rothberg and R. Schreiber,”Improved Load Distribution in Parallel Sparse Cholesky Factorization,”Proc. Supercomputing 94,1994.
[24] Rajeev Thakur, Alok Choudhary, and J. Ramanujam, “Efficient Algorithms for Array Redistribution,” IEEE Trans. On Parallel and Distributed Systems, pp587-594, June 1996
[25]http://www.nhse.org/rib/repositories/nhse/catalog/#Numerical_Programs_and_Routines
[26]http://www.netlib.org/
[27]http://www.nhse.org/rib/repositories/nhse/catalog/
[28]http://www.netlib/org/utk/papers/iterative-survey/