Reduction of a Symmetrical Matrix to Tridiagonal Form on GPUs

Chen, Shuotian

Permalink

https://hdl.handle.net/2142/73823 Copy

Description

Title

Reduction of a Symmetrical Matrix to Tridiagonal Form on GPUs

Author(s)

Chen, Shuotian

Contributor(s)

Kindratenko, Volodymyr

Issue Date

2014-12

Keyword(s)

• Eigenvalue
• Eigenvector
• Givens Method
• GPU
• CUDA

Abstract

Many eigenvalue and eigenvector algorithms begin with reducing the input matrix into a tridiagonal form. A tridiagonal matrix is a matrix that has non-zero elements only on its main diagonal, and the two diagonals directly adjacent to it. Reducing a matrix to a tridiagonal form is an iterative process which uses Jacobi rotations to reduce matrix elements to zero. The purpose of this research project is to implement an existing algorithm for tridiagonal reduction using CUDA, thus leveraging the parallelism present in GPUs to accelerate the process. In a serial implementation of the algorithm, at each step only the elements in 2 rows/ columns are modified. Therefore, the CUDA implementation takes the form of a parallel reduction algorithm which will simultaneously apply multiple Jacobi rotations to the matrix, thus zeroing out multiple elements at the same time. The CUDA implementation of this algorithm was measured to have a performance improvement of roughly an order of magnitude for sufficiently large matrices as compared to the reference serial CPU implementation. This result shows that the parallel algorithm is able to successfully exploit the GPU’s parallel architecture and provide a significant improvement to the performance of the original algorithm.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/73823

Owning Collections