An interpolation algorithm for computing Dixon resultants
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].
- A fast parallel sparse polynomial GCD algorithm
- An extended fast algorithm for constructing the Dixon resultant matrix
- Complexity of constructing Dixon resultant matrix
- Dixon-EDF: the premier method for solution of parametric polynomial systems
- Fast rational function reconstruction
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 1253976 (Why is no real title available?)
- scientific article; zbMATH DE number 1254250 (Why is no real title available?)
- scientific article; zbMATH DE number 1263399 (Why is no real title available?)
- scientific article; zbMATH DE number 2151215 (Why is no real title available?)
- Improved Division by Invariant Integers
- Interpolating polynomials from their values
- Maximal quotient rational reconstruction
- Modern computer algebra
- Resultants, implicit parameterizations, and intersections of surfaces
- Sparse interpolation of multivariate rational functions
- The Berlekamp-Massey algorithm revisited
- The Design of Maple's Sum-of-Products and POLY Data Structures for Representing Mathematical Objects
- The Evaluation of Determinants by Expansion by Minors and the General Problem of Substitution
- Heuristics to sift extraneous factors in Dixon resultants
- Computing Dixon polynomial via interpolation algorithms
- scientific article; zbMATH DE number 2058003 (Why is no real title available?)
- Computing the Dixon resultant with the Maple package DR
- A new interpolation algorithm for computing dixon resultants
- Solving Parametric Linear Systems Using Sparse Rational Function Interpolation
This page was built for publication: An interpolation algorithm for computing Dixon resultants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109984)
