Tata Institute of Fundamental Research
Analysis of a Classical Matrix Preconditioning Algorithm
Seminar
Speaker:
Leonard J. Schulman (California Institute of Technology Department of Computer Science 1200 E California Blvd, MC 305-16 Pasadena, CA 91125 United States of America)
Organiser:
Piyush Srivastava
Date:
Monday, 4 Jun 2018, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
There are several prominent computational problems for which simple iterative methods are widely preferred in practice despite an absence of runtime or performance analysis (or "worse", actual evidence that more sophisticated methods have superior performance according to the usual criteria). These situations raise interesting challenges for the analysis of algorithms.
We are concerned in this work with one such simple method: a classical iterative algorithm for balancing matrices via scaling transformations. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner for eigenvalue computations 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: a natural L_infinity -norm variant of the algorithm converges, on n by n matrices, in O(n^3 log(n)) elementary scaling transformations. This is tight up to the log n factor. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed (joint work with Alistair Sinclair).
| Speaker: | Leonard J. Schulman (California Institute of Technology Department of Computer Science 1200 E California Blvd, MC 305-16 Pasadena, CA 91125 United States of America) |
| Organiser: | Piyush Srivastava |
| Date: | Monday, 4 Jun 2018, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
There are several prominent computational problems for which simple iterative methods are widely preferred in practice despite an absence of runtime or performance analysis (or "worse", actual evidence that more sophisticated methods have superior performance according to the usual criteria). These situations raise interesting challenges for the analysis of algorithms.
We are concerned in this work with one such simple method: a classical iterative algorithm for balancing matrices via scaling transformations. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner for eigenvalue computations 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: a natural L_infinity -norm variant of the algorithm converges, on n by n matrices, in O(n^3 log(n)) elementary scaling transformations. This is tight up to the log n factor. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed (joint work with Alistair Sinclair).
We are concerned in this work with one such simple method: a classical iterative algorithm for balancing matrices via scaling transformations. This algorithm, which goes back to Osborne and Parlett & Reinsch in the 1960s, is implemented as a standard preconditioner for eigenvalue computations 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: a natural L_infinity -norm variant of the algorithm converges, on n by n matrices, in O(n^3 log(n)) elementary scaling transformations. This is tight up to the log n factor. We also prove a conjecture of Chen that characterizes those matrices for which the limit of the balancing process is independent of the order in which balancing operations are performed (joint work with Alistair Sinclair).