A simple and fast online power series multiplication and its analysis - Archive ouverte HAL Access content directly
Journal Articles Journal of Symbolic Computation Year : 2016

A simple and fast online power series multiplication and its analysis

(1) , (2)
1
2
Romain Lebreton

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.
Fichier principal
Vignette du fichier
RelaxMiddle-reviewed.pdf (317.74 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00867279 , version 1 (27-09-2013)
lirmm-00867279 , version 2 (24-11-2014)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More