Direct solution of linear systems of size \(10^{9}\) arising in optimization with interior point methods. (English) Zbl 1182.65050
Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 6th international conference, PPAM 2005, Poznań, Poland, September 11–14, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-34141-2/pbk). Lecture Notes in Computer Science 3911, 513-525 (2006).
Summary: 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.
For the entire collection see [Zbl 1103.68013].
For the entire collection see [Zbl 1103.68013].
MSC:
65F05 | Direct numerical methods for linear systems and matrix inversion |
65Y05 | Parallel numerical computation |
90C51 | Interior-point methods |