Solving polynomial systems numerically means computing approximations to all isolated solutions. Homotopy continuation methods provide paths to approximate solutions. The idea is to break up the original system into simpler problems. To solve the original system, the solutions of the simpler systems are deformed into the solutions of the original problem.
This paper presents optimal homotopies for three different classes of polynomial systems. Optimal means that for generic instances of the classes there are no diverging solution paths, whence the amount of computational work is linear in the number of solutions. In the next section we list the principal key words, definitions and main theorems for dense, sparse and determinantal polynomial systems. The proofs of these theorems follow from the correctness of the homotopies.
Path-following methods are standard numerical techniques ([3,4,5], [71], [123,125]) to achieve global convergence when solving nonlinear systems. For polynomial systems we can reach all isolated solutions. In the third section we describe the paradigm of Cheater's homotopy ([57], [59]) or coefficient-parameter polynomial continuation ([75], [76]). This paradigm allows to construct homotopies for which singularities only occur at the end of the paths. To deal with components of solutions we use an embedding method that leads to generic points on each component. This method is essential to numerical algebraic geometry [93].
From [48] we cite: ``Algebraic geometry studies the delicate balance between the geometrically plausible and the algebraically possible''. By a choice of coordinates we set up an algebraic formulation for a geometric problem that is then solved by automatic computations. While this approach is extremely powerful, we might get trapped into tedious wasted computations after loosing the original geometric meaning of the problem. In section four we stress the geometric intuition of homotopy methods. Compactifications and homogeneous coordinates provide us the tools to generate the numerically most favorable representations for the solutions to our problem. In section five we arrive at the heart of modern homotopy methods where we outline specific algorithms to implement the root counts2. The counting of the roots mirrors the resolution of a system in generic position that is used as starting point in the deformations.
Polyhedral methods occupy the central part of current research, as they are responsible for a computational breakthrough in numerical general-purpose solvers for polynomial systems. Section six is devoted to numerical software with an emphasis on the structure of the package PHC, developed by the author during the past decade. Another novel and exciting research development concerns the numerical Schubert calculus, which is one of the major new features in the second public release of PHC. The author has gathered more than one hundred polynomial systems that arose in various application fields. This collection serves as a test suite for software and a gallery to demonstrate the importance of polynomial systems to mathematical modelling. In section seven we sample some interesting cases.
The reference list contains a compilation of the most relevant technical contributions to polynomial homotopy continuation. Besides those we want to point at some other works in the literature that are of special interest. Some user-friendly introductions to algebraic geometry appeared in recent years: see [1], [27], [37], with computational aspects in [15] and [16]. As Newton polytopes have become extremely important, we recommend [130] and the handbook chapters [35]. See also [104] for the interplay between the combinatorics of polytopes and the (real) roots of polynomials. A recent survey that also covers polyhedral homotopies along with other polynomial continuation methods appeared in [64].