GPU Accelerated Lanczos Algorithm with Applications

Graphics Processing Units provide a large computational power at a very low price which position them as an ubiquitous accelerator. GPGPU is accelerating general purpose computations using GPU’s. GPU’s have been used to accelerate many Linear Algebra routines and Numerical Methods.Lanczos is an iterative method well suited for finding the extreme eigenvalues and the corresponding eigenvectors of large sparse symmetricmatrices.In this paper, we present an implementation of Lanczos Algorithm on GPU using the CUDA programming model and apply it to two important problems : graph bisection using spectral methods,and image segmentation. Our GPU implementation of spectral bisection per forms better when compared to both an Intel MathKernel Library implementation and a Matlab implementation.Our GPU implementation shows a speedup up

to 97.3 times over Matlab Implementation and 2.89 times over the Intel Math Kernel Library implementation on a Intel Core i7 920 Processor, which is a quad- core CPU. Similarly, our image segmentation implementation achieves a speed up of 3.27 compared to a multicore CPU based implementation using Intel Math Kernel Library and OpenMP. Through this work, we therefore wish to establish that the GPU may still be a better platform for also highly irregular and computationally intensive applications. I. INTRODUCTION The computationalpower of GPUs is increasing rapidly in the last few years. Coupled with the availability of programming environments such as CUDA, GPUsare being used for also general purpose computations.This trend is called GPGPU and presently several fundamental applications are available on GPUs. Examples include sparse matrix vector multiplication[1], SVD [7], and others. There are many problemswhich can be modeledas graphs and can be solved by formulating them as discrete combi- natorial optimizationproblems. Some of them include spec- tral graph partitioning,spectral image segmentation,spectral clustering, spectral graph layout and the like. Most of the aforementioned problems have a lot of practical applications, but posed as discrete optimization problems, these are hard to solve as they generally tend to be NP-complete problems. But real approximations to these problems can be solved using linear algebra methods like finding the spectrum of the Laplacian or adjacency matrix. These solutions require one to compute the extreme eigenvalues and corresponding eigenvectors of the Laplacian matrix of an underlying matrix. This approach of using the extreme eigenvalues, and the corresponding eigenvectors,also finds applications to many other problems from various settings such as computing page ranks [9], and latent semantic indexing. In general, the matrices involved in these computations are large, sparse, symmetric, and are real valued. Lanczos method is well suited for such problems.Lanczosmethodinvolves partial triadiagonalization on the given matrix, say A. Important information about the extremal eigenvalues of a matrix tends to emerge long before the tridiagonalizationis complete. This makes the Lanczos algorithm particular lyusefulin cases where a few of the largest or smallest eigen values of A are desired.Further, the onlylarge scale-operation involved is sparsematrix-vector multiplication which can be implemented as a black box. In this work, we implement Lanczos algorithm on a GPU and study two applications of the Lanczos algorithm : graph bisection with spectral methods,and image segmentation. Given an undirected graph G, with vertex set V(G) and edge setE(G), and a positive integerk, the graph partitioning problem is to partition the graph G into k partitions. The partitions have to satisfy two conditions. Firstly, each partition has an equal number of vertices....

Website: cstar.iiit.ac.in | Filesize: -
No of Page(s): 6
Download GPU Accelerated Lanczos Algorithm with Applications.pdf