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
Contributor : Pascal Giorgi Connect in order to contact the contributor
Submitted on : Tuesday, November 24, 2020 - 9:41:06 AM
Last modification on : Friday, August 5, 2022 - 3:02:58 PM


Files produced by the author(s)




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⟩



Record views


Files downloads