A fast algorithm for computing the truncated resultant

DOI10.1145/2930889.2930931MaRDI QIDQ2985846zbMATH OpenOpenAlexFDO

Authors Guillaume Moroz, Éric Schost

Publication date 10 May 2017

Published in Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.04259

zbMATH Keywords

half-GCDpower seriesresultant

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15) Symbolic computation and algebraic computation (68W30)

Abstract: Let P and Q be two polynomials in K[x, y] with degree at most d, where K is a field. Denoting by R $in$ K[x] the resultant of P and Q with respect to y, we present an algorithm to compute R mod x^k in O~(kd) arithmetic operations in K, where the O~ notation indicates that we omit polylogarithmic factors. This is an improvement over state-of-the-art algorithms that require to compute R in O~(d^3) operations before computing its first k coefficients.

Recommendations

• On computing the resultant of generic bivariate polynomials
• Probabilistic algorithms for computing resultants
• scientific article; zbMATH DE number 1253989
• Fast computation of generic bivariate resultants
• Fast computation of the Bézout and Dixon resultant matrices

Cited in

(8)

• Computing the equisingularity type of a pseudo-irreducible polynomial
• Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one
• Computing Puiseux series: a fast divide and conquer algorithm
• scientific article; zbMATH DE number 1253989 (Why is no real title available?)
• scientific article; zbMATH DE number 1279832 (Why is no real title available?)
• Algorithm for computing the truncation of the discriminant of a polynomial
• High-order lifting for polynomial Sylvester matrices
• Plane curve germs and contact factorization

This page was built for publication: A fast algorithm for computing the truncated resultant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985846)