Accession Number : ADA188500

Title :   Primal - Dual Parallel Solution of Very Large Sparse Linear Programs.

Descriptive Note : Final rept. 30 Jul 86-29 Jun 87,

Corporate Author : WISCONSIN UNIV-MADISON DEPT OF COMPUTER SCIENCES

Personal Author(s) : Mangasarian, Olvi L

PDF Url : ADA188500

Report Date : 17 Sep 1987

Pagination or Media Count : 6

Abstract : The principal area of our research has been the solution of very large sparse linear programs and linear complementarity problems by successive overrelaxation (SOR) methods. Another important ingredient of our research has been the parallelization of our SOR methods as well as other classical methods such as the simplex method for linear programming and Lemke's method for the linear complementarity problem. A major contribution of our research has been the solution of on of the largest general linear programs ever attempted on a workstation (or in fact on a mainframe). A linear program with 500,000 variables, 125,000 constraints and 1,125,000 nonzero matrix elements was solved in less than 72 hours on one of the Micro Vax II computers. Another significant achievement of our research has been the parallelization of our SOR methods with speedup efficiencies sometimes exceeding 100%. The MicroVax II's were used to test simulations of the parallel SOR algorithms before their implementation on our multicomputers and multiprocessors.

Descriptors :   *LINEAR PROGRAMMING, ALGORITHMS, MULTIPROCESSORS, PARALLEL PROCESSING, SIMPLEX METHOD, MICROCOMPUTERS, COMPUTERIZED SIMULATION

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE