Efficient variable elimination using resultants
Tushar Saxena · 1997
A new method for eliminating variables from polynomial equations is proposed, analyzed, evaluated and applied. Problems from many applications involve computation of resultants -- polynomials obtained after eliminating variables from polynomials. Therefore effective elimination procedures require efficient methods to compute resultants, especially those exploiting sparsity which typically exists in most real-world applications. A new method for computing resultants is proposed. This method exploits the sparsity in the problem, despite being based on a classical formulation by Dixon. It also extends the Dixon formulation for bi-degree polynomials to compute resultants of most multivariate polynomial systems, while implicitly exploiting the sparse structure of the input polynomial system. Our work, for the first time, links the classical Dixon formulation to the modern line of sparsity analysis based on Newton polytopes. This link enables us to (i) devise an algorithm for directly inter...