A simple and fast online power series multiplication and its analysis - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport Année : 2013

A simple and fast online power series multiplication and its analysis

Eric Schost
  • Fonction : Auteur
  • PersonId : 839026

Résumé

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
submissionJSC.pdf (318.1 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00867279 , version 1

Citer

Romain Lebreton, Eric Schost. A simple and fast online power series multiplication and its analysis. RR-13032, 2013. ⟨lirmm-00867279v1⟩
415 Consultations
455 Téléchargements

Partager

Gmail Facebook X LinkedIn More