Direct Solution of Linear Systems of Size 109
Arising in Optimization with Interior Point Methods

Technical Report MS 2005-003

J. Gondzio and A. Grothey

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 109 variables.

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

PDF MS05-003.pdf.
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.