Combinatorics Seminar

We study a classical iterative algorithm for the problem of balancing matrices in the L_\infty norm via a scaling transformation. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner in many numerical linear algebra packages. Surprisingly, despite its widespread use over several decades, no bounds were known on its rate of convergence. We prove the first such bound and indeed show that the algorithm converges in time O(n^3 log n) on n by n matrices, which is tight up to the log factor.

Joint work with Alistair Sinclair