Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization

John Gunnels(gunnelsus.ibm.com)
Jon Lee(jonleeus.ibm.com)
Susan Margulies(susan.marguliesrice.edu)

Abstract: We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L computer at IBM's T.J. Watson Research Center. Additionally, we have delineated the necessary algorithmic and coding changes required in order to address problems several orders of magnitude larger, dealing with the limits of scalability from memory footprint, computational, reliability, and interconnect perspectives.

Keywords: Nonlinear matroid optimization, model fitting, polynomial model, matrix algebra, Vandemonde system, Stirling numbers, extended precision arithmetic, distributed reduction, parallel Cholesky, limits of scalability, Blue Gene.

Category 1: Combinatorial Optimization

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: IBM Research Report RC24682, 10/29/2008

Download: [PDF]

Entry Submitted: 11/10/2008
Entry Accepted: 11/11/2008
Entry Last Modified: 11/10/2008

Modify/Update this entry