Suppose you would like to count the exact number of common roots (real or complex) of n polynomials in n variables. Classical algebraic geometry only gives loose upper bounds on this number. More recent methods, e.g, mixed volumes, give sharper upper bounds but can still overcount sometimes. One could, of course, resort to Grobner bases but this route is still too slow for many practical applications, e.g., inverse kinematics. So what to do?
We propose a new method, with great practical potential, based on the sparse resultant. The complexity of our algorithm is close to quadratic in the number of complex roots --- faster (at least asymptotically) than any previous algorithm.
(No prior knowledge of sparse resultants is assumed.)