Optimization of Sparse Matrix Vector Multiplication

Abstract

Sparse Matrix Vector Multiplication(SpMV) plays an important role in Data Mining Algorithms and Linear Iterative Solvers as they rely on Eigen values computation. In this type of applications major execution time is consumed by SpMV. Sparse Matrix contains large number of zeros elements, which results in irregular memory access pattern. Irregular memory access reduces the performance of SpMV. This thesis includes study and implementation of efficient storage methods of Sparse Matrix and the Reordering techniques to improve the locality of data which results in reduction in execution time. GPUs highly parallel structure is more effective for compute intensive applications. By implementing SpMV, which is a compute intensive kernel on GPU, it can give massive speed-up to applications of Mining and Linear Iterative Solvers.