Solving Polynomial Systems Equation by Equation

Andrew J. Sommese, Jan Verschelde, and Charles W. Wampler

Abstract:

By a numerical continuation method called a diagonal homotopy, one can compute the intersection of two irreducible positive dimensional solution sets of polynomial systems. This paper proposes to use this diagonal homotopy as the key step in a procedure to intersect general solution sets that are not necessarily irreducible or even equidimensional. Of particular interest is the special case where one of the sets is defined by a single polynomial equation. This leads to an algorithm for finding a numerical representation of the solution set of a system of polynomial equations introducing the equations one by one. Preliminary computational experiments show this approach can exploit the special structure of a polynomial system, which improves the performance of the path following algorithms.

2000 Mathematics Subject Classification. Primary 65H10; Secondary 13P05, 14Q99, 68W30.

Key words and phrases. Algebraic set, components of solutions, diagonal homotopy, embedding, equation-by-equation solver, generic point, homotopy continuation, irreducible component, numerical irreducible decomposition, numerical algebraic geometry, path following, polynomial system, witness point, witness set.