[BANANA] LAPACK seminar on Dec. 10

[Ming Gu]

               Math 290, Section 25, CS 298, Section 6,
                          FALL 2008
         (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 at cs.berkeley.edu), 
M. Gu (mgu at math.berkeley.edu), and B. N. Parlett (parlett at math.berkeley.edu). 
The program will be a mixture of research talks and tutorials.
The tutorials will provide a partial sequel to Math 221.

This will be the last meeting of this semester. 

Date: Dec. 10, 2008 
Speaker: Christopher Sikorski, School of Computing, University of Utah
Title: CES Program at the University of Utah and Computation of Fixed 
       Points for Nonexpanding Functions
Abstract: This talk consists of two parts. We first review the CES program 
(Computational Engineering and Science Program, www.ces.utah.edu)  at the 
University of Utah and then present an overview of our research on optimal 
algorithms for approximating fixed points. 

   In 1979 Khachiyan introduced the exterior ellipsoid 
algorithm (EEA) as the first method for solving linear programming
problems in polynomial time. We show that this algorithm can also 
be applied for approximating fixed points of $d$-dimensional directionally 
nonexpanding functions with respect to the second norm. The
number of iterations of EEA is at most $2 d^{2} \ln(1/\epsilon)$ for 
computing $x$: $||x-f(x)||_{2} \leq \epsilon$. Several tests of a numerically 
stable implementation of EEA as well as comparisons with the Simple Iteration 
algorithm will be presented. In 1988 the Interior Ellipsoid Algorithm (IEA) 
was developed by Khachiyan, Tarasov and Erlikh. The IEA algorithm enjoys 
an almost minimal number of iterations $6 d \ln(1/\epsilon)$, however  
efficient and numerically stable implementations of IEA are not known. 
   
   For the infinity norm case the ellipsoid constructions are not valid. 
In this case we outline an optimal Bisection-Envelope ($d=2$) algorithm. 
We also developed recursive bisection algorithms for $d>2$. We present 
several numerical tests and formulate some open problems.