The Middle Product Algorithm I. Speeding up the division and square root of power series

Guillaume Hanrot 1 Michel Quercia Paul Zimmermann 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present new algorithms for the inverse, division, and square root of power series. The key trick is a new algorithm --- {\tt MiddleProduct} or, for short, {\tt MP} --- computing the $n$ middle coefficients of a $(2n-1) \times n$ full product in the same number of multiplications as a full $n \times n$ product. This improves previous work of Brent, Mulders, Karp and Markstein, Burnikel and Ziegler. These results apply both to series and polynomials.
Type de document :
Article dans une revue
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2004, 14 (6), pp.415-438
Liste complète des métadonnées

https://hal.inria.fr/inria-00100147
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:39
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00100147, version 1

Collections

Citation

Guillaume Hanrot, Michel Quercia, Paul Zimmermann. The Middle Product Algorithm I. Speeding up the division and square root of power series. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2004, 14 (6), pp.415-438. 〈inria-00100147〉

Partager

Métriques

Consultations de la notice

334