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

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

Bruno Grenet
Pascal Giorgi

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 (211.96 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

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

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

Altmetric

Share

Gmail Facebook X LinkedIn More