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


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
Issue number2
StatePublished - Jun 19 2010
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: We gratefully acknowledge the use of the IBM Shaheen (which at the time of ourexperiments was an 8-rack Blue Gene/P supercomputer housed at the IBM T.J. Watson Research Center).The IBM Shaheen is now owned and operated by the King Abdullah University of Science and Technology(KAUST). We would like to thank Bob Walkup at IBM Research for his help in many aspects of this work,including the use of his performance-counter library for performance evaluation and Fred Mintzer at IBMResearch for arranging for our use of the Blue Gene/P Supercomputer. We are deeply indebted to DavidBailey and his team for the ARPREC software package and documentation. Our work was partially car-ried out, while S. Margulies was a graduate student at U.C. Davis, under an Open Collaborative Researchagreement between IBM and U.C. Davis.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


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