Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Generic reductions for in-place polynomial multiplication

Pascal Giorgi 1 Bruno Grenet 1 Daniel S. Roche 2 
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The polynomial multiplication problem has attracted considerable attention since the early days of computer algebra, and several algorithms have been designed to achieve the best possible time complexity. More recently, efforts have been made to improve the space complexity, developing modified versions of a few specific algorithms to use no extra space while keeping the same asymptotic running time. In this work, we broaden the scope in two regards. First, we ask whether an arbitrary multiplication algorithm can be performed in-place generically. Second, we consider two important variants which produce only part of the result (and hence have less space to work with), the so-called middle and short products, and ask whether these operations can also be performed in-place. To answer both questions in (mostly) the affirmative, we provide a series of reductions starting with any linear-space multiplication algorithm. For full and short product algorithms these reductions yield in-place versions with the same asymptotic time complexity as the out-of-place version. For the middle product, the reduction incurs an extra logarithmic factor in the time complexity only when the algorithm is quasi-linear.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02003089
Contributor : Pascal Giorgi Connect in order to contact the contributor
Submitted on : Wednesday, February 6, 2019 - 10:39:40 AM
Last modification on : Friday, August 5, 2022 - 3:02:58 PM
Long-term archiving on: : Tuesday, May 7, 2019 - 12:58:05 PM

Files

issac-report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02003089, version 1
  • ARXIV : 1902.02967

Citation

Pascal Giorgi, Bruno Grenet, Daniel S. Roche. Generic reductions for in-place polynomial multiplication. 2019. ⟨lirmm-02003089v1⟩

Share

Metrics

Record views

328

Files downloads

247