Journal
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE
Volume -, Issue -, Pages 230-249Publisher
IEEE
DOI: 10.1109/FOCS.2015.23
Keywords
Inverse Maintenance Problem; Linear Systems; Linear Programming
Categories
Funding
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1111109] Funding Source: National Science Foundation
Ask authors/readers for more resources
In this paper, we consider the following inverse maintenance problem: given A is an element of R-nxd and a number of rounds r, at round k, we receive a n x n diagonal matrix D-(k) and we wish to maintain an efficient linear system solver for A(T)D((k)) A under the assumption D-(k) does not change too rapidly. This inverse maintenance problem is the computational bottleneck in solving multiple optimization problems. We show how to solve this problem with (O) over tilde (nnz(A) + d(omega)) preprocessing time and amortized (O) over tilde (nnz(A) + d(2)) time per round, improving upon previous running times. Consequently, we obtain the fastest known running times for solving multiple problems including, linear programming and computing a rounding of a polytope. In particular given a feasible point in a linear program with n variables, d constraints, and constraint matrix A is an element of R-dxn, we show how to solve the linear program in time (O) over tilde((nnz(A)+d(2))root d log(epsilon(-1))). We achieve our results through a novel combination of classic numerical techniques of low rank update, preconditioning, and fast matrix multiplication as well as recent work on subspace embeddings and spectral sparsification that we hope will be of independent interest.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available