Skip to Main content Skip to Navigation
Journal articles

A simple and fast online power series multiplication and its analysis

Romain Lebreton 1 Éric Schost 2
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper focus on online (or relaxed) algorithms for the multiplication of power series over a field and their analysis. We propose a new online algorithm for the multiplication using middle and short products of polynomials as building blocks, and we give the first precise analysis of the arithmetic complexity of various online multiplications. Our algorithm is faster than Fischer and Stockmeyer's by a constant factor; this is confirmed by our experimental results.
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00867279
Contributor : Romain Lebreton <>
Submitted on : Monday, November 24, 2014 - 5:07:24 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Long-term archiving on: : Wednesday, February 25, 2015 - 11:26:50 AM

File

RelaxMiddle-reviewed.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Romain Lebreton, Éric Schost. A simple and fast online power series multiplication and its analysis. Journal of Symbolic Computation, Elsevier, 2016, 72, pp.231-251. ⟨10.1016/j.jsc.2015.03.001⟩. ⟨lirmm-00867279v2⟩

Share

Metrics

Record views

605

Files downloads

545