The sparse matrix is one of the most important data storage format for large amount of data. Sparse matrix-vector multiplication (SpMV) is important operation in many scientific and engineering applications. Many physical systems produce sparse matrices. Sparse matrix-vector multiplication can be implemented sequentially and it includes various methods like one dimensional cache-oblivious method, this method extended to two dimensional methods and Hilbert space filling curve. There is limitation of sequential case as it is not providing efficient result. There are some problems occur related to sequential case of multiplication that are less arithmetic intensity, cache inefficiency and limited memory bandwidth. To avoid such problem parallel techniques were introduced. It mainly focuses on high level strategies for efficient performance of sparse matrix-vector multiplication. High level strategies include no vector distribution, one dimensional distribution and two dimensional distributions. This provides high arithmetic intensity and better performance as compared to sequential technique on NUMA Architecture.

1. Albert-Jan Nicholas Yzelman and Dirk Roose, "High-Level Strategies for Parallel Shared-Memory Sparse Matrix-Vector Multiplication," IEEE Transaction on parallel and distributed systems, vol. 25, no. 1, Jan 2014.
2. M. R. Hestenes and E. Stiefel, "Methods of ConjugateGradients for Solving Linear Systems," J. Research Nat'lBureau of Standards, vol. 49, pp. 409-436, 1952.
3. H. van der Vorst, "BiCGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems," SIAM J. Scientific and Statistical Computation, vol. 13, pp. 631-644, 1992.
4. Y. Saad and M. Schultz, "GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems," SIAM J. Scientific and Statistical Computation, vol. 7, pp. 856-869,1986.
5. P. Sonneveld and M. B. van Gijzen, "IDR: A Family of Simple and Fast Algorithms for Solving Large Non symmetric Linear Systems," SIAM J. Scientific Computing, vol. 31, no. 2, pp. 1035- 1062, 2008.
6. A. N. Yzelman and R. H. Bisseling, "Cache-Oblivious Sparse Matrix-Vector Multiplication by Using Sparse Matrix Partitioning Methods," SIAM J. Scientific Computing, vol. 31, no. 4, pp. 3128- 3154, 2009.
7. A. N. Yzelman, "Fast Sparse Matrix-Vector Multiplication by Partitioning and Reordering," PhD dissertation, Utrecht Univ. , 2011.
8. A. Buluc¸, S. Williams, L. Oliker, and J. Demmel, "Reduced- Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication," Proc. IEEE Int'l Parallel and Distributed Processing Symp. (IPDPS '11), pp. 721- 733, 2011.

Sparse Matrix-vector Multiplication (spmv) Cache-oblivious Numa Architecture