Technion Computer Science Colloquium Time+Place : Monday 06/02/2012 14:30 room 337-8 Taub Bld. Speaker : Haim Avron SPECIAL GUEST TALK-NOTE UNUSUAL DAY Affiliation: Mathematical Sciences Dept., IBM T.J. Watson Research Center Host : Irad Yavneh Title : Random Sampling Preconditioners Abstract : 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 a 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 of 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 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. ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>