Cache Oblivious Sparse Matrix Multiplication

Matteo Dusefante, Riko Jacob

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review


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.
TitelLatin American Symposium on Theoretical Informatics : LATIN 2018: Theoretical Informatics
Publikationsdato13 mar. 2018
ISBN (Trykt)978-3-319-77403-9
ISBN (Elektronisk)978-3-319-77404-6
StatusUdgivet - 13 mar. 2018
NavnLecture Notes in Computer Science


Dyk ned i forskningsemnerne om 'Cache Oblivious Sparse Matrix Multiplication'. Sammen danner de et unikt fingeraftryk.