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.