BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-11430@webedit.cs.cornell.edu
DTSTAMP:20201207T212000Z
DTSTART:20201207T212000Z
DTEND:20201207T222000Z
SUMMARY:Approximate Diagonalization in Nearly Matrix Multiplication Time
DESCRIPTION:Jess Banks, University of California, Berkeley. Approximate Diagonalization in Nearly Matrix Multiplication Time (via Zoom)Abstract: In this talk I will show that any matrix can be approximately diagonalized in nearly matrix multiplication time. In particular, given a square, complex, n x n matrix A with operator norm at most one, and an error parameter d>0, one can compute with high probability an invertible matrix V and diagonal D such that ||A - VDV^{-1}|| < d, in O(MM(n) polylog(n/d)) arithmetic operations, using O(polylog(n/d)log(n)) bits of precision. Here MM(n) is the number of arithmetic operations required for numerically stable multiplication of two n x n matrices.The algorithm we analyze is a variant of the well-studied spectral bisection algorithm in numerical linear algebra, with a crucial Gaussian perturbation preprocessing step. This is the first algorithm that has been shown to achieve nearly matrix multiplication time for diagonalization in finite precision arithmetic, and...https://webedit.cs.cornell.edu/content/approximate-diagonalization-nearly-matrix-multiplication-time
LOCATION:Streaming via Zoom
END:VEVENT
END:VCALENDAR