We are interested in developing and analyzing fast Monte Carlo algorithms for
performing useful computations on large matrices. Examples of such
computations include matrix multiplication, the computation of the Singular
Value Decomposition of a matrix, the computation of compressed approximate
decompositions of a matrix, and testing the feasibility or infeasibility of
a linear program. We present a Pass-Efficient model of data streaming
computation in which our algorithms may naturally be formulated and present
algorithms that are efficient within this model for each of the four types of
matrix operations mentioned previously. We also discuss applications of these
methods to the analysis of massive data sets and outline an improved algorithm
for the Max-Cut problem that uses these methods. This is joint work with
Petros Drineas and Ravi Kannan.