Title: Monte-Carlo Algorithms for Matrices and Applications Location: Building 980, Room 95 (Sandia NM), Building 915, Room S107 (Sandia-CA) Brief Abstract: We are interested in developing and analyzing Monte Carlo algorithms for performing useful computations on large matrices, and applying them on (massive) datasets. Examples of such computations include matrix multiplication, the computation of the Singular Value Decomposition of a matrix, the computation of CUR type decompositions of matrices, testing the feasibility or infeasibility of linear programs, and solving least squares problems. 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. We also discuss various applications of these methods to the analysis of data sets. CSRI POC: Bruce Hendrickson, (505) 845-7599 |