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

John Gunnels, Jon Lee, Susan Margulies

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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. © Springer and Mathematical Programming Society 2010.
Original languageEnglish (US)
Pages (from-to)103-124
Number of pages22
JournalMathematical Programming Computation
Volume2
Issue number2
DOIs
StatePublished - Jun 19 2010
Externally publishedYes

Fingerprint Dive into the research topics of 'Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization'. Together they form a unique fingerprint.

Cite this