Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication

Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These algorithms make more efficient use of computational resources, such as the computation time, random access memory (RAM), and the number of passes over the data, than do previously known algorithms for these problems. In this paper, we devise two algorithms for the matrix multiplication problem. Suppose A and B (which are m × n and n × p, respectively) are the two input matrices. In our main algorithm, we perform c independent trials, where in each trial we randomly sample an element of {1, 2,..., n} with an appropriate probability distribution P on {1, 2,..., n}. We form an m × c matrix C consisting of the sampled columns of A, each scaled appropriately, and we form a c × n matrix R using the corresponding rows of B, again scaled appropriately. The choice of P and the column and row scaling are crucial features of the algorithm. When these are chosen judiciously, we show that CR is a good approximation to AB. More precisely, we show that �AB − CR�F = O(�A�F �B�F / √ c), where �·�F denotes the Frobenius norm, i.e., �A�2