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.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2016, 72, pp.231-251. 〈10.1016/j.jsc.2015.03.001〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00867279
Contributeur : Romain Lebreton <>
Soumis le : lundi 24 novembre 2014 - 17:07:24
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05
Document(s) archivé(s) le : mercredi 25 février 2015 - 11:26:50

Fichier

RelaxMiddle-reviewed.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

194