Cache Oblivious Sparse Matrix Multiplication

Matteo Dusefante, Riko Jacob

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationLatin American Symposium on Theoretical Informatics : LATIN 2018: Theoretical Informatics
PublisherSpringer
Publication date13 Mar 2018
Pages437-447
ISBN (Print)978-3-319-77403-9
ISBN (Electronic)978-3-319-77404-6
DOIs
Publication statusPublished - 13 Mar 2018
SeriesLecture Notes in Computer Science
Volume10807
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Cache Oblivious Sparse Matrix Multiplication'. Together they form a unique fingerprint.

Cite this