請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49445完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王偉仲 | |
| dc.contributor.author | Yung-Kang Lee | en |
| dc.contributor.author | 李永康 | zh_TW |
| dc.date.accessioned | 2021-06-15T11:29:01Z | - |
| dc.date.available | 2016-08-26 | |
| dc.date.copyright | 2016-08-26 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-17 | |
| dc.identifier.citation | [1] Michael W Berry and Ricardo D Fierro. Low-rank orthogonal decompositions for information retrieval applications. Numerical linear algebra with applications, 3(4):301–327, 1996.
[2] Tony F Chan. Rank revealing qr factorizations. Linear algebra and its applications, 88:67–82, 1987. [3] Tony F Chan and Per Christian Hansen. Low-rank revealing qr factorizations. Numerical Linear Algebra with Applications, 1(1):33–44, 1994. [4] Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix. SIAM Journal on Computing, 36(1):158–183, 2006. [5] Ricardo D Fierro and Per Christian Hansen. Low-rank revealing utv decompositions. Numerical Algorithms, 15(1):37–55, 1997. [6] Ricardo D Fierro and Per Christian Hansen. Utv expansion pack: Special-purpose rankrevealing algorithms. Numerical Algorithms, 40(1):47–66, 2005. [7] Ricardo D Fierro, Per Christian Hansen, and Peter S?ren Kirk Hansen. Utv tools: Matlab templates for rank-revealing utv decompositions. Numerical Algorithms, 20(2-3):165–194, 1999. [8] Shai Fine and Katya Scheinberg. Efficient svm training using low-rank kernel representations. Journal of Machine Learning Research, 2(Dec):243–264, 2001. [9] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011. [10] Hao Ji and Yaohang Li. Gpu accelerated randomized singular value decomposition and its application in image compression. Update, 4:5, 2014. [11] Hui Ji, Chaoqiang Liu, Zuowei Shen, and Yuhong Xu. Robust video denoising using low rank matrix completion. In CVPR, pages 1791–1798. Citeseer, 2010. [12] Tsung-Lin Lee, Tien-Yien Li, and Zhonggang Zeng. A rank-revealing method with updating, downdating, and applications. part ii. SIAM Journal on Matrix Analysis and Applications, 31(2):503–525, 2009. [13] Jing-Rebecca Li. Model reduction of large linear systems via low rank system gramians. PhD thesis, Massachusetts Institute of Technology, 2000. [14] Tien-Yien Li and Zhonggang Zeng. A rank-revealing method with updating, downdating, and applications. SIAM Journal on Matrix Analysis and Applications, 26(4):918–946, 2005. [15] Stanimire Tomov, Jack Dongarra, and Marc Baboulin. Towards dense linear algebra for hybrid GPU accelerated manycore systems. Parallel Computing, 36(5-6):232–240, June 2010. [16] Jiani Zhang, Jennifer Erway, Xiaofei Hu, Qiang Zhang, and Robert Plemmons. Randomized svd methods in hyperspectral imaging. Journal of Electrical and Computer Engineering, 2012:3, 2012. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/49445 | - |
| dc.description.abstract | Rank is an important characteristic of a matrix. In this thesis, we realize a known efficient rank-revealing algorithm out of MATLAB, into native C++ environment to achieve greater efficiency.
Further more, we utilize the power of GPGPU (General Purpose Graphic Process Unit) to further accelerate the algorithm. The algorithm gained its efficiency due to utilization of basic BLAS routine instead of more expensive LAPACK routine, which translates well to acceleration on GPGPU. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T11:29:01Z (GMT). No. of bitstreams: 1 ntu-105-R03246003-1.pdf: 527547 bytes, checksum: 98ed0f8000b4c041c514fda61959e1df (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 摘要i
Abstract ii 1 Introduction to Rank Revealing 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Other Rank Revealing algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Our Rank Revealing Algorithm 3 2.1 Low Rank Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Low Rank : First Iteration and Convergence Criteria . . . . . . . . . . 4 2.1.3 Low Rank : Second Iteration and Beyond . . . . . . . . . . . . . . . . 6 2.1.4 Low Rank Algorithm Overview . . . . . . . . . . . . . . . . . . . . . 9 2.1.5 Low Rank Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Low Rank Updating and Downdating . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Updating Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 Block Updating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.4 Downdating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 High Rank Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 High Rank: First Iteration . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 High Rank: Second Iteration and Beyond . . . . . . . . . . . . . . . . 17 2.3.4 High Rank Algorithm Overview . . . . . . . . . . . . . . . . . . . . . 18 2.4 Theoretical Difference between this algorithm and other algorithms . . . . . . 20 3 Code Implementation 21 3.1 Low Rank Revealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.1 USV-decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Updating and Downdating . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 High Rank Revealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3.1 Updating Q and R for next iteration . . . . . . . . . . . . . . . . . . . 24 4 Algorithm on GPU 25 4.1 GPU overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 Our Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3 Implementation of other algorithms . . . . . . . . . . . . . . . . . . . . . . . 27 5 K-Principal Revealing 28 5.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6 Low Rank Multi-Card GPU implementation 31 6.1 Dividing A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.2 Implementation Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.3 Calculating Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.4 Multi-CPU Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7 Rank-Revealing Package 34 7.1 Function Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.2 How to use the package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 8 Numerical Experiment 37 8.1 Testing Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 8.2 Low Rank Theoretical Complexity . . . . . . . . . . . . . . . . . . . . . . . . 38 8.3 Low Rank Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 8.4 K-Principal Revealing Results . . . . . . . . . . . . . . . . . . . . . . . . . . 43 8.5 Low Rank Updating result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 9 Conclusion 48 Bibliography 50 | |
| dc.language.iso | en | |
| dc.subject | GPU | zh_TW |
| dc.subject | 矩陣 | zh_TW |
| dc.subject | 秩 | zh_TW |
| dc.subject | C++ | zh_TW |
| dc.subject | CUDA | zh_TW |
| dc.subject | GPU | en |
| dc.subject | Matrix | en |
| dc.subject | Rank Reveal | en |
| dc.subject | C++ | en |
| dc.subject | CUDA | en |
| dc.title | 用CPU 與GPU 來實現找尋矩陣秩的演算法 | zh_TW |
| dc.title | Realizations of Rank-Revealing Algorithms on CPU and GPU | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳素雲,李宗錂 | |
| dc.subject.keyword | 矩陣,秩,C++,CUDA,GPU, | zh_TW |
| dc.subject.keyword | Matrix,Rank Reveal,C++,CUDA,GPU, | en |
| dc.relation.page | 53 | |
| dc.identifier.doi | 10.6342/NTU201602841 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-17 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 應用數學科學研究所 | zh_TW |
| 顯示於系所單位： | 應用數學科學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 515.18 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。