[theory students] Theory seminar this Thursday (April 17) *different time/place* 2:30-3:30pm CS 4331

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Hi everyone, 

This Thursday (April 17) we will have a seminar but at a different place and time (CS 4331, 2:30-3:30 pm) with our very own Jelena Diakonikolas.

Title: Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm

Abstract: In 1960, Osborne proposed a simple iterative algorithm for matrix balancing with outstanding numerical performance. Today, it is the default preconditioning procedure before eigenvalue computation and other linear algebra subroutines in mainstream software packages such as Python, Julia, MATLAB, EISPACK, LAPACK, and more. Despite its widespread usage, Osborne's algorithm has long resisted theoretical guarantees for its runtime: the first polynomial-time guarantees were obtained only in the past decade, and recent near-linear runtimes remain confined to variants of Osborne's algorithm with important differences that make them simpler to analyze but empirically slower. I will present results that address this longstanding gap between theory and practice by proving that Osborne's original algorithm -- the de facto preconditioner in practice -- in fact has a near-linear runtime. This runtime guarantee (1) is optimal in the input size up to at most a single logarithm, (2) is the first runtime for Osborne's algorithm that does not dominate the runtime of downstream tasks like eigenvalue computation, and (3) improves upon the theoretical runtimes for all other variants of Osborne's algorithm. The talk is based on a recent preprint https://arxiv.org/abs/2503.16312. 

See you then!

Sandeep