Fast and Efficient Algorithms for Linear Programming and for the Linear Least Squares Problem.

摘要

We present a new parallel algorithm for computing a least-squares solution to a sparse overdetermined system of linear equations Ax=b such that mXn matrix A is sparse and the graph, G = (V,E), of the matrix H. Our algorithm uses O(log(m+n) log squared s(m+n)) steps and < or = s cubed (m+n) processors; it relies on our recent parallel algorithm for solving sparse linear systems. The objective of this paper is to reexamine the time-complexity of the l.l.s.p. and to indicate the possibility of speeding up its solution using the parallel algorithms of PR in brackets. As a major consequence, (which may become decisive for determining the best algorithm for the linear programming problem (l.p.p) at least over some important classes of instances of that problem), we will substantially speed up Karmarkar's algorithm, K, for the l.p.p. because solving the l.l.s.p. constitutes the most costly part of every iteration of that algorithm. A very wide range of applications leads to in particular the acceleration of the simplex algorithms, see C,M, for sparse l.p. problems. Further applications may include several combinatorial computations. In the next section we recall two known representations of the l.l.s.p. using normal equations. In sect. 3 we reexamine the computational cost of sequential algorithms for l.l.s.p. In sect. 4 we estimate the cost of performing our parallel algorithm for the same problem. In sect. 5 we consider one of the major applications of our results, that is, to the acceleration of Karmarkar's algorithm. In Appendix we will briefly comment on the current estimates for the computational cost of solving the l.p.p.