Abstract
In this chapter, we study two computational approaches to solve a system of polynomial equations. We contrast the symbolic power of Gröbner bases with the numerical efficiency of Polynomial Homotopy Continuation (PHC), providing a foundational overview for practical applications in science and engineering.
Introduction
At the heart of many scientific problems—from robotics and computer vision to chemical kinematics—lies a system of polynomial equations. Unlike linear systems, which are readily solvable via matrix algebra, polynomial systems present unique challenges. They may possess multiple isolated solutions, positive-dimensional components (solution "blobs"), or no solutions at all. This paper addresses the representation and computation of these solutions, focusing on "square systems" where the number of equations equals the number of variables, and exploring parametric systems where equations depend on external values.
Symbolic Methods: Gröbner Bases
The symbolic approach relies on the construction of Gröbner bases. This method transforms a complex system of equations into a "nicer" set that generates the same ideal. By employing a specific "Lexicographic" (dictionary) ordering of terms, one can perform variable elimination. This effectively reduces a multivariate system into a sequence of univariate polynomials, analogous to back-substitution in linear algebra.
A key result in this domain is the connection between the number of "standard monomials" in a Gröbner basis and the total number of solutions (counting multiplicities). However, symbolic computation is notoriously expensive, with worst-case complexity being doubly exponential, limiting its use for very large systems.
Numerical Methods: Polynomial Homotopy Continuation (PHC)
As an alternative to symbolic manipulation, Polynomial Homotopy Continuation (PHC) offers numerical efficiency. The process begins with a "start system" with known solutions (e.g., $x^n - 1 = 0$) and continuously deforms it into the "target system." By tracking solution paths using numerical ODE solvers and Newton’s method, one can find all regular isolated solutions.
The reliability of PHC rests on the concept of the discriminant. For parametric systems, the number of solutions remains constant as long as the parameters avoid this "bad" set. Furthermore, while Bézout’s Theorem provides a general upper bound on solutions based on total degree, the BKK Theorem offers tighter bounds for "sparse" systems by analyzing the geometry of Newton Polytopes, preventing the tracking of unnecessary paths.
Software and Implementation
The theoretical frameworks are implemented in several key software packages:
- Macaulay2: Utilized for symbolic calculations, including Gröbner basis construction and ideal saturation (a technique to remove unwanted solution components).
- HomotopyContinuation.jl: A Julia-based package designed for efficient numerical path tracking and certification.
Conclusion
While symbolic methods provide exact algebraic insights, numerical methods offer scalability for complex engineering problems. Recent advancements in "numerical certification" allow researchers to provide computer-generated proofs that numerical approximations are close to true solutions, bridging the gap between the two paradigms. Future work continues to address the challenges of positive-dimensional components and numerical stability near discriminants.
Summary updated