Computational Mathematics and Scientific Computing Seminar
Random Sampling Preconditioners
Speaker: Haim Avron, IBM
Location: Warren Weaver Hall 1302
Date: Nov. 18, 2011, 10 a.m.
Synopsis:
Randomization is arguably the most exciting and innovative idea to have hit linear algebra in a long time. Several such algorithms have been proposed and explored in the past decade. Some forms of randomization have been used for decades in linear algebra. For example, the starting vectors in Lanczos algorithms are always random. But recent research led to new uses of randomization: random mixing and random sampling, which can be combined to form random projections. These ideas have been explored theoretically and have found use in some specialized applications (e.g., data mining), but they have had little influence so far on mainstream numerical linear algebra. Numerical linear algebra is an highly practical field. New techniques need to show practical applications in order to make significant impact Therefore, the core question that needs answering is: can randomized algorithms beat state-of-the-art numerical linear algebra libraries in practice?
For reasons that I will explain in the talk, the answer is far from trivial. Nevertheless, I will show that at least for one important problem in numerical linear algebra, the answer is yes. More specifically, I will show how the use preconditioners based on random sampling of rows can accelerate the solution of certain linear systems. I will argue that the fusion of randomization with preconditioning is what enables fast and reliable randomized algorithms for this problem.
The talk will discuss both dense and sparse matrices. For dense matrices, I will describe Blendenpik, a least-square solver for dense highly overdetermined systems that achieves residuals similar to those of direct factorization based state-of-the-art solvers (LAPACK), outperforms LAPACK by large factors, and scales significantly better than any QR-based solver. For sparse matrices, I will relate random sampling preconditioners to nearly-linear time SDD solvers, and how the sampling process can be generalized to finite element matrices. The last topic is still work in progress, so I will not present a concrete solver.