An interpolation algorithm for computing Dixon resultants
type: Item
instance of: scholarly article
title: An interpolation algorithm for computing Dixon resultants
DOI: 10.1007/978-3-031-14788-3_11
author: Ayoola Jinadu
author: Michael Monagan
publication date: 2022-12-21T00:00:00Z
review text: 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].
reviewed by: Gema Maria Diaz Toca
Mathematics Subject Classification ID: 13P05
Mathematics Subject Classification ID: 13P15
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 7635699
zbMATH Keywords: Dixon resultant
zbMATH Keywords: parametric polynomial systems
zbMATH Keywords: resultant
zbMATH Keywords: sparse rational function interpolation
zbMATH Keywords: Kronecker substitution
describes a project that uses: POLY
describes a project that uses: Dixon-EDF
describes a project that uses: Maple
MaRDI profile type: Publication
full work available at URL: 978-3-031-14788-3 11
OpenAlex ID: W4300221964
cites work: The Berlekamp-Massey algorithm revisited
cites work: Q4660683
cites work: Sparse interpolation of multivariate rational functions
cites work: The Evaluation of Determinants by Expansion by Minors and the General Problem of Substitution
cites work: Modern computer algebra
cites work: A Fast Parallel Sparse Polynomial GCD Algorithm
cites work: Q4226953
cites work: Q4234291
cites work: Q4227295
cites work: Fast rational function reconstruction
cites work: Dixon-EDF: The Premier Method for Solution of Parametric Polynomial Systems
cites work: Resultants, implicit parameterizations, and intersections of surfaces
cites work: Maximal quotient rational reconstruction
cites work: The Design of Maple's Sum-of-Products and POLY Data Structures for Representing Mathematical Objects
cites work: Improved Division by Invariant Integers
cites work: Complexity of constructing Dixon resultant matrix
cites work: An extended fast algorithm for constructing the Dixon resultant matrix
cites work: Q3851616
cites work: Interpolating polynomials from their values
description: scientific article; zbMATH DE number 7635699