Most polynomial systems arising in practical applications are sparse, i.e.: only relatively few monomials appear with a nonzero coefficient. Therefore, bounds on the number of roots based on the degree structures may drastically overshoot the actual number of solutions. The performance of homotopy methods depends critically on the accuracy of these bounds, because the bounds determine the number of solution paths. Using a recursive formula to compute mixed volumes, David Bernstein outlined in his 1975 paper a deformation method to show that mixed volumes give sharp root counts, along with conditions on the system when the count is not sharp. HOM4PS/MixedVol, PHoM, and PHCpack provide implementations of the polyhedral homotopy methods introduced by Birkett Huber and Bernd Sturmfels in 1995. Several interesting numerical issues arise when applied to large systems.
IMA PostDoc Seminar, 31 October 2006.