Smaller steps for faster algorithms : a new approach to solving linear systems

In this thesis we study iterative algorithms with simple sublinear time update steps, and we show how a mix of of data structures, randomization, and results from numerical analysis allow us to achieve faster algorithms for solving linear systems in a variety of different regimes. First we present a simple combinatorial algorithm for solving symmetric diagonally dominant (SDD) systems of equations that improves upon the best previously known running time for solving such system in the standard unit-cost RAM model. Then we provide a general method for convex optimization that improves this simple algorithm's running time as special case. Our results include the following: -- We achieve the best known running time of ... for solving Symmetric Diagonally Dominant (SDD) system of equations in the standard unit-cost RAM model. -- We obtain a faster asymptotic running time than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. -- We achieve faster asymptotic convergence rates than the best known for Kaczmarz methods for solving overdetermined systems of equations, by accelerating an algorithm of Strohmer and Vershynin [55]. Beyond the independent interest of these solvers, we believe they highlight the versatility of the approach of this thesis and we hope that they will open the door for further algorithmic improvements in the future. This work was done in collaboration with Jonathan Kelner, Yin Tat Lee, Lorenzo Orecchia, and Zeyuan Zhu, and is based on the content of [30] and [35].

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Sidford, Aaron Daniel

Advisor dc:contributor.advisor

• Jonathan Kelner.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/84861

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/84861