Structured Semidefinite Programming for Recovering Structured Preconditioners Arun Jambulapati Christopher Musco Jerry Li Simons Institute Aaron Sidford Broad Institute of MIT and Harvard

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental preconditioning and linear system solving problems including: Diagonal preconditioning.