Cache Oblivious Sparse Matrix Multiplication

We study the problem of sparse matrix multiplication in theRandom Access Machine and in the Ideal Cache-Oblivious model. Wepresent a simple algorithm that exploits randomization to compute theproduct of two sparse matrices with elements over an arbitrary field. LetA ∈ Fn×n and C ∈ Fn×n be matrices with h nonzero entries in totalfrom a field F. In the RAM model, we are able to compute all the knonzero entries of the product matrix AC ∈ Fn×n using O˜(h + kn)time and O(h) space, where the notation O˜(·) suppresses logarithmicfactors. In the External Memory model, we are able to compute cacheobliviously all the k nonzero entries of the product matrix AC ∈ Fn×nusing O˜(h/B + kn/B) I/Os and O(h) space. In the Parallel ExternalMemory model, we are able to compute all the k nonzero entries ofthe product matrix AC ∈ Fn×n using O˜(h/PB + kn/PB) time andO(h) space, which makes the analysis in the External Memory model aspecial case of Parallel External Memory for P = 1. The guarantees aregiven in terms of the size of the field and by bounding the size of F as|F| > knlog(n2/k) we guarantee an error probability of at most 1/n forcomputing the matrix product.