More Web Proxy on the site http://driver.im/

research-article

Polynomial homotopy continuation on GPUs

Authors:

Jan Verschelde,

Xiangcheng YuAuthors Info & Claims

ACM Communications in Computer Algebra, Volume 49, Issue 4

Pages 130 - 133

https://doi.org/10.1145/2893803.2893810

Published: 17 February 2016 Publication History

Abstract

The purpose of the software presentation is to announce a library to track many solution paths defined by a polynomial homotopy on a Graphics Processing Unit (GPU). Developed on NVIDIA graphics cards with CUDA SDKs, our code is released under the GNU GPL license. Via the C interface to PHCpack, we can call our GPU library from Python.

References

[1]

N. Bliss, J. Sommars, J. Verschelde, and Xiangcheng Yu. Solving polynomial systems in the cloud with polynomial homotopy continuation. In V.P. Gerdt, W. Koepf, E.W. Mayr, and E.V. Vorozhtsov, editors, Computer Algebra in Scientific Computing, 17th International Workshop, CASC 2015, Aachen, Germany, volume 9301 of Lecture Notes in Computer Science, pages 87--100. Springer-Verlag, 2015.

[2]

A. Griewank and A. Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, second edition, 2008.

Digital Library

[3]

Y. Hida, X. S. Li, and D. H. Bailey. Algorithms for quad-double precision floating point arithmetic. In 15th IEEE Symposium on Computer Arithmetic (Arith-15 2001), 11--17 June 2001, Vail, CO, USA, pages 155--162. IEEE Computer Society, 2001. Shortened version of Technical Report LBNL-46996, software at http://crd.lbl.gov/~dhbailey/mpdist.

Digital Library

[4]

A. Leykin and J. Verschelde. Interfacing with the numerical homotopy algorithms in PHCpack. In N. Takayama and A. Iglesias, editors, Proceedings of ICMS 2006, volume 4151 of Lecture Notes in Computer Science, pages 354--360. Springer-Verlag, 2006.

Digital Library

[5]

M. Lu, B. He, and Q. Luo. Supporting extended precision on graphics processors. In A. Ailamaki and P.A. Boncz, editors, Proceedings of the Sixth International Workshop on Data Management on New Hardware (DaMoN 2010), June 7, 2010, Indianapolis, Indiana, pages 19--26, 2010. Software at http://code.google.com/p/gpuprec/.

Digital Library

[6]

S. M. Rump. Verification methods: Rigorous results using floating-point arithmetic. Acta Numerica, 19:287449, 2010.

[7]

J. Verschelde. Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw., 25(2):251--276, 1999.

Digital Library

[8]

J. Verschelde. Polynomial homotopy continuation with PHCpack. ACM Communications in Computer Algebra, 44(4):217--220, 2010.

Digital Library

[9]

J. Verschelde. Modernizing PHCpack through phcpy. In P. de Buyl and N. Varoquaux, editors, Proceedings of the 6th European Conference on Python in Science (EuroSciPy 2013), pages 71--76, 2014.

[10]

J. Verschelde and G. Yoffe. Polynomial homotopies on multicore workstations. In M.M. Maza and J.-L. Roch, editors, Proceedings of the 4th International Workshop on Parallel Symbolic Computation (PASCO 2010), July 21-23 2010, Grenoble, France, pages 131--140. ACM, 2010.

Digital Library

[11]

J. Verschelde and G. Yoffe. Evaluating polynomials in several variables and their derivatives on a GPU computing processor. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops (PDSEC 2012), pages 1391--1399. IEEE Computer Society, 2012.

Digital Library

[12]

J. Verschelde and G. Yoffe. Orthogonalization on a general purpose graphics processing unit with double double and quad double arithmetic. In Proceedings of the 2013 IEEE 27th International Parallel and Distributed Processing Symposium Workshops (PDSEC 2013), pages 1373--1380. IEEE Computer Society, 2013.

Digital Library

[13]

J. Verschelde and X. Yu. GPU acceleration of Newton's method for large systems of polynomial equations in double double and quad double arithmetic. In Proceedings of the 16th IEEE International Conference on High Performance Computing and Communication (HPCC 2014), pages 161--164. IEEE Computer Society, 2014.

Digital Library

[14]

J. Verschelde and X. Yu. Accelerating polynomial homotopy continuation on a graphics processing unit with double double and quad double arithmetic. In J.-G. Dumas and E.L. Kaltofen, editors, Proceedings of the 7th International Workshop on Parallel Symbolic Computation (PASCO 2015), July 10--11 2015, Bath, United Kingdom, pages 109--118. ACM, 2015.

Digital Library

[15]

J. Verschelde and X. Yu. Tracking many solution paths of a polynomial homotopy on a graphics processing unit in double double and quad double arithmetic. In Proceedings of the 17th IEEE International Conference on High Performance Computing and Communication (HPCC 2015), pages 371--376. IEEE Computer Society, 2015.

Digital Library

Cited By

Barbosa-Ayala OMontañez-Barrera JDamian-Ascencio CSaldaña-Robles AAlfaro-Ayala JPadilla-Medina JCano-Andrade S(2020)Solution to the Economic Emission Dispatch Problem Using Numerical Polynomial Homotopy ContinuationEnergies10.3390/en1317428113:17(4281)Online publication date: 19-Aug-2020
https://doi.org/10.3390/en13174281
Li XGe QGao F(2018)A Computational Geometric Approach for Motion Generation of Spatial Linkages With Sphere and Plane ConstraintsJournal of Mechanisms and Robotics10.1115/1.404178811:1Online publication date: 10-Dec-2018
https://doi.org/10.1115/1.4041788

Recommendations

Brook for GPUs: stream computing on graphics hardware
SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a ...
Brook for GPUs: stream computing on graphics hardware

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a ...
LU Decomposition on GPUs: The Impact of Memory Access
SBAC-PADW '10: Proceedings of the 2010 22nd International Symposium on Computer Architecture and High Performance Computing Workshops

Graphics Processing Units (GPUs) are emerging as an attractive computing platform for general purpose computations due to their extremely high floating-point processing performance and their comparatively low cost. In the context of dense linear algebra,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Communications in Computer Algebra

ACM Communications in Computer Algebra Volume 49, Issue 4

December 2015

23 pages

ISSN:1932-2232

EISSN:1932-2240

DOI:10.1145/2893803

Issue’s Table of Contents

Copyright © 2016 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 February 2016

Published in SIGSAM-CCA Volume 49, Issue 4

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barbosa-Ayala OMontañez-Barrera JDamian-Ascencio CSaldaña-Robles AAlfaro-Ayala JPadilla-Medina JCano-Andrade S(2020)Solution to the Economic Emission Dispatch Problem Using Numerical Polynomial Homotopy ContinuationEnergies10.3390/en1317428113:17(4281)Online publication date: 19-Aug-2020
https://doi.org/10.3390/en13174281
Li XGe QGao F(2018)A Computational Geometric Approach for Motion Generation of Spatial Linkages With Sphere and Plane ConstraintsJournal of Mechanisms and Robotics10.1115/1.404178811:1Online publication date: 10-Dec-2018
https://doi.org/10.1115/1.4041788

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents