Polynomials are ubiquitous in a variety of applications.
A relatively recent theory exploits their
sparse structure by associating a point configuration to each
polynomial system; however, it has so far mostly dealt with roots
having nonzero coordinates.
We shift attention to arbitrary affine roots,
and improve upon the
existing algorithms for counting them and computing them numerically.
The one existing approach is too expensive in practice because of
the usage of recursive liftings of the given point configuration.
Instead, we define a single lifting which yields the desired count
and defines a homotopy continuation for computing all solutions.
We enhance the numerical stability of the homotopy by establishing
lower bounds on the lifting values and prove that
they can be derived dynamically to obtain
the lowest possible values.
Our construction may be regarded as a generalization of the dynamic lifting algorithm for the computation
of mixed cells.
Keywords: Regular subdivision, dynamic lifting, stable mixed volume, polyhedral homotopy, affine root count, polynomial system.
Discrete Applied Mathematics 93(1): 21-32, 1999.