article

Free Access

Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation

Author:
Jan Verschelde

Mathematical Sciences Research Institute, Berkeley, CA

Mathematical Sciences Research Institute, Berkeley, CA
View Profile

Authors Info & Claims

ACM Transactions on Mathematical Software Volume 25 Issue 2pp 251–276https://doi.org/10.1145/317275.317286

Published:01 June 1999Publication History

ACM Transactions on Mathematical Software

Abstract

Polynomial systems occur in a wide variety of application domains. Homotopy continuation methods are reliable and powerful methods to compute numerically approximations to all isolated complex solutions. During the last decade considerable progress has been accomplished on exploiting structure in a polynomial system, in particular its sparsity. In this article the structure and design of the software package PHC is described. The main program operates in several modes, is menu driven, and is file oriented. This package features great variety of root-counting methods among its tools. The outline of one black-box solver is sketched, and a report is given on its performance on a large database of test problems. The software has been developed on four different machine architectures. Its portability is ensured by the gnu-ada compiler.

Supplemental Material

Available for Download

795.gz (789.4 KB)

Software for "PHCpack: a general-purpose solver for polynomial systems by homotopy continuation"

References

ADA CORE TECHNOLOGIES. 1997. GNAT user's guide: The GNU Ada 95 compiler. Ada Core Technologies, New York, NY. Available at http://www.gnat.com.Google Scholar
ALLISON, D. C. S., CHAKRABORTY, A., AND WATSON, L. T. 1989. Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube. J. Supercomput. 3, 5-20.Google ScholarCross Ref
BACKELIN, J.-R. AND FR BERG, R. 1991. 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, Bonn, Germany, July 15-17, 1991), S. M. Watt, Ed. ACM Press, New York, NY, 103-111. Google ScholarDigital Library
BELLIDO, A. M. 1992. Construction of iteration functions for the simultaneous computation of the solutions of equations and algebraic systems. Num. Alg. 6, 3-4, 317-351.Google Scholar
BERNSHTEIN, D. N. 1975. The number of roots of a system of equations. Func. Anal. Apps. 9, 3, 183-185.Google ScholarCross Ref
BINI, D. AND MOURRAIN, B. 1998. Polynomial test suite, http://www-sop.inria.fr/saga/POL/.Google Scholar
BJ RCK, a. AND FR BERG, R. 1991. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots. J. Symb. Comput. 12, 3 (Sept. 1991), 329-336. Google ScholarDigital Library
BJ RCK, G. AND FR BERG, R. 1994. Methods to "divide out" certain solutions from systems of algebraic equations, applied to find all cyclic 8-roots. In Analysis, Algebra and Computers in Mathematical Research, M. Gyllenberg and L. Persson, Eds. Marcel Dekker, Inc. Series of Pure and Applied Mathematics, vol. 564. 57-70.Google Scholar
BLUM, L., CUCKER, F., SHUB, M., AND SMALL, S. 1997. Complexity and Real Computation. Springer-Verlag, New York, NY. Google ScholarDigital Library
BOEGE, W., GEBAUER, R., AND KREDEL, H. 1986. Some examples for solving systems of algebraic equations by calculating Groebner bases. J. Symb. Comput. 2, 1 (Mar. 1986), 83-98. Google ScholarDigital Library
BOON, S. 1992. Solving systems of equations. Sci. Math. Num-Analysis. Newsgroup Article 3529.Google Scholar
CANNY, J. AND ROJAS, J. M. 1991. An optimal condition for determining the exact number of roots of a polynomial system. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC '91, Bonn, Germany, July 15-17, 1991), S. M. Watt, Ed. ACM Press, New York, NY, 96-102. Google ScholarDigital Library
CHU, M. T., LI, T. Y., AND SAUER, T. 1988. Homotopy method for general A-matrix problems. SIAM J. Matrix Anal. Appl. 9, 4 (Oct. 1988), 528-536. Google ScholarDigital Library
COHN, H. AND DEUTSCH, g. 1988. An explicit modular equation in two variables for Q{sqrt(3)}. Math. Comput. 50, 557-568.Google Scholar
Cox, D., LITTLE, J., AND O'SHEA, D. 1998. Using Algebraic Geometry. Springer Graduate Texts in Mathematics, vol. 185. Springer-Verlag, New York, NY.Google Scholar
EMIRIS, I. Z. 1994. Sparse elimination and applications in kinematics. Ph.D. Dissertation. Computer Science Department, University of California at Berkeley, Berkeley, CA. Available at http://www.inria.fr/saga/emiris. Google ScholarDigital Library
EMIRIS, I. Z. 1997. A general solver based on sparse resultants: Numerical issues and kinematic applications. Rapport de recherche no. 3110. INRIA, Rennes, France. Available via anonymous ftp to ftp.inria.fr.Google Scholar
EMIRIS, I. Z. 1998. Symbolic-numeric algebra for polynomials. In Encyclopedia of Computer Science and Technology, A. Kent and J. Williams, Eds. Encyclopedia of Computer Science, vol. 39. Marcel Dekker, Inc., New York, NY, 261-281.Google Scholar
EMIRIS, I. Z. AND CANNY, J. F. 1995. Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Comput. 20, 2 (Aug. 1995), 117-149. Google ScholarDigital Library
EMIRIS, I. Z. AND VERSCHELDE, g. 1999. How to count efficiently all affine roots of a polynomial system. Discrete Appl. Math. 93, 1, 21-32. Google ScholarDigital Library
GALLIGO, A. AND TRAVERSO, C. 1989. Practical determination of the dimension of an algebraic variety. In Proceedings of the 3rd Conference on Computers and Mathematics (Boston, MA, June 13-17, 1989), E. Kaltofen and S. M. Watt, Eds. Conferences in Computers and Mathematics Springer-Verlag, New York, NY, 46-52. Google ScholarDigital Library
GAO, T., LI, T. Y., AND WANG, X. 1997. Finding isolated zeros of polynomial systems in Cn with stable mixed volumes. J. Symb. Comput. To be published. Google ScholarDigital Library
GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY. Google ScholarDigital Library
GATERMANN, K. 1990. Symbolic solution of polynomial equation systems with symmetry. In Symbolic and Algebraic Computation on Proceedings of the International Symposium (ISSAAC '90, Tokyo, Japan), S. Watanabe and M. Nagata, Eds. ACM Press, New York, NY, 112-119. Google ScholarDigital Library
GEL'FAND, I. M., KAPRANOV, M. M., AND ZELEVINSKY, A.V. 1994. Discriminants, Resultants and Multidimensional Determinants. Birkh user Boston Inc., Cambridge, MA.Google Scholar
GIORDANO, T. 1996. Impl mention distribu e du calcul du volume mixte. Master's Thesis. University of Nice, Sophia-Antipolis, France.Google Scholar
HARIMOTO, S. AND WATSON, L.T. 1989. The granularity of homotopy algorithms for polynomial systems of equations. In Parallel Processing for Scientific Computing, G. Rodrique, Ed. SIAM, Philadelphia, PA, 115-120. Google ScholarDigital Library
HUBER, B. 1995. Pelican manual. Availabe via http://www.mrsi.org/people/members/birk.Google Scholar
HUBER, B. T. 1996. Solving sparse polynomial systems. Ph.D. Dissertation. Cornell University, Ithaca, NY. Available at http://www.msri.org/people/members/birk.Google Scholar
HUBER, B. AND STURMFELS, B. 1995. A polyhedral method for solving sparse polynomial systems. Math. Comput. 64, 212 (Oct. 1995), 1541-1555. Google ScholarDigital Library
HUBER, B. AND STURMFELS, B. 1997. Bernstein's theorem in affine space. Discrete Comput. Geom. 17, 2, 137-141.Google ScholarDigital Library
HUBER, B. AND VERSCHELDE, J. 1998. Polyhedral end games for polynomial continuation. Num. Alg. 18, 1, 91-108.Google ScholarCross Ref
HUBER, B., SOTTILE, F., AND STURMFELS, B. 1998. Numerical Schubert calculus. J. Symb. Comput. 26, 6, 767-788. Google ScholarDigital Library
KHOVANSKII, A. 1991. Fewnomials. Translations of Mathematical Monographs, vol. 88. American Mathematical Society, Boston, MA.Google Scholar
KLEIMAN, S. AND LAKSOV, D. 1972. Schubert calculus. Am. Math. Mon. 79, 10, 1061-1082.Google ScholarCross Ref
KUSHNIRENKO, A. 1976. Newton Polytopes and the B zout Theorem. Func. Anal. Apps. 10, 3, 233-235.Google ScholarCross Ref
LI, T.-Y. 1987. Solving polynomial systems. Math. Intell. 9, 3, 33-39.Google ScholarCross Ref
LI, T.-Y. 1997. Numerical solutions of multivariate polynomial systems by homotopy continuation methods. Act. Numer. 6, 399-436.Google ScholarCross Ref
LI, T.-Y. AND SAUER, T. 1987. Regularity results for solving systems of polynomials by homotopy method. Numer. Math. 50, 3, 283-289. Google ScholarDigital Library
LI, T.-Y. AND WANG, X. 1991. Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant. Math. Comput. 56, 194, 693-710.Google ScholarCross Ref
LI, T.-Y. AND WANG, X. 1992. Nonlinear homotopies for solving deficient polynomial systems with parameters. SIAM J. Numer. Anal. 29, 4 (Aug. 1992), 1104-1118. Google ScholarDigital Library
LI, T.-Y. AND WANG, X. 1996. The BKK root count in Cn. Math. Comput. 65, 216, 1477-1484. Google ScholarDigital Library
LI, T.-Y., SAUER, T., AND YORKE, J. A. 1987a. Numerical solution of a class of deficient polynomial systems. SIAM J. Numer. Anal. 24, 2 (Apr. 1987), 435-451. Google ScholarDigital Library
LI, T.-Y., SAUER, T., AND YORKE, J.A. 1987b. The random product homotopy and deficient polynomial systems. Numer. Math. 51, 5, 481-500. Google ScholarDigital Library
LI, T.-Y., SAUER, T., AND YORKE, g. A. 1989. The cheater's homotopy: An efficient procedure for solving systems of polynomial equations. SIAM J. Numer. Anal. 26, 5 (Oct. 1989), 1241-1251. Google ScholarDigital Library
LI, T.-Y., WANG, T., AND WANG, X. 1996. Random product homotopy with minimal BKK bound. In The Mathematics of Numerical Analysis, J. Renegar, M. Shub, and S. Smale, Eds. Lectures in Applied Mathematics, vol. 32.Google Scholar
MALAJOVICH, G. 1996. pss 2.beta, polynomial system solver. (Software). Available at http://www.labma.ufrj.br:80/gregorio.Google Scholar
THE FRISCO CONSORTIUM. 1996. FRISCO--A framework for integrated symbolic/numeric computation. Available at http://www.nag.co.uk/projects/FRISCO.html.Google Scholar
THE PISA TEAM OF PoSSo. 1993. PoSSo home page. http://janet.dm.unipi.it/.Google Scholar
MEINTJES, K. AND MORGAN, A. P. 1990. Chemical equilibrium systems as numerical test problems. ACM Trans. Math. Softw. 16, 2 (June 1990), 143-151. Google ScholarDigital Library
MOORE, R. E. AND JONES, S.T. 1977. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14, 6, 1051-1065.Google ScholarCross Ref
MOR , J. J., GARBOW, B. S., AND HILLSTROM, K. E. 1981. Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 1 (Mar.), 17-41. Google ScholarDigital Library
MORGAN, A. P. 1987. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall, Inc., Upper Saddle River, NJ.Google Scholar
MORGAN, A. AND SHAPIRO, V. 1987a. Box-bisection for solving second-degree systems and the problem of clustering. ACM Trans. Math. Softw. 13, 2, 152-167. Google ScholarDigital Library
MORGAN, A. AND SOMMESE, A. 1987b. Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput. 24, 2 (Nov. 1987), 115-138. Google ScholarDigital Library
MORGAN, A. AND SOMMESE, A. 1987c. A homotopy for solving general polynomial systems that respects m-homogenous structures. Appl. Math. Comput. 24, 2 (Nov. 1987), 101-113. Google ScholarDigital Library
MORGAN, A. P. AND SOMMESE, A. J. 1989. Coefficient-parameter polynomial continuation. Appl. Math. Comput. 29, 2 (Jan. 1989), 123-160. Google ScholarDigital Library
MORGAN, A. P. AND WAMPLER, C.W. 1990. Solving a planar four-bar design problem using continuation. ASME J. Mech. Des. 112, 544-550.Google ScholarCross Ref
MORGAN, A. P., SOMMESE, A. J., AND WAMPLER, C.W. 1991. Computing singular solutions to nonlinear analytic systems. Numer. Math. 58, 669-684.Google ScholarDigital Library
MORGAN, A. P., SOMMESE, A. J., AND WAMPLER, C.W. 1992a. Computing singular solutions to polynomial systems. Adv. Appl. Math. 13, 3 (Sept. 1992), 305-327. Google ScholarDigital Library
MORGAN, A. P., SOMMESE, A. J., AND WAMPLER, C.W. 1992b. A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math. 63, 391-409.Google ScholarDigital Library
MORGAN, A. P., SOMMESE, A. J., AND WAMPLER, C.W. 1995. A product-decomposition bound for Bezout numbers. SIAM J. Numer. Anal. 32, 4 (Aug. 1995), 1308-1325. Google ScholarDigital Library
MORGAN, A. P., SOMMESE, A. J., AND WATSON, L. T. 1989. Finding all isolated solutions to polynomial systems using HOMPACK. ACM Trans. Math. Softw. 15, 2 (June 1989), 93-122. Google ScholarDigital Library
MOURRAIN, B. 1993. The 40 "generic" positions of a parallel robot. In Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation (ISSAC '93, Kiev, Ukraine, July 6-8, 1993), M. Bronstein, Ed. ACM Press, New York, NY, 173-182. Google ScholarDigital Library
MOURRAIN, B. 1996. The handbook of polynomial systems. Available via http://www.inria.fr/ saga/POL/index.html.Google Scholar
NAUHEIM, R. 1998. Systems of algebraic equations with bad reduction. J. Symb. Comput. 25, 5, 619-641. Google ScholarDigital Library
NELSEN, C. V. AND HODGKIN, B. C. 1981. Determination of magnitudes, directions, and locations of two independent dipoles in a circular conducting region from boundary potential measurements. IEEE Trans. Bio. Eng. 28, 12, 817-823.Google ScholarCross Ref
NOONBURG, V. W. 1989. A neural network modeled by an adaptive Lotka-Volterra system. SIAM J. Appl. Math. 49, 6 (Dec. 1989), 1779-1792. Google ScholarDigital Library
RAVI, M. S., ROSENTHAL, J., AND WANG, X. 1996. Dynamic pole placement assignment and Schubert calculus. SIAM J. Control Optim. 34, 3, 813-832. Google ScholarDigital Library
ROJAS, J. M. 1994. A convex geometric approach to counting the roots of a polynomial system. Theor. Comput. Sci. 133, 1 (Oct. 10, 1994), 105-140. Google ScholarDigital Library
ROJAS, J. M. 1997. Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert's tenth problem. In Selected papers of a conference on Foundations of computational mathematics (FoCM '97, Rio de Janeiro, Brazil, Jan. 1997), F. Cucker and M. Shub, Eds. Springer-Verlag, New York, NY, 369-381. Google ScholarDigital Library
ROJAS, J. M. 1999. Toric intersection theory for affine root counting. J. Pure Applied Alg. 136, 1 (Mar.), 67-100.Google ScholarCross Ref
ROJAS, J. M. AND WANG, X. 1996. Counting affine roots of polynomial systems via pointed Newton polytopes. J. Complexity 12, 2, 116-133. Google ScholarDigital Library
ROSENTHAL, g. AND SOTTILE, F. 1998. Some remarks on real and complex output feedback. Syst. Control Lett. 33, 2, 73-80. See http://www.nd.edu/-rosen/pole for a description of computational aspects of the paper. Google ScholarDigital Library
ROSENTHAL, J. AND WILLEMS, J. C. 1998. Open problems in the area of pole placement. In Open Problems in Mathematical Systems and Control Theory, V. D. Blondel, E. D. Sontag, M. Vidyasagar, and J. C. Willems, Eds. Communication and Control Engineering Series. Springer-Verlag, New York, NY, 181-191.Google Scholar
SCHRANS, S. AND TROOST, W. 1990. Generalized Virasoro constructions for SU(3). Nuc. Phy. B345, 2-3, 584-606.Google Scholar
SOSONKINA, M., WATSON, L. T., AND STEWART, D. E. 1996. A note on the end game in homotopy zero curve tracking. ACM Trans. Math. Softw. 22, 3 (Sept.), 281-287. Google ScholarDigital Library
SOTTILE, F. 1997. Enumerative geometry for real varieties. In Algebraic Geometry--Santa Cruz 1995: Part I of Proceedings of Symposia in Pure Mathematics, J. Koll r, R. Lazarsfeld, and D. R. Morrison, Eds. University of California at Santa Cruz, Santa Cruz, CA, 435-447.Google Scholar
SOTTILE, F. 1998. Real Schubert calculus: Polynomial systems and a conjecture of Shapiro and Shapiro. Tech. Rep. Preprint 1998-066. Mathematical Sciences Research Institute, Berkeley, CA. To appear in Experimental Mathematics.Google ScholarCross Ref
STEENKAMP, M. C. 1982. Die numeriese oplos van stelsels polinoomvergelykings. Tech. Rep. Nasionale Navorsingsinstituut vir Wiskundige Wetenskappe, Pretoria.Google Scholar
STROUD, A. H. AND SECREST, D. 1966. Gaussian Quadrature Formulas. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
STURMFELS, B. 1994. On the Newton polytope of the resultant. J. Algebraic Comb. 3, 2 (Apr. 1994), 207-236. Google ScholarDigital Library
STURMFELS, B. 1998. Polynomial equations and convex polytopes. Am. Math. Mon. 105, 10, 907-922.Google ScholarCross Ref
SWELDENS, W. 1994. The construction and application of wavelets in numerical analysis. Ph.D. Dissertation. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.Google Scholar
SYIEK, D. 1995. C vs Ada: Arguing performance religion. SIGADA Ada Lett. XV, 6 (Nov./Dec. 1995), 67-69. Google ScholarDigital Library
TRAVERSO, C. 1993. The PoSSo test suite examples. Available at http://www.inria.fr/saga/ POL/index.html.Google Scholar
VAN HENTENRYCK, P., MCALLESTER, D., AND KAPUR, D. 1997. Solving polynomial systems using a branch and prune approach. SIAM J. Numer. Anal. 34, 2, 797-827. Google ScholarDigital Library
VERSCHELDE, J. 1990. Oplossen van stelsels veeltermvergelijkingen met behulp van continueringsmethodes. Bachelor's Thesis. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.Google Scholar
VERSCHELDE, J. 1995. PHC and MVC: Two programs for solving polynomial systems by homotopy continuation. In Proceedings of the PoSSo Workshop on Software (Paris, France, Mar. 1-4), J. Faug re, J. Marchand, and R. Rioboo, Eds. 165-175.Google Scholar
VERSCHELDE, J. 1996. Homotopy continuation methods for solving polynomial systems. Ph.D. Dissertation. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.Google Scholar
VERSCHELDE, J. 1998. Numerical evidence for a conjecture in real algebraic geometry. Preprint 1998-064. Mathematical Sciences Research Institute, Berkeley, CA. To appear in Experimental Mathematics.Google Scholar
VERSCHELDE, J. AND COOLS, R. 1992. Nonlinear reduction for solving deficient polynomial systems by continuation methods. Numer. Math. 63, 2, 263-282.Google ScholarDigital Library
VERSCHELDE, J. AND COOLS, R. 1993a. An Ada workbench for homotopy continuation for solving polynomial systems. Ada Belg. Newslett. 2, 1, 23-40.Google Scholar
VERSCHELDE, J. AND COOLS, R. 1993b. Symbolic homotopy construction. Appl. Alg. Eng. Commun. Comput. 4, 169-183.Google ScholarDigital Library
VERSCHELDE, J. AND COOLS, R. 1994. Symmetric homotopy construction. J. Comput. Appl. Math. 50, 1-3 (May 20, 1994), 575-592. Google ScholarDigital Library
VERSCHELDE, J. AND COOLS, R. 1996. Polynomial homotopy continuation, a portable Ada software package. Ada Belg. Newslett. 4, 59-83.Google Scholar
VERSCHELDE, J. AND GATERMANN, K. 1995. Symmetric Newton polytopes for solving sparse polynomial systems. Adv. Appl. Math. 16, 1 (Mar. 1995), 95-127. Google ScholarDigital Library
VERSCHELDE, J. AND HAEGEMANS, A. 1993. The GBQ-algorithm for constructing start systems of homotopies for polynomial systems. SIAM J. Numer. Anal. 30, 2 (Apr. 1993), 583-594. Google ScholarDigital Library
VERSCHELDE, g., BECKERS, M., AND HAEGEMANS, A. 1991. A new start system for solving deficient polynomial systems using continuation. Appl. Math. Comput. 44, 3 (Aug. 1991), 225-239. Google ScholarDigital Library
VERSCHELDE, J., GATERMANN, K., AND COOLS, R. 1996. Mixed-volume computation by dynamic lifting applied to polynomial system solving. Discrete Comput. Geom. 16, 1, 69-112.Google ScholarDigital Library
VERSCHELDE, J., VERLINDEN, P., AND COOLS, R. 1994. Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SIAM J. Numer. Anal. 31, 3 (June 1994), 915-930. Google ScholarDigital Library
WALLACK, A., EMIRIS, I. Z., AND MANOCHA, D. 1998. MARS: a MAPLE/MATLAB/C resultantbased solver. In Proceedings of the 1998 international symposium on Symbolic and algebraic computation (ISSAC '98, Rostock, Germany, Aug. 13-15, 1998), V. Weispfenning and B. Trager, Eds. ACM Press, New York, NY, 244-251. Google ScholarDigital Library
WAMPLER, C.W. 1992. Bezout number calculations for multi-homogeneous polynomial systems. Appl. Math. Comput. 51, 2-3, 143-157.Google Scholar
WAMPLER, C.W. 1996. Isotropic coordinates, circularity and Bezout numbers: Planar kinematics from a new perspective. In Proceedings of the 1996 ASME Design Engineering Technical Conference (Irvine, CA, Aug. 18-22). ASME, New York, NY. Also available as GM Tech. Rep. R&D-8188.Google Scholar
WAMPLER, C. AND MORGAN, A. 1991. Solving the 6R inverse position problem using a generic-case solution methodology. Mech. Mach. Theory 26, 1, 91-106.Google ScholarCross Ref
WATSON, L. T 1986. Numerical linear algebra aspects of globally convergent homotopy methods. SIAM Rev. 28, 4 (Dec. 1986), 529-545. Google ScholarDigital Library
WATSON, L. T., BILLUPS, S. C., AND MORGAN, A. P. 1987. ALGORITHM 652: HOMPACK: A suite of codes for globally convergent homotopy algorithms. ACM Trans. Math. Softw. 13, 3 (Sept. 1987), 281-310. Google ScholarDigital Library
WATSON, L. T., SOSONKINA, M., MELVILLE, R. C., MORGAN, A. P., AND WALKER, H. F. 1997. HOMPACK90: A suite of Fortran 90 codes for globally convergent homotopy algorithms. ACM Trans. Math. Softw. 23, 4, 514-549. Google ScholarDigital Library
WISE, S., SOMMESE, A., AND WATSON, L. 1998. POLSYS PLP: A partitioned linear product homotopy code for solving polynomial systems of equations.Google Scholar
WRIGHT, A. H. 1985. Finding all solutions to a system of polynomial equations. Math. Comput. 44 (Jan. 1985), 125-133.Google Scholar

Index Terms

Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation
1. Mathematics of computing
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

On the Number of Flats Tangent to Convex Hypersurfaces in Random Position
Abstract
Motivated by questions in real enumerative geometry (Borcea et al., in Discrete Comput Geom 35(2):287–300, 2006; Bürgisser and Lerario, in J Reine Angew Math, 10.1515/crelle-2018-0009, 2018; Megyesi and Sottile, in Discrete Comput Geom 33(4):617–... $_{}_{_{}}^{}$ $_{}$ $_{}_{_{}}$ $_{}_{}_{_{}}$
$\begin{matrix} _{}_{}_{_{}}_{}_{}^{_{}} \frac{_{}_{}}{} \end{matrix}$
$_{}$ $_{}$ $_{}$ $_{}$ $_{}$ $^{}$
$\begin{matrix} \frac{_{}}{}_{} \end{matrix}$
$\begin{matrix} _{}_{}_{_{}}_{}^{_{}} \end{matrix}$
$_{}_{}$ $_{}_{}_{}_{}$
Read More
A subdivision-based algorithm for the sparse resultant

Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal ...
Read More
High probability analysis of the condition number of sparse polynomial systems
Algebraic and numerical algorithm

Let f := (f¹ ..... fⁿ) be a random polynomial system with fixed n-tuple of supports. Our main result is an upper bound on the probability that the condition number of f in a region U is larger than 1/ε. The bound depends on an integral of a differential ...
Read More

Comments

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 Article

Published in

ACM Transactions on Mathematical Software Volume 25, Issue 2
June 1999
148 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/317275
Issue’s Table of Contents

Copyright © 1999 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
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 1 June 1999
Published in toms Volume 25, Issue 2

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Badges
- Artifacts Available
- Artifacts Evaluated & Reusable
Author Tags
Bézout number
Bernshtein's theorem
Schubert calculus
enumerative geometry
homotopy continuation
mixed volume
polyhedral homotopy
polynomial systems
root count
start system
Qualifiers
- article
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 396
  Total Citations
  View Citations
- 1,637
  Total Downloads
- Downloads (Last 12 months)127
- Downloads (Last 6 weeks)23
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation

ACM Transactions on Mathematical Software

Abstract

Supplemental Material

Available for Download

References

Cited By

Index Terms

Recommendations

On the Number of Flats Tangent to Convex Hypersurfaces in Random Position

A subdivision-based algorithm for the sparse resultant

High probability analysis of the condition number of sparse polynomial systems