On the improvement and acceleration of eigenvalue decomposition in spectral methods using GPUs

Abstract

The key objectives in this thesis are; the study of GPU-accelerated eigenvalue decomposition in an effort to uncover both benefits and pitfalls, and then to investigate and facilitate a future GPU implementation of the symmetric QR algorithm with permutations. With the current trend of having ever larger datasets both in terms of features and observations, we propose that GPU computation can help ameliorate the temporal penalties incurred by eigendecomposing large matrices. We successfully show the benefits of performing eigendecomposition on GPUs, and also highlight some problems with current GPU implementations. While implementing the QR algorithm on GPU, we discovered that the GPU-based QR decomposition does not explicitly form the orthogonal matrix needed as part of the QR algorithm. Therefore, we propose a novel GPU algorithm for “implicitly” computing the orthogonal matrix Q from the Householder vectors given by the QR decomposition. To illustrate the benefits of our methods, we show that the kernel entropy component analysis algorithm on GPU is two orders of magnitude faster than an equivalent CPU implementation.