# GPU Algorithms for Structured Sparse Matrix Multiplication with Diagonal Storage Schemes +
## 3 Storage Schemes
### Compact Diagonal Storage Scheme  
In this section, we will describe our proposed compact diagonal storage scheme. For the rest of the study, the two terms _\"Compact Diagonal\"_ and _\"CDM\"_ will be used interchangeably to denote our proposed storage scheme. Rather than computing the super- and subdiagonals of the product \(C=AB\) separately, we can pack compatible pairs of super- and subdiagonals in a vector of length \(n\). The \(k\)th superdiagonal for \(k=1,2,\ldots,n-1\) of matrix \(A\) is a vector \(\overline{A_{k}}\) of length \(n-k\)  
Figure 2: (a) A banded matrix, (b) column-major storage scheme for diagonals of (a), and (c) alternative column-major storage for (a). Here “\(\ast\)” means the the absence values as the diagonal size is equal or less than the dimensions of the matrix. \[\overline{A_{k}}=\left( \begin{array}{c}a_{0,k}\\ a_{1,k+1}\\ \vdots\\ a_{(n-k-1,n-1)}\end{array} \right).\]  
Likewise, the \(k\)th subdiagonal is a vector \(\underline{A_{k}}\) of length \(n-k\),  
\[\underline{A_{k}}=\left( \begin{array}{c}a_{k,0}\\ a_{k+1,1}\\ \vdots\\ a_{(n-1,n-k-1)}\end{array} \right).\]  
We define the \(k\)th _compact diagonal_ as  
\[A_{k}=\left( \begin{array}{c}\overline{A_{k}}\\ \underline{A_{n-k}}\end{array} \right)\]  
where the \(k\)th superdiagonal is stacked on top of the \((n-k)\)th subdiagonal. In the case of dense matrices, we store each of these compact diagonals as a row of a matrix. For sparse matrices, all compact diagonals are kept in one long one-dimensional array, and we store some auxiliary arrays to represent the boundary between two diagonals. It follows that each compact diagonal is a vector of length \(n\). For example, the third compact diagonal (for \(n=4\)) is the vector \(A_{3}\) of length \(4\):  
\[A_{3}=\left( \begin{array}{c}\overline{A_{3}}\\ \underline{A_{1}}\end{array} \right)=\left( \begin{array}{c}a_{0,3}\\ a_{1,0}\\ a_{2,1}\\ a_{3,2}\end{array} \right)\]  
where \(\overline{A_{3}}\) is above the thick horizontal line and \(\underline{A_{1}}\) is below it. The _reverse_ of the \(k\)th compact diagonal is defined as  
\[\tilde{A_{k}}=\left( \begin{array}{c}\underline{A_{k}}\\ \overline{A_{n-k}}\end{array} \right)\]  
by swapping the position of the superdiagonal and subdiagonal pair. Figure 3 presents a visualization of a matrix of size \(n=4\) (Figure 2(a)), the diagonal storage suggested in [20] (Figure 2(b)), and the compact diagonal storage (Figure 2(c)) proposed in the current study. Figure 3: Visualizations of (**a**) an original matrix, (**b**) HM (i.e., diagonal) storage, and (**c**) CDM (i.e., compact diagonal) storage. Matrix transposition is an algorithmic building block for algorithms such as Fast Fourier Transform (FFT) and K-means clustering [34]. The MKL implementation of BLAS provides transposed matrix multiplication,  
\[C\gets C+A^{\top}B,C\gets C+AB^{\top},\]  
as well as symmetric rank-\(k\) (SYRK) and rank-\(2k\) (SYR2K) updates,  
\[C\gets AA^{\top}+C,C\gets AB^{\top}+BA^{\top}+C\]  
respectively. With traditional row-major (or column-major) storage, the naive in-place transposition incurs \(\Omega(n^{2})\) I/O operations. In a computer with multilevel hierarchical memory, this translates to \(\Omega(n^{2})\) cache misses, resulting in an unacceptably high penalty for performance. Both CDM and HM almost entirely avoid performance degradation due to transposed access to matrix elements. To see this, consider an arbitrary element \(a_{i,j}\) of matrix \(A\). Without loss of generality, assume that \(i<j\) and that \(k=(j-i)\). It follows that \(a_{i,j}\) is stored in compact diagonal \(k\) which has the form  
\[A_{k}=\left( \begin{array}{c}\overline{A_{k}}\\ \underline{A_{n-k}}\end{array} \right)\]  
and that \(a_{i,j}\) is an element of superdiagonal \(\overline{A_{k}}\). Now, consider the reverse \(\tilde{A_{k}}\) of the \(k\)th compact diagonal  
\[\tilde{A_{k}}=\left( \begin{array}{c}\underline{A_{k}}\\ \overline{A_{n-k}}\end{array}