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

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.

REFERENCES

• 1: 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.
• 2: 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.
• 3: Jörgen Backelin , Ralf Fröberg, How we proved that there are exactly 924 cyclic 7-roots, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.103-111, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120708]
• 4: 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.
• 5: BERNSHTEIN, D. N. 1975. The number of roots of a system of equations. Func. Anal. Apps. 9, 3, 183-185.
• 6: BINI, D. AND MOURRAIN, B. 1998. Polynomial test suite, http://www-sop.inria.fr/saga/POL/.
• 7: Göran Björck , Ralf Fröberg, A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots, Journal of Symbolic Computation, v.12 n.3, p.329-336, Sept. 1991 [doi>10.1016/S0747-7171(08)80153-8]
• 8: 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.
• 9: Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: W. Boege , R. Gebauer , H. Kredel, Some examples for solving systems of algebraic equations by calculating Groebner, Journal of Symbolic Computation, v.2 n.1, p.83-98, March 1986 [doi>10.1006/jsco.1996.0042]
• 11: BOON, S. 1992. Solving systems of equations. Sci. Math. Num-Analysis. Newsgroup Article 3529.
• 12: John Canny , J. Maurice Rojas, An optimal condition for determining the exact number of roots of a polynomial system, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.96-102, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120707]
• 13: Moody T. Chu , T. Y. Li , Tim Sauer, Homotopy method for general &lgr;-matrix problems, SIAM Journal on Matrix Analysis and Applications, v.9 n.4, p.528-536, Oct. 1988 [doi>10.1137/0609043]
• 14: COHN, H. AND DEUTSCH, g. 1988. An explicit modular equation in two variables for Q{sqrt(3)}. Math. Comput. 50, 557-568.
• 15: Cox, D., LITTLE, J., AND O'SHEA, D. 1998. Using Algebraic Geometry. Springer Graduate Texts in Mathematics, vol. 185. Springer-Verlag, New York, NY.
• 16: Ioannis Zacharias Emiris, Sparse elimination and applications in kinematics, University of California at Berkeley, Berkeley, CA, 1994
• 17: 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.
• 18: 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.
• 19: Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
• 20: Ioannis Z. Emiris , Jan Verschelde, How to count efficiently all affine roots of a polynomial system, Discrete Applied Mathematics, v.93 n.1, p.21-32, April 15, 1999 [doi>10.1016/S0166-218X(99)00003-7]
• 21: A. Galligo , C. Traverso, Practical determination of the dimension of an algebraic variety, Proceedings of the third conference on Computers and mathematics, p.46-52, May 1989, Boston, Massachusetts, United States
• 22: Tangan Gao , T. Y. Li , Xiaoshen Wang, Finding all isolated zeros of polynomial systems in Cn via stable mixed volumes, Journal of Symbolic Computation, v.28 n.1-2, p.187-211, July/Aug. 1999 [doi>10.1006/jsco.1998.0272]
• 23: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 24: K. Gatemann, Symbolic solution polynomial equation systems with symmetry, Proceedings of the international symposium on Symbolic and algebraic computation, p.112-119, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96907]
• 25: GEL'FAND, I. M., KAPRANOV, M. M., AND ZELEVINSKY, A.V. 1994. Discriminants, Resultants and Multidimensional Determinants. Birkh user Boston Inc., Cambridge, MA.
• 26: GIORDANO, T. 1996. Impl mention distribu e du calcul du volume mixte. Master's Thesis. University of Nice, Sophia-Antipolis, France.
• 27: S. Harimoto , Layne T. Watson, The Granularity of Homotopy Algorithms for Polynomial Systems of Equations, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.115-120, December 01-04, 1987
• 28: HUBER, B. 1995. Pelican manual. Availabe via http://www.mrsi.org/people/members/birk.
• 29: HUBER, B. T. 1996. Solving sparse polynomial systems. Ph.D. Dissertation. Cornell University, Ithaca, NY. Available at http://www.msri.org/people/members/birk.
• 30: Birkett Huber , Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation, v.64 n.212, p.1541-1555, Oct. 1995 [doi>10.2307/2153370]
• 31: HUBER, B. AND STURMFELS, B. 1997. Bernstein's theorem in affine space. Discrete Comput. Geom. 17, 2, 137-141.
• 32: HUBER, B. AND VERSCHELDE, J. 1998. Polyhedral end games for polynomial continuation. Num. Alg. 18, 1, 91-108.
• 33: Birkett Huber , Frank Sottile , Bernd Sturmfels, Numerical Schubert calculus, Journal of Symbolic Computation, v.26 n.6, p.767-788, Dec. 1998 [doi>10.1006/jsco.1998.0239]
• 34: KHOVANSKII, A. 1991. Fewnomials. Translations of Mathematical Monographs, vol. 88. American Mathematical Society, Boston, MA.
• 35: KLEIMAN, S. AND LAKSOV, D. 1972. Schubert calculus. Am. Math. Mon. 79, 10, 1061-1082.
• 36: KUSHNIRENKO, A. 1976. Newton Polytopes and the B zout Theorem. Func. Anal. Apps. 10, 3, 233-235.
• 37: LI, T.-Y. 1987. Solving polynomial systems. Math. Intell. 9, 3, 33-39.
• 38: LI, T.-Y. 1997. Numerical solutions of multivariate polynomial systems by homotopy continuation methods. Act. Numer. 6, 399-436.
• 39: T. Y. Li , T. Sauer, Regularity results for solving systems of polynomials by homotopy method, Numerische Mathematik, v.50 n.3, p.283-289, Jan. 1987 [doi>10.1007/BF01390706]
• 40: 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.
• 41: T. Y. Li , Xiaoshen Wang, Nonlinear homotopies for solving deficient polynomial systems with parameters, SIAM Journal on Numerical Analysis, v.29 n.4, p.1104-1118, Aug. 1992 [doi>10.1137/0729067]
• 42: T. Y. Li , Xiaoshen Wang, The BKK root count in Cn, Mathematics of Computation, v.65 n.216, p.1477-1484, Oct. 1996 [doi>10.1090/S0025-5718-96-00778-8]
• 43: Tien-Yien Li , Tim Sauer , James A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM Journal on Numerical Analysis, v.24 n.2, p.435-451, April 1987 [doi>10.1137/0724032]
• 44: T. Y. Li , Tim Sauer , James A. Yorke, The random product homotopy and deficient polynomial systems, Numerische Mathematik, v.51 n.5, p.481-500, October 1, 1987 [doi>10.1007/BF01400351]
• 45: T. Y. Li , T. Sauer , J. A. Yorke, The cheater's homotopy: an efficient procedure for solving systems of polynomial equations, SIAM Journal on Numerical Analysis, v.26 n.5, p.1241-1251, Oct. 1989 [doi>10.1137/0726069]
• 46: 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.
• 47: MALAJOVICH, G. 1996. pss 2.beta, polynomial system solver. (Software). Available at http://www.labma.ufrj.br:80/gregorio.
• 48: THE FRISCO CONSORTIUM. 1996. FRISCO--A framework for integrated symbolic/numeric computation. Available at http://www.nag.co.uk/projects/FRISCO.html.
• 49: THE PISA TEAM OF PoSSo. 1993. PoSSo home page. http://janet.dm.unipi.it/.
• 50: Keith Meintjes , Alexander P. Morgan, Chemical equilibrium systems as numerical test problems, ACM Transactions on Mathematical Software (TOMS), v.16 n.2, p.143-151, June 1990 [doi>10.1145/78928.78930]
• 51: MOORE, R. E. AND JONES, S.T. 1977. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14, 6, 1051-1065.
• 52: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 53: MORGAN, A. P. 1987. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall, Inc., Upper Saddle River, NJ.
• 54: Alexander Morgan , Vadim Shapiro, Box-bisection for solving second-degree systems and the problem of clustering, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.152-167, June 1987 [doi>10.1145/328512.328521]
• 55: Alexander Morgan , Andrew Sommese, Computing all solutions to polynomial systems using homotopy continuation, Applied Mathematics and Computation, v.24 n.2, p.115-138, Nov. 1987 [doi>10.1016/0096-3003(87)90064-6]
• 56: Alexander Morgan , Andrew Sommese, A homotopy for solving general polynomial systems that respects m-homogenous structures, Applied Mathematics and Computation, v.24 n.2, p.101-113, Nov. 1987 [doi>10.1016/0096-3003(87)90063-4]
• 57: Alexander P. Morgan , Andrew J. Sommese, Coefficient-parameter polynomial continuation, Applied Mathematics and Computation, v.29 n.2, p.123-160, Jan. 1989 [doi>10.1016/0096-3003(89)90099-4]
• 58: MORGAN, A. P. AND WAMPLER, C.W. 1990. Solving a planar four-bar design problem using continuation. ASME J. Mech. Des. 112, 544-550.
• 59: MORGAN, A. P., SOMMESE, A. J., AND WAMPLER, C.W. 1991. Computing singular solutions to nonlinear analytic systems. Numer. Math. 58, 669-684.
• 60: Alexander P. Morgan , Andrew J. Sommese , Charles W. Wampler, Computing singular solutions to polynomial systems, Advances in Applied Mathematics, v.13 n.3, p.305-327, Sept. 1992 [doi>10.1016/0196-8858(92)90014-N]
• 61: 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.
• 62: Alexander P. Morgan , Andrew J. Sommese , Charles W. Wampler, A product-decomposition bound for Bezout numbers, SIAM Journal on Numerical Analysis, v.32 n.4, p.1308-1325, Aug. 1995 [doi>10.1137/0732061]
• 63: Alexander P. Morgan , Andrew J. Sommese , Layne T. Watson, Finding all isolated solutions to polynomial systems using HOMPACK, ACM Transactions on Mathematical Software (TOMS), v.15 n.2, p.93-122, June 1989 [doi>10.1145/63522.64124]
• 64: B. Mourrain, The 40 “generic” positions of a parallel robot, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.173-182, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164120]
• 65: MOURRAIN, B. 1996. The handbook of polynomial systems. Available via http://www.inria.fr/ saga/POL/index.html.
• 66: Raphael Nauheim, Systems of algebraic equations with bad reduction, Journal of Symbolic Computation, v.25 n.5, p.619-641, May 1998 [doi>10.1006/jsco.1997.0191]
• 67: 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.
• 68: V. W. Noonburg, A neural network modeled by an adaptive Lotka-Volterra system, SIAM Journal on Applied Mathematics, v.49 n.6, p.1779-1792, Dec. 1989 [doi>10.1137/0149109]
• 69: M. S. Ravi , Joachim Rosenthal , Xiaochang Wang, Dynamic Pole Assignment and Schubert Calculus, SIAM Journal on Control and Optimization, v.34 n.3, p.813-832, May 1996 [doi>10.1137/S036301299325270X]
• 70: J. Maurice Rojas, A convex geometric approach to counting the roots of a polynomial system, Theoretical Computer Science, v.133 n.1, p.105-140, Oct. 10, 1994
• 71: J. Maurice Rojas, Toric laminations, sparse generalized characteristic polynomials, and a refinement of Hilbert's tenth problem, Selected papers of a conference on Foundations of computational mathematics, p.369-381, September 1997, Rio de Janeiro, Brazil
• 72: ROJAS, J. M. 1999. Toric intersection theory for affine root counting. J. Pure Applied Alg. 136, 1 (Mar.), 67-100.
• 73: J. Maurice Rojas , Xiaoshen Wang, Counting affine roots of polynomial systems via pointed Newton polytopes, Journal of Complexity, v.12 n.2, p.116-133, June 1996 [doi>10.1006/jcom.1996.0009]
• 74: Joachim Rosenthal , Frank Sottile, Some remarks on real and complex output feedback, Systems & Control Letters, v.33 n.2, p.73-80, Feb. 1998 [doi>10.1016/S0167-6911(97)00122-9]
• 75: 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.
• 76: SCHRANS, S. AND TROOST, W. 1990. Generalized Virasoro constructions for SU(3). Nuc. Phy. B345, 2-3, 584-606.
• 77: Maria Sosonkina , Layne T. Watson , David E. Stewart, Note on the end game in homotopy zero curve tracking, ACM Transactions on Mathematical Software (TOMS), v.22 n.3, p.281-287, Sept. 1996 [doi>10.1145/232826.232843]
• 78: 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.
• 79: 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.
• 80: STEENKAMP, M. C. 1982. Die numeriese oplos van stelsels polinoomvergelykings. Tech. Rep. Nasionale Navorsingsinstituut vir Wiskundige Wetenskappe, Pretoria.
• 81: STROUD, A. H. AND SECREST, D. 1966. Gaussian Quadrature Formulas. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Englewood Cliffs, NJ.
• 82: Bernd Sturmfels, On the Newton Polytope of the Resultant, Journal of Algebraic Combinatorics: An International Journal, v.3 n.2, p.207-236, April 1994 [doi>10.1023/A:1022497624378]
• 83: STURMFELS, B. 1998. Polynomial equations and convex polytopes. Am. Math. Mon. 105, 10, 907-922.
• 84: SWELDENS, W. 1994. The construction and application of wavelets in numerical analysis. Ph.D. Dissertation. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.
• 85: David Syiek, C vs Ada: arguing performance religion, ACM SIGAda Ada Letters, v.XV n.6, p.67-69, Nov./Dec. 1995 [doi>10.1145/216578.216583]
• 86: TRAVERSO, C. 1993. The PoSSo test suite examples. Available at http://www.inria.fr/saga/ POL/index.html.
• 87: Pascal Van Hentenryck , David McAllester , Deepak Kapur, Solving Polynomial Systems Using a Branch and Prune Approach, SIAM Journal on Numerical Analysis, v.34 n.2, p.797-827, April. 1997 [doi>10.1137/S0036142995281504]
• 88: VERSCHELDE, J. 1990. Oplossen van stelsels veeltermvergelijkingen met behulp van continueringsmethodes. Bachelor's Thesis.. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.
• 89: 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.
• 90: VERSCHELDE, J. 1996. Homotopy continuation methods for solving polynomial systems. Ph.D. Dissertation. Department of Computer Science, Katholieke Universiteit Leuven, Leuven, Belgium.
• 91: 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.
• 92: VERSCHELDE, J. AND COOLS, R. 1992. Nonlinear reduction for solving deficient polynomial systems by continuation methods. Numer. Math. 63, 2, 263-282.
• 93: VERSCHELDE, J. AND COOLS, R. 1993a. An Ada workbench for homotopy continuation for solving polynomial systems. Ada Belg. Newslett. 2, 1, 23-40.
• 94: VERSCHELDE, J. AND COOLS, R. 1993b. Symbolic homotopy construction. Appl. Alg. Eng. Commun. Comput. 4, 169-183.
• 95: Jan Verschelde , Ronald Cools, Symmetric homotopy construction, Journal of Computational and Applied Mathematics, v.50 n.1-3, p.575-592, May 20, 1994
• 96: VERSCHELDE, J. AND COOLS, R. 1996. Polynomial homotopy continuation, a portable Ada software package. Ada Belg. Newslett. 4, 59-83.
• 97: Jan Verschelde , Karin Gatermann, Symmetric Newton polytopes for solving sparse polynomial systems, Advances in Applied Mathematics, v.16 n.1, p.95-127, March 1995 [doi>10.1006/aama.1995.1005]
• 98: Jan Verschelde , Ann Haegemans, The GBQ-algorithm for constructing start systems of homotopies for polynomial systems, SIAM Journal on Numerical Analysis, v.30 n.2, p.583-594, April 1993 [doi>10.1137/0730028]
• 99: Jan Verschelde , Marc Beckers , Ann Haegemans, A new start system for solving deficient polynomial systems using continuation, Applied Mathematics and Computation, v.44 n.3, p.225-239, Aug. 1991 [doi>10.1016/0096-3003(91)90059-V]
• 100: 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.
• 101: Jan Verschelde , Pierre Verlinden , Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM Journal on Numerical Analysis, v.31 n.3, p.915-930, June 1994 [doi>10.1137/0731049]
• 102: Aaron Wallack , Ioannis Z. Emiris , Dinesh Manocha, MARS: a MAPLE/MATLAB/C resultant-based solver, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.244-251, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281626]
• 103: WAMPLER, C.W. 1992. Bezout number calculations for multi-homogeneous polynomial systems. Appl. Math. Comput. 51, 2-3, 143-157.
• 104: 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.
• 105: 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.
• 106: Layne T Watson, Numerical linear algebra aspects of globally convergent homotopy methods, SIAM Review, v.28 n.4, p.529-545, Dec. 1986 [doi>10.1137/1028157]
• 107: Layne T. Watson , Stephen C. Billups , Alexander P. Morgan, ALGORITHM 652: HOMPACK: a suite of codes for globally convergent homotopy algorithms, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.281-310, Sept. 1987 [doi>10.1145/29380.214343]
• 108: Layne T. Watson , Maria Sosonkina , Robert C. Melville , Alexander P. Morgan , Homer F. Walker, Algorithm 777: HOMPACK90: a suite of Fortran 90 codes for globally convergent homotopy algorithms, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.514-549, Dec. 1997 [doi>10.1145/279232.279235]
• 109: WISE, S., SOMMESE, A., AND WATSON, L. 1998. POLSYS PLP: A partitioned linear product homotopy code for solving polynomial systems of equations.
• 110: WRIGHT, A. H. 1985. Finding all solutions to a system of polynomial equations. Math. Comput. 44 (Jan. 1985), 125-133.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Ada

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations; Polynomials, methods for
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Theory

Keywords:
Bézout number, Bernshtein's theorem, Schubert calculus, enumerative geometry, homotopy continuation, mixed volume, polyhedral homotopy, polynomial systems, root count, start system