用CPU 與GPU 來實現找尋矩陣秩的演算法

Realizations of Rank-Revealing Algorithms on CPU and GPU

李永康(Yung-Kang Lee)

指導教授 ： 王偉仲

國立臺灣大學/理學院/應用數學科學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201602841

摘要

無資料

關鍵字

矩陣 ； 秩 ； C++ ； CUDA ； GPU

並列摘要

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.

並列關鍵字

Matrix ； Rank Reveal ； C++ ； CUDA ； GPU

參考文獻

[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.