A parallel formulation of interior point algorithms

Author

Karypis, George ; Gupta, Anshul ; Kumar, Vipin

Author_Institution

Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA

fYear

1994

fDate

14-18 Nov 1994

Firstpage

204

Lastpage

213

Abstract

Describes a scalable parallel formulation of interior point algorithms. Through our implementation on a 256-processor nCUBE 2 parallel computer, we show that our parallel formulation utilizes hundreds of processors efficiently and delivers much higher performance and speedups than reported earlier. These speedups are a result of our highly efficient parallel algorithm for solving a linear symmetric positive definite system using Cholesky factorization. We also evaluate a number of ordering algorithms for sparse matrix factorization in terms of their suitability for parallel Cholesky factorization

Keywords

linear programming; mathematics computing; parallel algorithms; software performance evaluation; sparse matrices; efficient parallel algorithm; interior point algorithms; linear programming; linear symmetric positive definite system; nCUBE 2 parallel computer; ordering algorithms; parallel Cholesky factorization; performance; scalable parallel formulation; sparse matrix factorization; speedups; Computer science; Concurrent computing; Contracts; High performance computing; Iterative algorithms; Iterative methods; Linear programming; Parallel algorithms; Polynomials; Sparse matrices;

fLanguage

English

Publisher

ieee

Conference_Titel

Supercomputing '94., Proceedings

Conference_Location

Washington, DC

Print_ISBN

0-8186-6605-6

Type

conf

DOI

10.1109/SUPERC.1994.344280

Filename

344280