An interpolation algorithm for computing Dixon resultants (Q2109984)

Given a system of polynomial equations with parameters, this paper introduces a new algorithm for computing the monic square-free factors of its Dixon resultant R, without interpolating R. Obviously, the advantage of the algorithm over other known polynomial interpolation algorithms (see [\textit{M. Ben-Or} and \textit{P. Tiwari}, ``A deterministic algorithm for sparse multivariate polynomial interpolation'', in: Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC '88. New York, NY: Association for Computing Machinery (ACM). 301--309 (1988; \url{doi:10.1145/62212.62241}); \textit{R. Zippel}, Lect. Notes Comput. Sci. 72, 216--226 (1979; Zbl 0418.68040)]) is that the number of polynomial terms in the square-free factors to be interpolated is much less than in polynomial R. The algorithm uses sparse multivariate rational function interpolation to interpolate the coefficients of the factors in Q(Y) modulo primes and, also, Chinese remaindering and rational number reconstruction to recover the rational coefficients of the factors. The authors modify the sparse rational function interpolation algorithm of Cuyt and Lee to use Kronecker substitutions to combat the large prime and unlucky evaluation point problems that occurs when the adopted sparse polynomial algorithm in Cuyt and Lee's method is the Ben-Or/Tiwari sparse polynomial algorithm. The efficiency of the algorithm is shown in several tables through the paper and the interested reader can download the Maple and C codes from the website \url{https://www.cecm.sfu.ca/mmonagan/code/DixonR}. For the entire collection see [Zbl 07573785].