@inproceedings{89603ca35dd044ad8f4a3481e23b5db0,

title = "Cache Oblivious Sparse Matrix Multiplication",

abstract = "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.",

author = "Matteo Dusefante and Riko Jacob",

year = "2018",

month = mar,

day = "13",

doi = "10.1007/978-3-319-77404-6_32",

language = "English",

isbn = "978-3-319-77403-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "437--447",

booktitle = "Latin American Symposium on Theoretical Informatics",

address = "Germany",

}