Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/1899

Title: Adapting the interior point method for the solution of linear programs on high performance computers
Authors: Anderson, J
Levkovitz, R
Mitra, G
Publication Date: 1991
Publisher: Brunel University
Citation: Maths Technical Papers (Brunel University). Oct 1991, pp 1-14
Abstract: In this paper we describe a unified algorithmic framework for the interior point method (IPM) of solving Linear Programs (LPs) which allows us to adapt it over a range of high performance computer architectures. We set out the reasons as to why IPM makes better use of high performance computer architecture than the sparse simplex method. In the inner iteration of the IPM a search direction is computed using Newton or higher order methods. Computationally this involves solving a sparse symmetric positive definite (SSPD) system of equations. The choice of direct and indirect methods for the solution of this system and the design of data structures to take advantage of coarse grain parallel and massively parallel computer architectures are considered in detail. Finally, we present experimental results of solving NETLIB test problems on examples of these architectures and put forward arguments as to why integration of the system within sparse simplex is beneficial.
URI: http://bura.brunel.ac.uk/handle/2438/1899
Appears in Collections:Mathematical Science
Dept of Mathematics Research Papers

Files in This Item:

File Description SizeFormat
TR_15_91.pdf375.15 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.