Skip to Main content Skip to Navigation
Conference papers

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

Bruno Grenet 1 Daniel S. Roche 2 Pascal Giorgi 1
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02493066
Contributor : Pascal Giorgi <>
Submitted on : Tuesday, November 24, 2020 - 9:41:06 AM
Last modification on : Thursday, November 26, 2020 - 11:57:02 AM

File

preprint-v2.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Bruno Grenet, Daniel S. Roche, Pascal Giorgi. 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-02493066v3⟩

Share

Metrics

Record views

55

Files downloads

69