
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
ongoing 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 stateoftheart 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 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 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
postdoctoral 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

