Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
Mathematics Technical Papers >

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

Title: Solving large scale linear programming problems
Authors: Levkovitz, R
Publication Date: 1993
Publisher: Brunel University
Citation: Maths Technical Papers (Brunel University). August 1993, pp 1-24
Abstract: The interior point method (IPM) is now well established as a computationaly com-petitive scheme for solving very large scale linear programming problems. The leading variant of the IPM is the primal dual predictor corrector algorithm due to Mehrotra. The main computational efforts in this algorithm are the repeated calculation and solution of a large sparse positive definite system of equations. We describe an implementation of this algorithm for vector processors. At the heart of the implementation is a vectorized matrix multiplication and Cholesky factorization for sparse matrices. We identify the parts where vectorization can be beneficial and discuss in details the merits of alternative vectorization techniques. We show that the best way to utilize a vector processor is by exploiting dense computation within the sparse framework and by unrolling loop operations. We further present an extended definition of supernodes, and describe an implementation based on this new approach. We show that although this approach requires more memory it can increase the scope of dense computation substantially with out adding extra operations. Performance results on standard industrial test problems and comparison between an algorithm that utilizes the extended supernodes and one that utilizes standard supernodes are presented and discussed.
URI: http://bura.brunel.ac.uk/handle/2438/2077
Appears in Collections:Mathematics Technical Papers

Files in This Item:

File Description SizeFormat
TR_06_93.pdf872.34 kBAdobe PDFView/Open

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