Skip to Main content Skip to Navigation
Conference papers

Essentially optimal sparse polynomial multiplication

Pascal Giorgi 1 Bruno Grenet 1 Armelle Perret Du Cray 1
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of characteristic zero or larger than the degree. We mainly rely on sparse interpolation and on a new algorithm for verifying a sparse product that has also a quasi-linear time complexity. Using Kronecker substitution techniques we extend our result to the multivariate case.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Armelle Perret Du Cray <>
Submitted on : Wednesday, May 13, 2020 - 2:27:31 PM
Last modification on : Thursday, September 3, 2020 - 4:46:32 AM


Files produced by the author(s)



Pascal Giorgi, Bruno Grenet, Armelle Perret Du Cray. Essentially optimal sparse polynomial multiplication. ISSAC: International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. pp.202-209, ⟨10.1145/3373207.3404026⟩. ⟨hal-02476609v1⟩



Record views


Files downloads