[Crib-list] MIT Numerical Linear Algebra Seminar -- Spk. Jorge Garza-Vargas (Caltech) -- Friday, Oct. 20th @ 1:00 - 2:00 PM in Math, Room 2-449

[Shirley Entzminger]

                  MIT Numerical Linear Algebra Seminar


DATE:     Friday, October 20, 2023

TIME:     1:00 PM

LOCATION: Building 2, Room 449

=============================================

SPEAKER:   Jorge Garza-Vargas  (Caltech)

TITLE:     Rigorous Guarantees for Randomized Diagonalization Algorithms

ABSTRACT:

The task of designing efficient and reliable algorithms for computing 
the eigenvalues
and eigenvectors of a matrix (i.e. solving the eigenvalue problem) is of
unquestionable relevance in science and engineering. However, despite 
substantial
progress on several of its practical facets, there are fundamental 
theoretical questions
about the eigenvalue problem that remain poorly understood.

In this talk, I will present results that provide rigorous guarantees 
for two of the most
commonly used diagonalization algorithms. Specifically, we show that the 
eigenvalue problem
can be solved (via the spectral bisection algorithm) in nearly 
matrix-multiplication time
and that a certain randomized shifting strategy for the QR algorithm is 
globally
convergent (implying an O(n3) worst-case running time for this 
algorithm).

A key step in our analysis requires understanding the spectral stability 
properties of
arbitrary deterministic matrices that have been randomly perturbed by a 
very small
"noise matrix". With this, in the spirit of smoothed analysis, we can 
show rigorous
guarantees for the aforementioned algorithms when run on tiny 
perturbations of
arbitrary (possibly non-normal) inputs.

This is joint work with Jess Banks, Archit Kulkarni, and Nikhil 
Srivastava.

===============================

Shirley Entzminger
Administrative Assistant II
MIT - Math Dept.
77 Massachusetts Avenue
Bldg. 2, RM 350A
Cambridge, MA   02136
PHONE:  617-253-4994
EMAIL:  daisymae at math.mit.edu

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Jorge_Garza-Vargas_NLA_seminar_flyer.pdf
Type: application/pdf
Size: 95793 bytes
Desc: not available
URL: <http://mailman.mit.edu/pipermail/crib-list/attachments/20231019/b202d9a1/attachment.pdf>