iBet uBet web content aggregator. Adding the entire web to your favor.

Link to original content: https://doi.org/10.1145/1837210.1837230

Polynomial homotopies on multicore workstations | Proceedings of the 4th International Workshop on Parallel and Symbolic Computation

research-article

Polynomial homotopies on multicore workstations

Authors:

Jan Verschelde,

Genady YoffeAuthors Info & Claims

PASCO '10: Proceedings of the 4th International Workshop on Parallel and Symbolic Computation

Pages 131 - 140

https://doi.org/10.1145/1837210.1837230

Published: 21 July 2010 Publication History

Abstract

Homotopy continuation methods to solve polynomial systems scale very well on parallel machines. We examine its parallel implementation on multiprocessor multicore workstations using threads. With more cores we speed up pleasingly parallel path tracking jobs. In addition, we compute solutions more accurately in about the same amount of time with threads, and thus achieve quality up. Focusing on polynomial evaluation and linear system solving (key ingredients of Newton's method) we can double the accuracy of the results with the quad doubles of QD-2.3.9 in less than double the time, if all available eight cores are used.

References

[1]

AdaCore. The GNAT Reference Manual. At http://gcc.gnu.org/onlinedocs/gnat_rm.

[2]

S. G. Akl. Superlinear performance in real-time parallel computation. The Journal of Supercomputing, 29(1):89--111, 2004.

Digital Library

[3]

D. C. S. Allison, A. Chakraborty, and L. T. Watson. Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube. J. of Supercomputing, 3:5--20, 1989.

[4]

J. Backelin and R. Fröberg. How we proved that there are exactly 924 cyclic 7-roots. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC'91), pages 101--111. ACM, 1991.

Digital Library

[5]

D. H. Bailey, R. Barrio, and J. H. Borwein. High precision computation: Mathematical physics and dynamics. Joint SIAM-RSME-SCM-SEMA Meeting on Emerging Topics in Dynamical Systems and Partial Differential Equations (DSPDEs'10), 31 May 2010, Barcelona, Spain.

[6]

C. Bajaj, J. Canny, T. Garrity, and J. Warren. Factoring rational polynomials over the complex numbers. SIAM J. Comput., 22(2):318--331, 1993.

Digital Library

[7]

D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler. Adaptive multiprecision path tracking. SIAM J. Numer. Anal., 46(2):722--746, 2008.

Digital Library

[8]

D. J. Bates, J. D. Hauenstein, A. J. Sommese, and C. W. Wampler. Bertini: Software for numerical algebraic geometry. Available at http://www.nd.edu/~sommese/bertini/.

[9]

C. Beltran and Leykin. A. Certified numerical homotopy tracking. Preprint arXiv:0912.0920v1 {math.NA}.

[10]

R. H. Bisseling. Parallel Scientific Computation. A structured approach using BSP and MPI. Oxford University Press, 2004.

Digital Library

[11]

G. Björck and R. Fröberg. Methods to "divide out" certain solutions from systems of algebraic equations, applied to find all cyclic 8-roots. In M. Gyllenberg and L. E. Persson, editors, Analysis, Algebra and Computers in Math. research, volume 564 of Lecture Notes in Mathematics, pages 57--70. Dekker, 1994.

[12]

L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.

[13]

A. Burns and A. Wellings. Concurrent and Real-Time Programming in Ada. Cambridge University Press, 2007.

Digital Library

[14]

G. Chèze and A. Galligo. Four lectures on polynomial absolute factorization. In Solving Polynomial Equations. Foundations, Algorithms and Applications, volume 14 of Algorithms and Computation in Mathematics, pages 339--394. Springer-Verlag, 2005.

[15]

R. M. Corless, A. Galligo, I. S. Kotsireas, and S. M. Watt. A geometric-numeric algorithm for factoring multivariate polynomials. In T. Mora, editor, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC 2002), pages 37--45. ACM, 2002.

Digital Library

[16]

R. M. Corless, M. W. Giesbrecht, M. van Hoeij, I. S. Kotsireas, and S. M. Watt. Towards factoring bivariate approximate polynomials. In B. Mourrain, editor, Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation (ISSAC 2001), pages 85--92. ACM, 2001.

Digital Library

[17]

T. J. Dekker. A floating-point technique for extending the available precision. Numerische Mathematik, 18(3):224--242, 1971.

Digital Library

[18]

J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst. Numerical Linear Algebra for High-Performance Computers. SIAM, 1998.

Digital Library

[19]

J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart. LINPACK Users' Guide. SIAM, 1979.

[20]

A. Galligo and A. Poteaux. Continuations and monodromy on random Riemann surfaces. In H. Kai and H. Sekigawa, editors, SNC'09: Proceedings of the 2009 conference on Symbolic-Numeric Computation, pages 115--124. ACM, 2009.

Digital Library

[21]

A. Galligo and M. van Hoeij. Approximate bivariate factorization: a geometric viewpoint. In J. Verschelde and S. M. Watt, editors, SNC'07: Proceedings of the 2007 international workshop on Symbolic-Numeric Computation, pages 1--10. ACM, 2007.

Digital Library

[22]

T. Gao, T. Y. Li, and M. Wu. Algorithm 846: MixedVol: a software package for mixed-volume computation. ACM Trans. Math. Softw., 31(4):555--560, 2005.

Digital Library

[23]

Y. Guan and J. Verschelde. Parallel implementation of a subsystem-by-subsystem solver. In Proceedings of the 22th High Performance Computing Symposium, Quebec City, 9--11 June 2008, pages 117--123. IEEE Computer Society, 2008.

Digital Library

[24]

T. Gunji, S. Kim, K. Fujisawa, and M. Kojima. PHoMpara -- parallel implementation of the Polyhedral Homotopy continuation Method for polynomial systems. Computing, 77(4):387--411, 2006.

Digital Library

[25]

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/qd-2.3.9.tar.gz.

Digital Library

[26]

B. Huber and B. Sturmfels. A polyhedral method for solving sparse polynomial systems. Math. Comp., 64(212):1541--1555, 1995.

Digital Library

[27]

M. Kojima. Efficient evaluation of polynomials and their partial derivatives in homotopy continuation methods. Journal of the Operations Research Society of Japan, 51(1):29--54, 2008.

[28]

A Leykin and F. Sottile. Galois groups of Schubert problems via homotopy continuation. Mathematics of Computation, 78(267):1749--1765, 2009.

[29]

A. Leykin and J. Verschelde. Factoring solution sets of polynomial systems in parallel. In T. Skeie and C.-S. Yang, editors, Proceedings of the 2005 International Conference on Parallel Processing Workshops. 14--17 June 2005. Oslo, Norway. High Performance Scientific and Engineering Computing, pages 173--180. IEEE Computer Society, 2005.

Digital Library

[30]

A. Leykin and J. Verschelde. Decomposing solution sets of polynomial systems: a new parallel monodromy breakup algorithm. The International Journal of Computational Science and Engineering, 4(2):94--101, 2009.

Digital Library

[31]

A. Leykin, J. Verschelde, and Y. Zhuang. Parallel homotopy algorithms to solve polynomial systems. In N. Takayama and A. Iglesias, editors, Proceedings of ICMS 2006, volume 4151 of Lecture Notes in Computer Science, pages 225--234. Springer-Verlag, 2006.

Digital Library

[32]

T. Y. Li. Numerical solution of polynomial systems by homotopy continuation methods. In F. Cucker, editor, Handbook of Numerical Analysis. Volume XI. Special Volume: Foundations of Computational Mathematics, pages 209--304. North-Holland, 2003.

[33]

T. Y. Li, T. Sauer, and J. A. Yorke. The cheater's homotopy: an efficient procedure for solving systems of polynomial equations. SIAM J. Numer. Anal., 26(5):1241--1251, 1989.

Digital Library

[34]

T. Y. Li and C.-H. Tsai. HOM4PS-2.0para: Parallelization of HOM4PS-2.0 for solving polynomial systems. Parallel Computing, 35(4):226--238, 2009.

Digital Library

[35]

A. Morgan. Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, 1987. Volume 57 of Classics in Applied Mathematics Series, SIAM 2009.

Digital Library

[36]

A. P. Morgan and A. J. Sommese. Coefficient-parameter polynomial continuation. Appl. Math. Comput., 29(2):123--160, 1989. Errata: Appl. Math. Comput. 51:207(1992).

Digital Library

[37]

A. Poteaux. Computing monodromy groups defined by plane curves. In J. Verschelde and S. M. Watt, editors, SNC'07. Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation, pages 239--246. ACM, 2007.

Digital Library

[38]

D. N. Priest. On Properties of Floating Point Arithmetics: Numerical Stability and the Cost of Accurate Computations. PhD thesis, University of California at Berkeley, 1992. ftp://ftp.icsi.berkeley.edu/pub/theory/priest-thesis.ps.Z.

Digital Library

[39]

J. F. Ruiz. GNAT Pro for on-board mission-critical space applications. In T. Vardanega and A. Wellings, editors, Reliable Software Technology -- Ada-Europe 2005. 10th Ada-Europe International Conference on Reliable Software Technologies. York, UK, June 20--24, 2005. Proceedings, volume 3555 of Lecture Notes in Computer Science, pages 248--259, 2005.

Digital Library

[40]

J. R. Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geom., 18(3):305--363, 1997.

[41]

M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra. MPI - The Complete Reference Volume 1, The MPI Core. Massachusetts Institute of Technology, second edition, 1998.

Digital Library

[42]

A. J. Sommese, J. Verschelde, and C. W. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. In C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher, editors, Application of Algebraic Geometry to Coding Theory, Physics and Computation, pages 297--315. Kluwer Academic Publishers, 2001. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel.

[43]

A. J. Sommese and C. W. Wampler. The Numerical solution of systems of polynomials arising in engineering and science. World Scientific, 2005.

[44]

H.-J. Su, J. M. McCarthy, M. Sosonkina, and L. T. Watson. Algorithm 857: POLSYS_GLP: A parallel general linear product homotopy code for solving polynomial systems of equations. ACM Trans. Math. Softw., 32(4):561--579, 2006.

Digital Library

[45]

J. Verschelde. Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw., 25(2):251--276, 1999. Software available at http://www.math.uic.edu/~jan/download.html.

Digital Library

[46]

J. Verschelde and Y. Wang. Computing feedback laws for linear systems with a parallel Pieri homotopy. In Y. Yang, editor, Proceedings of the 2004 International Conference on Parallel Processing Workshops, 15--18 August 2004, Montreal, Quebec, Canada. High Performance Scientific and Engineering Computing, pages 222--229. IEEE Computer Society, 2004.

Digital Library

[47]

J. Verschelde and Y. Zhuang. Parallel implementation of the polyhedral homotopy method. In T. M. Pinkston and F. Ozguner, editors, Proceedings of the 2006 International Conference on Parallel Processing Workshops. 14--18 Augustus 2006. Columbus, Ohio. High Performance Scientific and Engineering Computing, pages 481--488. IEEE Computer Society, 2006.

Digital Library

[48]

Y. Wang. Computing Dynamic Output Feedback Laws with Pieri Homotopies on a Parallel Computer. PhD thesis, University of Illinois at Chicago, 2005.

Digital Library

[49]

B. Wilkinson and M. Allen. Parallel Programming. Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall, 2nd edition, 2005.

Digital Library

[50]

Y. Zhuang. Parallel Implementation of Polyhedral Homotopy Methods. PhD thesis, University of Illinois at Chicago, 2007.

Digital Library

Cited By

Verschelde JYu X(2016)Polynomial homotopy continuation on GPUsACM Communications in Computer Algebra10.1145/2893803.289381049:4(130-133)Online publication date: 17-Feb-2016
https://dl.acm.org/doi/10.1145/2893803.2893810
Verschelde JYu XPernet C(2015)Accelerating polynomial homotopy continuation on a graphics processing unit with double double and quad double arithmeticProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790294(109-118)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790294
Verschelde JYu X(2014)GPU Acceleration of Newton's Method for Large Systems of Polynomial Equations in Double Double and Quad Double ArithmeticProceedings of the 2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS)10.1109/HPCC.2014.31(161-164)Online publication date: 20-Aug-2014
https://dl.acm.org/doi/10.1109/HPCC.2014.31
Show More Cited By

Index Terms

Polynomial homotopies on multicore workstations
1. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations

Recommendations

Number of Tasks, not Threads, is Key
PDP '15: Proceedings of the 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing

The concept of task already exists in many parallel programming models. Programmers express parallelism by defining tasks in their applications, and runtime libraries schedule tasks on threads. However, in many task-based parallel programming models, ...
Parallel homotopy algorithms to solve polynomial systems
ICMS'06: Proceedings of the Second international conference on Mathematical Software

Homotopy continuation methods to compute numerical approximations to all isolated solutions of a polynomial system are known as “embarrassingly parallel”, i.e.: because of their low communication overhead, these methods scale very well for a large ...
Teaching Parallel Computing Concepts with OpenMP (Abstract Only)
SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education

OpenMP is an industry-standard, platform-independent parallel programming library built into all modern C and C++ compilers. Unlike complex parallel platforms, OpenMP is designed to make it relatively easy to add parallelism to existing sequential ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

PASCO '10: Proceedings of the 4th International Workshop on Parallel and Symbolic Computation

July 2010

192 pages

ISBN:9781450300674

DOI:10.1145/1837210

Editors:
Marc Moreno Maza
London
,
Jean-Louis Roch
Grenoble

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Grenoble University: Grenoble University
Grenoble INP / ENSIMAG
INRIA: Institut Natl de Recherche en Info et en Automatique

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

PASCO '10

Sponsor:

Grenoble University
INRIA

PASCO '10: 4th International Workshop on Parallel and Symbolic Computation

July 21 - 23, 2010

Grenoble, France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
88
Total Downloads

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

Reflects downloads up to 05 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Verschelde JYu X(2016)Polynomial homotopy continuation on GPUsACM Communications in Computer Algebra10.1145/2893803.289381049:4(130-133)Online publication date: 17-Feb-2016
https://dl.acm.org/doi/10.1145/2893803.2893810
Verschelde JYu XPernet C(2015)Accelerating polynomial homotopy continuation on a graphics processing unit with double double and quad double arithmeticProceedings of the 2015 International Workshop on Parallel Symbolic Computation10.1145/2790282.2790294(109-118)Online publication date: 10-Jul-2015
https://dl.acm.org/doi/10.1145/2790282.2790294
Verschelde JYu X(2014)GPU Acceleration of Newton's Method for Large Systems of Polynomial Equations in Double Double and Quad Double ArithmeticProceedings of the 2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS)10.1109/HPCC.2014.31(161-164)Online publication date: 20-Aug-2014
https://dl.acm.org/doi/10.1109/HPCC.2014.31
Verschelde JYoffe G(2013)Orthogonalization on a General Purpose Graphics Processing Unit with Double Double and Quad Double ArithmeticProceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPSW.2013.189(1373-1380)Online publication date: 20-May-2013
https://dl.acm.org/doi/10.1109/IPDPSW.2013.189
Verschelde JYoffe G(2012)Evaluating Polynomials in Several Variables and their Derivatives on a GPU Computing ProcessorProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum10.1109/IPDPSW.2012.177(1397-1405)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPSW.2012.177
Li YDos Reis GSchost ÉEmiris I(2011)An automatic parallelization framework for algebraic computation systemsProceedings of the 36th international symposium on Symbolic and algebraic computation10.1145/1993886.1993923(233-240)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1145/1993886.1993923
Guan YVerschelde J(2011)Sampling algebraic sets in local intrinsic coordinatesComputers & Mathematics with Applications10.1016/j.camwa.2011.09.01362:10(3706-3721)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.camwa.2011.09.013

View Options

Get Access

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 Table of Contents