An Interpolation algorithm for computing Dixon Resultants

Ayoola Jinadu, CECM, Simon Fraser Univeristy

Friday March 18th, 12:30pm, online.

Abstract:

Given a system of polynomial equations with parameters, we present a new Dixon resultant algorithm for computing its resultant. Our algorithm interpolates the square-free factors of the resultant one at a time from monic univariate polynomial images using sparse rational function interpolation. The sparse multivariate rational function algorithm of Cuyt and Lee is the adopted algorithm in this work. To overcome the large prime and unlucky evaluation point problems posed by using the Ben-Or/Tiwari sparse interpolation algorithm, we have modified Cuyt and Lee’s algorithm to use Kronecker substitutions and we have modified the Ben-Or/Tiwari sparse interpolation algorithm. We present timing results comparing hybrid Maple + C implementations of our Dixon resultant algorithm and Zippel’s algorithm with an implementation of the Gentleman & Johnson minor expansion method in Maple.