Approximating all isolated solutions to polynomial systems using homotopy continuation

Abstract:

Homotopy continuation methods operate in two stages. First, we define a homotopy which is family of polynomial systems connecting the system we want to solve with a system of similar structure whose solutions are known, or easier to compute. Second, numerical continuation methods are applied to trace the solution paths defined by the homotopy. Since the performance of the homotopy is determined by the number of paths which need to be traced, exponential speedups are often obtained by exploiting multi-homogeneous or sparse structures. To overcome numerical difficulties during path following, we scale the coefficients, compute in projective space, and apply endgames.

First lecture at RAAG Summer School on Computer Tools for Real Algebraic Geometry, Monday 30 June 2003, Rennes, France.