A Fast Algorithm for Computing the Truncated Resultant

Guillaume Moroz (1) , Éric Schost (2)

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
2 University of Waterloo [Waterloo]

Let P and Q be two polynomials in K[x, y] with degree at most d, where K is a field. Denoting by R ∈ 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.

Mots clés: half-GCD; power series; resultant

Domaines: Calcul formel [cs.SC]

Guillaume Moroz, Éric Schost. A Fast Algorithm for Computing the Truncated Resultant. ISSAC '16, Sergei A. Abramov; Eugene V. Zima, Jul 2016, Waterloo, Canada. pp.341-348, ⟨10.1145/2930889.2930931⟩. ⟨hal-01366386⟩