16 citations · 59 across the 20 of their papers we have counts for
4 papers · 1 filter
Optimizing the half-gcd algorithm
Joris van der Hoeven
In this paper, we propose a carefully optimized "half-gcd" algorithm for polynomials. We achieve a constant speed-up with respect to previous work for the asymptotic time complexit…
Faster polynomial multiplication over finite fields
David Harvey, Joris van der Hoeven, Grégoire Lecerf
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n)…
Even faster integer multiplication
David Harvey, Joris van der Hoeven, Grégoire Lecerf
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coeffici…
Quasi-optimal multiplication of linear differential operators
Alexandre Benoit, Alin Bostan, Joris van der Hoeven
We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question r…