lapackers

[Ming Gu <mgu@math.berkeley.edu>]

               Math 290, Section 29, CS 298, Section 6,
                          Spring 2011
         (Matrix Computations and Scientific Computing)

We meet WEDNESDAYS 11:10 - noon in Room 380 Soda Hall,
Berkeley campus.  The coordinators are Profs. J. Demmel
(demmel@cs.berkeley.edu) and M. Gu (mgu@math.berkeley.edu).
The program will be a mixture of research talks and
tutorials.  The tutorials will provide a partial sequel to
Math 221.

For the schedule and other details about the seminar, please see
math.berkeley.edu/~mgu/LAPACKSeminar.htm

We kick off our semester with a joint Scientific
Computing/Applied Math Seminar featuring Prof. Rokhlin of
Yale University. Note that for Jan. 26 only, we will meet
from 4:00-5:00PM in 939 Evans Hall.

Date: Jan. 26
Speaker: Vladimir Rokhlin, Yale University
Title: Accurate randomized algorithms of numerical analysis
Abstract: See attached.

Date: Feb. 2
Speaker: Dr. David Gleich
Title: Fast Katz and Commuters - Quadrature Rules and Sparse
Linear Solvers for Link Prediction Heuristics


Title: Accurate Randomized Algorithms of Numerical Analysis 
   Vladimir Rokhlin, Yale University 
Abstact: Randomized algorithms are ubiqutous in computer science and computer 
engineering. Many problems that are intractable when viewed deterministic
ally canbeeffectively solved withprobabilistictechniques. Perhapsthemost 
important aspect of most randomized procedures in current use is the fact 
thattheyproducethe correct result with(practically speaking) 100% reliabili
ty, and with(essentially) machineprecision. 

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 
lowerCPU time requirements than existing methods,both asymptotically and 
intermsofactual timings. Iwillillustratetheapproach with several numerical 
examples, and discuss possible extensions.