A practical method for the sparse resultant
Ioannis Z. Emiris, John Canny · 1993
We propose an efficient method for computing the resultant, of a sparse polynomial system of n + 1 equations in n unknowns.Our approach carries over from [(UE93] and constructs a matrix whose determinant is a nonzero multiple of the resultant, and from which the latter is easily extracted.For certain classes of syskms, it attains optimality by expressing the resultant, as a sillgle determinant.An illll>lenlelltatioll of the algorithm is described and empirical results presented and conlpared with those from [CE93] and [SZ].In addition, the important subproblem of computiug Mixed [Tolumes is examined and an efficient algorithm is inlplemeuted.Dixon ~esultant, of a perturbed system leads to an algorit,hln that terminates successfully in about 30 minutes, while all major Clrobner bases methods seem to run out of memory after running for a few days, even }vhen wor]iing on a homomorphic image of the problem over a finite field [MC92aj.In general, Grobner bases algorit)hlns can also exploit, sparseness; yet, when a sparse resultant, is known, the solution is much faster, as seen iu these applications.There exist some classes of problems, such as the kinematics of mechanisms and the generalized kinematics problem with ods aw expected 183 constraints, for which sparse methto be very efficient.So, ideally, we would like to have a sparse resultant for every problem, which calls for a general algorithm to construct, sparse resultants.The first efficient, algorithm was proposed in [CE93], while here we take a different, tack at