Reduction of a Symmetrical Matrix to Tridiagonal Form on GPUs

Shuotian Chen
Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign, 2014


   title={Reduction of a Symmetrical Matrix to Tridiagonal Form on GPUs},

   author={Chen, Shuotian},



Download Download (PDF)   View View   Source Source   



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.
Rating: 2.0/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: