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

**ORSA J. on Computing**, vol.** **1,
pp. 84-106, 1989.

**ABSTRACT**

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 then 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.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home PageLast modified: