Cache Oblivious Sparse Matrix Multiplication

We study the problem of sparse matrix multiplication in the Random Access Machine and in the Ideal Cache-Oblivious model. We present a simple algorithm that exploits randomization to compute the product of two sparse matrices with elements over an arbitrary field. Let \(A \in \mathbb {F}^{n \times n}\) and \(C \in \mathbb {F}^{n \times n}\) be matrices with h nonzero entries in total from a field \(\mathbb {F}\). In the RAM model, we are able to compute all the k nonzero entries of the product matrix \(AC \in \mathbb {F}^{n \times n}\) using \(\tilde{\mathcal {O}}(h + kn)\) time and \(\mathcal {O}(h)\) space, where the notation \(\tilde{\mathcal {O}}(\cdot )\) suppresses logarithmic factors. In the External Memory model, we are able to compute cache obliviously all the k nonzero entries of the product matrix \(AC \in \mathbb {F}^{n \times n}\) using \(\tilde{\mathcal {O}}(h/B + kn/B)\) I/Os and \(\mathcal {O}(h)\) space. In the Parallel External Memory model, we are able to compute all the k nonzero entries of the product matrix \(AC \in \mathbb {F}^{n \times n}\) using \(\tilde{\mathcal {O}}(h/PB + kn/PB)\) time and \(\mathcal {O}(h)\) space, which makes the analysis in the External Memory model a special case of Parallel External Memory for \(P=1\). The guarantees are given in terms of the size of the field and by bounding the size of \(\mathbb {F}\) as \({|}\mathbb {F}{|} > kn \log (n^2/k)\) we guarantee an error probability of at most \(1{\text{/ }}n\) for computing the matrix product.