Essentially Optimal Sparse Polynomial Multiplication

Pascal Giorgi; Bruno Grenet; Armelle Perret du Cray

doi:10.48550/arxiv.2001.11959

Retour

Prépublication

Essentially Optimal Sparse Polynomial Multiplication

Pascal Giorgi, Bruno Grenet et Armelle Perret du Cray

arXiv.org

05/06/2020

DOI: https://doi.org/10.48550/arxiv.2001.11959

Résumé

Computer Science - Computational Complexity

Computer Science - Data Structures and Algorithms

Computer Science - Symbolic Computation

Proc. ISSAC'20, pp 202-209, ACM, 2020 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.

Indicateurs

1 Consultations de la notice

Détails

Titre: Essentially Optimal Sparse Polynomial Multiplication
Créateurs - sans rôle: Pascal Giorgi
Bruno Grenet
Armelle Perret du Cray
Détails de publication: arXiv.org
Identifiants: 99139238309311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Langue: English
Type de ressource: Preprint