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

John Gunnels; Jon Lee; Susan Margulies

doi:10.1007/s12532-010-0014-4

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

John Gunnels, Jon Lee, Susan Margulies

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	103-124
Number of pages	22
Journal	Mathematical Programming Computation
Volume	2
Issue number	2
DOIs	https://doi.org/10.1007/s12532-010-0014-4
State	Published - Jun 19 2010
Externally published	Yes

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.

Access to Document

10.1007/s12532-010-0014-4

Cite this

@article{f44d93cd2ba04ad5acbaff1af789d9a8,

title = "Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization",

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. {\textcopyright} Springer and Mathematical Programming Society 2010.",

author = "John Gunnels and Jon Lee and Susan Margulies",

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.",

year = "2010",

month = jun,

day = "19",

doi = "10.1007/s12532-010-0014-4",

language = "English (US)",

volume = "2",

pages = "103--124",

journal = "Mathematical Programming Computation",

issn = "1867-2949",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

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

AU - Gunnels, John

AU - Lee, Jon

AU - Margulies, Susan

N1 - 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.

PY - 2010/6/19

Y1 - 2010/6/19

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/598106

UR - http://link.springer.com/10.1007/s12532-010-0014-4

UR - http://www.scopus.com/inward/record.url?scp=84870396157&partnerID=8YFLogxK

U2 - 10.1007/s12532-010-0014-4

DO - 10.1007/s12532-010-0014-4

M3 - Article

SN - 1867-2949

VL - 2

SP - 103

EP - 124

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

IS - 2

ER -

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

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this