Accurate randomized algorithms of numerical analysis

Wednesday, August 4, 2010 - 11:00am - 12:00pm
Keller 3-180
Vladimir Rokhlin (Yale University)
Randomized algorithms are ubiquitous in computer science and
engineering. Many problems that are intractable when viewed
deterministically can be effectively solved with probabilistic techniques.
Perhaps the most
important aspect of most randomized procedures in current use
is the fact
that they produce the correct result with (practically
speaking) 100% reliability, and with (essentially) machine precision.

Historically, randomized techniques have been less popular in
analysis. Most of them trade accuracy for speed, and in many
environments one does not want to add yet another source of
inaccuracy to
the calculation that is already sufficiently inaccurate. One
could say that in
numerical analysis probabilistic methods are an approach of
last resort.

I will discuss several probabilistic algorithms of numerical
linear algebra
that are never less accurate than their deterministic
counterparts, and in fact
tend to produce better accuracy. In many situations, the new
schemes have
lower CPU time requirements than existing methods, both
asymptotically and
in terms of actual timings. I will illustrate the approach with
several numerical
examples, and discuss possible extensions.