Randomized Matrix Multiplication

Abstract. We examine the BASICMATRIXMULTIPLICATION (BMM) algo- rithm introduced by Drineas, Kannan, and Mahoney and attempt to reduce the error of their algorithm. The algorithm randomly samples columns and rows from the input matrices A and B, respectively—these sampled columns and rows are scaled such that the expected value of their product is equal to the true product AB. For sufficiently large matrices, BMM is computationally less expensive than traditional deterministic matrix algorithms; however, the algorithm is prohibitively inexact for most input matrices. We modify BMM by pre-multiplying the input matrices with Hadamard matrices and random diagonal matrices; we hope this pre- processing step will smooth matrix data and reduce algorithm error. We present both our methods and the experimental results of our modified algorithm.