In this paper we outline an algorithmic approach to compute Puiseux series expansions for algebraic sets. The series expansions originate at the intersection of the algebraic set with as many coordinate planes as the dimension of the algebraic set. Our approach starts with a polyhedral method to compute cones of normal vectors to the Newton polytopes of the given polynomial system that defines the algebraic set. If as many vectors in the cone as the dimension of the algebraic set define an initial form system that has isolated solutions, then those vectors are potential tropisms for the initial term of the Puiseux series expansion. Our preliminary methods produce exact representations for solution sets of the cyclic n-roots problem, for n = m2, corresponding to a result of Backelin.

We present a new numerical homotopy continuation algorithm for finding all solutions to Schubert problems on Grassmannians. This Littlewood-Richardson homotopy is based on Vakil's geometric proof of the Littlewood-Richardson rule. Its start solutions are given by linear equations and they are tracked through a sequence of homotopies encoded by certain checker configurations to find the solutions to a given Schubert problem. For generic Schubert problems the number of paths tracked is optimal. The Littlewood-Richardson homotopy algorithm is implemented using the path trackers of the software package PHCpack.

Two ideas are combined to construct a hybrid symbolic-numeric differential-elimination method for identifying and including missing constraints arising in differential systems. First we exploit the fact that a system once differentiated becomes linear in its highest derivatives. Then we apply diagonal homotopies to incrementally process new constraints, one at a time. The method is illustrated on several examples, combining symbolic differential elimination (using rifsimp) with numerical homotopy continuation (using phc).

In a recent joint work with Andrew Sommese and Charles Wampler, numerical homotopy continuation methods have been developed to deal with positive dimensional solution sets of polynomial systems. As solving polynomial systems is such a fundamental problem, connections with recent research in symbolic computation are not hard to find. We will address two such connections.One part of the numerical output of our methods consists of a "membership test" used to determine whether a point lies on apositive dimensional solution component. While Grobner bases provide an exact answer to the ideal membership test, geometrical results can be obtained at a lower complexity, as shown by Marc Giusti and Joos Heintz [6]. The recent work of Gregoire Lecerf [7, 9] implements an irreducible decomposition in a symbolic manner.The factorization of multivariate polynomials with approximate coefficients was posed as an open problem in symbolic computation by Erich Kaltofen [8]. Providing a certificate for a numerical factorization by means of the linear trace is related to ideas of André Galligo and David Rupprecht [3, 4], which also appears in the works of Tateaki Sasaki [10] and collaborators. See also [1, 2] and [5].

Many applications modeled by polynomial systems have positive dimensional solution components (e.g., the path synthesis problems for four-bar mechanisms) that are challenging to compute numerically by homotopy continuation methods. A procedure of A. Sommese and C. Wampler consists in slicing the components with linear subspaces in general position to obtain generic points of the components as the isolated solutions of an auxiliary system. Since this requires the solution of a number of larger overdetermined systems, the procedure is computationally expensive and also wasteful because many solution paths diverge. In this article an embedding of the original polynomial system is presented, which leads to a sequence of homotopies, with solution paths leading to generic points of all components as the isolated solutions of an auxiliary system. The new procedure significantly reduces the number of paths to solutions that need to be followed. This approach has been implemented and applied to various polynomial systems, such as the cyclic n -roots problem.

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.