APPLIED MATH SEMINAR

Speaker: Prof. Vladimir Rokhlin, Yale University

Title: Accurate Randomized Algorithms of Numerical Analysis

When/where: Tuesday, November 10th, 4:15 PM, AKW 200

Abstract:

   Randomized algorithms are ubiqutous in computer science and computer
engineering. Many problems that are intractable when viewed deterministi-
cally 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% reliabil-
ity, and with (essentially) machine precision.
   Historically, randomized techniques have been less popular in numerical
analysis. Most of them trade accuracy for speed, and in many numerical
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.