Computer Science NASC Seminar
Random Sampling Preconditioners
Haim Avron, IBM
November 18, 2011
10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 100121110
(Directions)
Fall 2011 NASC Seminars Calendar
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 stateoftheart 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 leastsquare solver for dense highly overdetermined systems that achieves residuals similar to those of direct factorization based stateoftheart solvers (LAPACK), outperforms LAPACK by large factors, and scales significantly better than any QRbased solver. For sparse matrices, I will relate random sampling preconditioners to nearlylinear 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.
