Abstract
At this point in time, we understand fairly well how randomized projections can be used to very efficiently compute a low rank approximation to a given matrix. We have seen that randomized methods are often substantially faster than traditional deterministic methods, and that they enable the processing of matrices that are simply too large to be handled using traditional deterministic methods. In this talk, we will describe how randomization can also be used to accelerate the computation of a *full* factorization (e.g. a column pivoted QR decomposition) of a matrix. These methods achieve high speed primarily by reducing the amount of communication that is required, as compared to existing methods. This makes them particularly competitive in communication constrained environments such as data stored out-of-core, GPU computing, distributed memory machines, etc. While the methods presented were developed primarily for the purpose of computing a full factorization, they are also very convenient to use for computing partial factorizations in situations where we have no prior information about the numerical rank of the input matrix.