Speaker
Raphael Meyer
(UC Berkeley)
Description
Solving linear systems Ax=b is a fundamental pillar of NLA. For over 60 years, iterative methods that access A only through matrix-vector products have been the standard approach for solving large linear systems. While lower bounds exist for many special cases, prior work has not shown that methods like GMRES and MINRES achieve an asymptotically optimal matrix-vector complexity for approximately solving Ax=b. In this talk, we prove that MINRES (and CG on the normal equations) achieves an optimal complexity (up to a factor of 4) over all randomized matrix-vector methods, and GMRES achieves the best possible over all "transpose-free" methods.
Authors
Ethan Epperly
(UC Berkeley)
Prof.
Michał Dereziński
(University of Michigan)
Raphael Meyer
(UC Berkeley)