Compressed matrix multiplication

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 h 1 , h 2 : [ n ]→ [ b ], and s 1 , s 2 : [ n ]→ {−1,+1} the algorithm works by first “compressing” the matrix product into the polynomial p ( x ) = ∑ k =1 n (∑ i =1 n A ik s 1 ( i ) x h 1 ( i ) ) (∑ j =1 n B kj s 2 ( j ) x h 2 ( j ) ). Using the fast Fourier transform to compute polynomial multiplication, we can compute c 0 ,…, c b −1 such that ∑ i c i x i = ( p ( x ) mod x b ) + ( p ( x ) div x b ) in time Õ( n 2 + nb ). An unbiased estimator of ( AB ) ij with variance at most ‖ AB ‖ F 2 / b can then be computed as: C ij = s 1 ( i ) s 2 ( j ) c ( h 1 ( i )+ h 2 ( j )) mod b . Our approach also leads to an algorithm for computing AB exactly, with high probability, in time Õ( N + nb ) in the case where A and B have at most N nonzero entries, and AB has at most b nonzero entries.