#
Direct Solution of Linear Systems of Size 10^{9}

Arising in Optimization with Interior Point Methods

###
Technical Report MS 2005-003

**
J. Gondzio and
A. Grothey
**

**
Abstract
**

Solution methods for very large scale optimization problems
are addressed in this paper. Interior point methods are
demonstrated to provide unequalled efficiency in this context.
They need a small (and predictable) number of iterations
to solve a problem. A single iteration of interior point
method requires the solution of indefinite system of equations.
This system is regularized to guarantee the existence
of triangular decomposition. Hence the well-understood
parallel computing techniques developed for positive definite
matrices can be extended to this class of indefinite matrices.
A parallel implementation of an interior point method is described
in this paper. It uses object-oriented programming techniques
and allows for exploiting different block-structures of matrices.
Our implementation outperforms the industry-standard optimizer,
shows very good parallel efficiency on massively parallel architecture
and solves problems of unprecedented sizes reaching 10^{9} variables.

**
Key words:
**
Very Large Scale Optimization, Interior Point Methods,
Exploiting Structure, Parallel Computing.

**
Text
**

PDF MS05-003.pdf.

**
History:
**

Written: November 30, 2005.

R. Wyrzykowski, J. Dongarra, N. Meyer and J. Wasniewski (eds.),
Parallel Processing and Applied Mathematics PPAM 2005,
*Lecture Notes in Computer Science,* **3911**,
Springer-Verlag, Berlin, 2006, pp 513-525.

**
Related Software:
**

OOPS
Object-Oriented Parallel Solver.