Pseudospectral Shattering and Diagonalization in Nearly Matrix Multiplication Time
Event details
| Date | 01.04.2021 |
| Hour | 16:15 › 17:15 |
| Speaker | Professor Nikhil Srivastava (UC Berkeley) |
| Location | Online |
| Category | Conferences - Seminars |
We give an algorithm which diagonalizes an n x n complex matrix up to backward error delta in O(n^{\omega+o(1)}polylog(n/delta))
bit operations in finite arithmetic with O(polylog(n/delta)) bits of precision, substantially improving the previously known running time of O(n^10/delta^2). The two key ingredients are (1) A random matrix theory result showing that every matrix is close to one with well-conditioned eigenvalues and eigenvectors, resolving a conjecture of E.B. Davies. (2) A rigorous analysis of Roberts' Newton iteration method for computing the matrix sign function in finite arithmetic, itself an open problem in numerical analysis since the 80's.
Joint work with J. Banks, J. Garza-Vargas, A. Kulkarni, and S. Mukherjee.
Practical information
- General public
- Free
Organizer
- Prof. Daniel Kressner
Prof. Nicolas Boumal
Contact
- Samantha Bettschen