TY - GEN

T1 - Cache Oblivious Sparse Matrix Multiplication

AU - Dusefante, Matteo

AU - Jacob, Riko

PY - 2018/3/13

Y1 - 2018/3/13

N2 - 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.

AB - 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.

KW - Sparse matrix multiplication

KW - Random Access Machine (RAM)

KW - Ideal Cache-Oblivious model

KW - External Memory model

KW - Parallel External Memory model

KW - Sparse matrix multiplication

KW - Random Access Machine (RAM)

KW - Ideal Cache-Oblivious model

KW - External Memory model

KW - Parallel External Memory model

U2 - 10.1007/978-3-319-77404-6_32

DO - 10.1007/978-3-319-77404-6_32

M3 - Article in proceedings

SN - 978-3-319-77403-9

T3 - Lecture Notes in Computer Science

SP - 437

EP - 447

BT - Latin American Symposium on Theoretical Informatics

PB - Springer

ER -