# Compressed matrix multiplication

Compressed matrix multiplication Compressed Matrix Multiplication RASMUS PAGH, IT University of Copenhagen We present a simple algorithm that approximates the product of n-by-n real matrices A and B. Let ||AB|| F denote the Frobenius norm of AB, and b be a parameter determining the time/accuracy trade-off. Given 2-wise independent hash functions h1 , h2 : [n] [b], and s1 , s2 : [n] {-1, +1} the algorithm works by first "compressing" the matrix product into the polynomial n n p(x) = k=1 i=1 Aiks1 (i) x h1 (i) n Bkj s2 ( j) x h2 ( j) . j=1 Using the fast Fourier transform to compute polynomial multiplication, we can compute c0 , . . . , cb-1 such ~ that i ci xi = ( p(x) mod x b ) + ( p(x) div x b ) in time O(n2 + nb). An unbiased estimator of (AB)i j with variance at most ||AB||2 /b can then be computed as: F Ci j = s1 (i) s2 ( j) c(h1 (i)+h2 ( j)) mod b . ~ Our approach also leads to an algorithm for computing AB exactly, with high probability, in time O(N + nb) in the case where A http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

# Compressed matrix multiplication

, Volume 5 (3) – Aug 1, 2013
17 pages      /lp/association-for-computing-machinery/compressed-matrix-multiplication-lnJBeAPkcH
Publisher
Association for Computing Machinery
ISSN
1942-3454
DOI
10.1145/2493252.2493254
Publisher site
See Article on Publisher Site

### Abstract

Compressed Matrix Multiplication RASMUS PAGH, IT University of Copenhagen We present a simple algorithm that approximates the product of n-by-n real matrices A and B. Let ||AB|| F denote the Frobenius norm of AB, and b be a parameter determining the time/accuracy trade-off. Given 2-wise independent hash functions h1 , h2 : [n] [b], and s1 , s2 : [n] {-1, +1} the algorithm works by first "compressing" the matrix product into the polynomial n n p(x) = k=1 i=1 Aiks1 (i) x h1 (i) n Bkj s2 ( j) x h2 ( j) . j=1 Using the fast Fourier transform to compute polynomial multiplication, we can compute c0 , . . . , cb-1 such ~ that i ci xi = ( p(x) mod x b ) + ( p(x) div x b ) in time O(n2 + nb). An unbiased estimator of (AB)i j with variance at most ||AB||2 /b can then be computed as: F Ci j = s1 (i) s2 ( j) c(h1 (i)+h2 ( j)) mod b . ~ Our approach also leads to an algorithm for computing AB exactly, with high probability, in time O(N + nb) in the case where A

### Journal

ACM Transactions on Computation Theory (TOCT)Association for Computing Machinery

Published: Aug 1, 2013