Skip to main content

Vladimir Rokhlin: Accurate Randomized Algorithms of Numerical Analysis

Vladimir Rokhlin, Yale university

Time: Wed 2012-05-09 15.00 - 16.00

Location: Oskar Klein auditorium, Alba Nova


14:00-14:45: Precolloquium for PhD and master students (room FB52)

15:00-16:00: Colloquium lecture by Vladimir Rokhlin.

16:00-17:00: Coffee and SMC social get-together.

Abstract (colloquium)

Title: Accurate Randomized Algorithms of Numerical Analysis

Randomized algorithms are ubiquitous in computer science and computer 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 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.

Abstract (precolloquium)

Title: The use of inexact and randomized algorithms – all is fair in the quest for speed

Classical algorithms for solving problems on a computer are often exact and deterministic, that is, they compute the solution as accurately as the machine precision and the input data allow and behave in a predictable fashion. Examples include QR factorization and standard schemes for computing gravitational N-body interactions. These algorithms are easy to understand and the fact that they are exact and predictable is very reassuring and makes life easier for the programmer. There is, however, a lot of speed to be gained by instead using inexact and/or randomized algorithms. We will look at a few examples of such algorithms that professor Vladimir Rokhlin helped pioneer, with some emphasis on the fast multipole method for particle interactions.

Title Date
Hendrik Lenstra: Escher and the Droste effect Dec 12, 2012
Bo Berndtsson: Complex Brunn-Minkowski theory Nov 21, 2012
Martin Aigner: From Irrational Numbers to Perfect Matchings: 100 Years of Markov’s Uniqueness Problem Oct 10, 2012
Vladimir Rokhlin: Accurate Randomized Algorithms of Numerical Analysis May 19, 2012
Martin R. Bridson: Discrete groups: A story of geometry, complexity, and imposters Apr 11, 2012
Mats Gyllenberg: Rock, scissors, paper — what a children's game can tell us about evolution Mar 14, 2012
Persi Diaconis: Who Needs Positivity? Feb 10, 2012