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

https://hal.archives-ouvertes.fr/hal-02476609
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

File

2001.11959.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

172

Files downloads

61