# GPU Algorithms for Structured Sparse Matrix Multiplication with Diagonal Storage Schemes +
## 7 Experimental Results
### Structured Sparse Matrix Multiplication  
In this section, we evaluate GPU matrix-matrix multiplication algorithms for structured sparse matrices, i.e., matrices where the nonzero diagonals are arbitrarily distributed instead of being confined within a narrow band around the main diagonal. In other words, the class of banded matrices can be considered as a special case of the class of structured sparse matrices. Numerical methods for solving partial differential equations using finite-difference discretization give rise to linear systems where the coefficient matrices display structured sparsity patterns. Standard banded matrix storage schemes including the one specified using BLAS are not directly applicable to structured sparse matrices. Consequently, structured sparse matrices can be treated as general sparse matrices and be stored, for example, in a compressed sparse row (CRS) requiring auxiliary data structures. Thus, the class of structured sparse matrices presents an interesting case study on its own. Figure 6: Comparison of CPU and GPU times for banded matrix multiplications. Figure 7: Relative improvements for GPU timings compared to CPU timings for banded matrix multiplication (matrix size 10,240). In Tables 1 and 2, we present the running time of CPU and GPU structured sparse matrix multiplication experiments. The nonzero diagonals are randomly picked for the argument matrices \(A\) and \(B\). We include the number of diagonals (dgA, dgB) as well as the total number of nonzeros (nzA, nzB) for arguments \(A\) and \(B\), respectively. It is to be emphasized that the product \(C\) need not have a structured sparse form. In fact, \(C\) may contain partially filled (with nonzeros) diagonals. In Table 1, we vary both matrix size and number of diagonals in the generated test matrices \(A\) and \(B\). The running times for the CPU and GPU implementations exhibit relative performance profiles similar to that for banded matrices. The running time performance of CPU and GPU improves with the matrix size and the number of diagonals because of the increase in the computational work and the improved data locality. Moreover, the relative performance (the ratio of CPU and GPU running time) shows good scalability, yielding a speedup of 65 times. In Table 2, the matrix dimension is held constant at 10  
diagonal storage schemes HM and CDM. An extensive set of numerical experiments with banded and structured sparse matrices convincingly established the advantage of our diagonally structured storage mechanism in implementing matrix-matrix multiplication, a computational workhorse in scientific computation. The experiments clearly demonstrate that the implemented GPU algorithms are highly scalable and give significant parallel speedups, up to two orders of magnitude. The storage scheme based on matrix diagonals, as opposed to rows/columns, provides an alternative approach to implementing linear algebraic kernel operations in the BLAS specification. More specifically, this new storage scheme avoids explicit matrix transposition and thereby has the potential to improve the performance of BLAS level-2 and level-3 operations. We are currently developing sequential, multicore, and many-core parallel algorithms for general sparse matrix multiplication. S.A.H. : Conceptualization, methodology, writing--original draft preparation, software,; M.T.P. : validation, writing--review and editing, visualization; S.H. : Conceptualization, methodology, writing--review and editing. All authors have read and agreed to the published version of the manuscript. This research received no external funding. No new data were created or analyzed in this study. Data sharing is not applicable to this article. S.A.H. : Conceptualization, methodology, writing--original draft preparation, software,; M.T.P. : validation, writing--review and editing, visualization; S.H. : Conceptualization, methodology, writing--review and editing. All authors have  
* [PERSON] et al.