Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm

Explore a conference talk where Jason Altschuler from MIT presents groundbreaking research on matrix preconditioning algorithms at IPAM's Statistical and Numerical Methods for Non-commutative Optimal Transport Workshop. Discover how Osborne's algorithm, the default preconditioning procedure in Python, Julia, MATLAB, EISPACK, and LAPACK, has finally been proven to have near-linear runtime after decades of theoretical uncertainty. Learn about the connection between this classical algorithm and Sinkhorn's algorithm for matrix scaling used in optimal transport problems. The presentation details how this new runtime guarantee is optimal in input size, doesn't slow down downstream tasks like eigenvalue computation, and improves upon all other Osborne algorithm variants. Based on joint research with Xufeng Cai and Jelena Diakonikolas, this 55-minute talk bridges a longstanding gap between theoretical analysis and practical implementation in computational linear algebra.