Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases

Abstract

This paper discusses the computation of LU factorizations for large sparse matrices with emphasis on large-scale linear programming bases. We present new implementation techniques which reduce the computation times significantly. Numerical experiments with large-scale real life test problems were conducted. The software is compared with the basis factorization of MPSX/370, IBM's commercial LP system. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.