Mathematical Programming Computation, Volume 2, Number 2 / June 2010

Font Size:  Small  Medium  Large

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

John Gunnels, Jon Lee, Susan Margulies


We provide a first demonstration of the idea that matrix-based algorithms for nonlinear combinatorial optimization problems can be efficiently implemented. Such algorithms were mainly conceived by theoretical computer scientists for proving efficiency. We are able to demonstrate the practicality of our approach by developing an implementation on a massively parallel architecture, and exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision linear algebra. Additionally, we have delineated and implemented 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 efficiency, reliability, and interconnect perspectives.

Full Text: PDF

mpc footer
© MPS 2008-2019