Fast in-place algorithms for polynomial operations: division, evaluation, interpolation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2020

Fast in-place algorithms for polynomial operations: division, evaluation, interpolation

Pascal Giorgi
Bruno Grenet

Abstract

We consider space-saving versions of several important operations on univariate polynomials, namely power series inversion and division, division with remainder, multi-point evaluation, and interpolation. Now-classical results show that such problems can be solved in (nearly) the same asymptotic time as fast polynomial multiplication. However, these reductions, even when applied to an in-place variant of fast polynomial multiplication, yield algorithms which require at least a linear amount of extra space for intermediate results. We demonstrate new in-place algorithms for the aforementioned polynomial computations which require only constant extra space and achieve the same asymptotic running time as their out-of-place counterparts. We also provide a precise complexity analysis so that all constants are made explicit, parameterized by the space usage of the underlying multiplication algorithms.
Fichier principal
Vignette du fichier
preprint-v2.pdf (293.92 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-02493066 , version 1 (27-02-2020)
lirmm-02493066 , version 2 (12-11-2020)
lirmm-02493066 , version 3 (24-11-2020)

Identifiers

Cite

Pascal Giorgi, Bruno Grenet, Daniel S. Roche. Fast in-place algorithms for polynomial operations: division, evaluation, interpolation. 45th International Symposium on Symbolic and Algebraic Computation (ISSAC), Jul 2020, Kalamata, Greece. pp.210-217, ⟨10.1145/3373207.3404061⟩. ⟨lirmm-02493066v2⟩
142 View
198 Download

Altmetric

Share

More