Govind Menon (Brown)

Title: How long does it take to compute the eigenvalues of a random symmetric matrix?

Abstract: The QR algorithm is an iterative method for the numerical computation of eigenvalues that is based on the QR factorization of a matrix (i.e. the Gram-Schmidt procedure).  The algorithm goes as follows. In the $k$-th step, we first factor $M_k=Q_kR_k$. The factors are then "flipped" to form the next matrix $M_{k+1}=R_kQ_k$. For generic initial conditions, the sequence $M_k$ converges to a diagonal matrix exponentially fast.

This algorithm is part of a larger family of eigenvalue and sorting algorithms each of which is obtained as a time-1 map of a completely integrable Hamiltonian flow. I will describe this algorithmic framework, some background on the need to quantify the "probability that a numerical algorithm is good on average", some random matrix theory, and intriguing empiricial evidence for "universality". I won't presume much background, and I hope the talk will be broadly accessible.

This is joint work with Percy Deift and Christian Pfrang.