News

Colloquia

Random Sampling Preconditioners

Speaker: Haim Avron
IBM Research

April 05, 2012 - 4:00 p.m. to 5:00 p.m.
Location: Troy 2012
Hosted By: Dr. Petros Drineas (x8265)

Abstract:

Randomization is arguably the most exciting and innovative idea to have hit linear algebra in a long time. Some forms of randomization have been used for decades in linear algebra. For example, the starting vectors in Lanczos algorithms were always random. But recent research led to new uses of randomization: random mixing and random sampling, which can be combined to form random projections. Recent research has shown that these powerful techniques offer great promise in the on-going quest to further accelerate matrix computations. Indeed, several algorithms based on these techniques have been proposed and explored in the past decade.

However, for reasons that I will explain in the talk, even with such powerful algorithms it is still far from trivial to beat state-of-the-art numerical linear algebra libraries in practice. Nevertheless, I will show that at least for one important problem in numerical linear algebra, significant acceleration can be achieved. More specifically, I will show how the use of preconditioners based on random sampling 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 discuss 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.

Short Bio:

Haim Avron received his B.Sc. in Computer Science and Mathematics in 1999, and his M.Sc. in Computer Science in 2005, both from Tel Aviv University. He received his Ph.D. in computer science from The School of Computer Science at Tel Aviv University in 2010. From 2010 he is a post-doctoral researcher in the Mathematical Sciences Department at IBM T.J. Watson Research Center. Haim's research focuses on combinatorial scientific computing, numerical linear algebra and parallel computing, and the application of linear algebra in computer graphics and machine learning

Last updated: March 16, 2012