Data structures and programming techniques for the implementation of Karmarkar’s algorithm. (English) Zbl 0752.90043

Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio G. C.; Veiga, Geraldo

ORSA J. Comput. 1, No. 2, 84-106 (1989).

Summary: This paper describes data structures and programming techniques used in an implementation of Karmarkar’s algorithm for linear programming. Most of our discussion focuses on applying Gaussian elimination toward the solution of a sequence of sparse symmetric positive definite systems of linear equations, the main requirement in Karmarkar’s algorithm. Our approach relies on a direct factorization scheme, with an extensive symbolic factorization step performed in a preparatory stage of the linear programming algorithm. An interpretative version of Gaussian elimination makes use of the symbolic information to perform the actual numerical computations at each iteration of the algorithm. We also discuss ordering algorithms that attempt to reduce the amount of fill-in in the LU factors, a procedure to build the linear system solved at each iteration, the use of a dense window data structure in the Gaussian elimination method, a preprocessing procedure designed to increase the sparsity of the linear programming coefficient matrix, and the special treatment of dense columns in the coefficient matrix.

MSC:

90C05	Linear programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

data structures; implementation of Karmarkar’s algorithm; Gaussian elimination; symbolic factorization step