Smaller steps for faster algorithms : a new approach to solving linear systems
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/84861 |
| _version_ | 1826194164434337792 |
|---|---|
| author | Sidford, Aaron Daniel |
| author2 | Jonathan Kelner. |
| author_facet | Jonathan Kelner. Sidford, Aaron Daniel |
| author_sort | Sidford, Aaron Daniel |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T09:51:55Z |
| format | Thesis |
| id | mit-1721.1/84861 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:51:55Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/848612019-04-10T09:03:54Z Smaller steps for faster algorithms : a new approach to solving linear systems Sidford, Aaron Daniel Jonathan Kelner. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (pages 81-85). 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]. by Aaron Daniel Sidford. S.M. 2014-02-10T16:55:39Z 2014-02-10T16:55:39Z 2013 Thesis http://hdl.handle.net/1721.1/84861 868322914 eng 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. http://dspace.mit.edu/handle/1721.1/7582 85 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Sidford, Aaron Daniel Smaller steps for faster algorithms : a new approach to solving linear systems |
| title | Smaller steps for faster algorithms : a new approach to solving linear systems |
| title_full | Smaller steps for faster algorithms : a new approach to solving linear systems |
| title_fullStr | Smaller steps for faster algorithms : a new approach to solving linear systems |
| title_full_unstemmed | Smaller steps for faster algorithms : a new approach to solving linear systems |
| title_short | Smaller steps for faster algorithms : a new approach to solving linear systems |
| title_sort | smaller steps for faster algorithms a new approach to solving linear systems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/84861 |
| work_keys_str_mv | AT sidfordaarondaniel smallerstepsforfasteralgorithmsanewapproachtosolvinglinearsystems |