Fast Monte-Carlo algorithms for approximate matrix multiplication

Given an m x n matrix A and an n x p matrix B, we present 2 simple and intuitive algorithms to compute an approximation P to the pr oductA·B, with provable bounds for the norm of the err or matrix "P- A·B. Both algorithms run in O(mp+mn+np) time. In both algorithms, we randomly pick s = O(1) columns of A to form an m x s matrix S and the corresponding rows of B to form an s x p matrix R. After scaling the columns of S and the rows of R, we multiply them together to obtain our approximation P. The choice of the probability distribution we use for picking the columns of A and the scaling are the crucial features which enable us to give fairly elementary proofs of the error bounds. Our first algorithm can be implemented without storing the matrices A and B in Random Access Memory, provided we can make two passes through the matrices (stored in external memory). The second algorithm has a smaller bound on the 2-norm of the error matrix, but requires storage of A and B in RAM. We also present a fast algorithm that "describes" P as a sum of rank one matrices if B = A T .