Arbre de produits

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, et plus particulièrement en calcul formel, un arbre de produits est une structure obtenue en découpant récursivement un produit d'objets tels que des entiers ou des polynômes en sous-produits équilibrés. Le produit complet  est placé à la racine de l'arbre ; celle-ci a (généralement) deux fils étiquetés par des sous-produits de taille (degré ou nombre de chiffres, par exemple) comparable et tels que  ; et ainsi de suite jusqu'aux feuilles qui portent les éléments à multiplier. Ainsi, les nœuds de l'arbre correspondent aux résultats intermédiaires dans le calcul du produit par un algorithme diviser pour régner.

L'intérêt principal des arbres de produits est de tirer parti des algorithmes de multiplication rapide d'entiers ou de polynômes. La situation la plus simple est celle où l'on cherche à calculer le produit d'un grand nombre de « petits » entiers ou polynômes . Dans ce contexte, et pourvu que l'on dispose d'une multiplication rapide, l'algorithme diviser pour régner esquissé au paragraphe précédent pour calculer  est plus efficace que la méthode consistant à former , , puis , et ainsi de suite. Le résultat du calcul correspond alors simplement à la racine de l'arbre.

Des arbres de produits entiers, résultats intermédiaires compris, interviennent notamment dans les algorithmes classiques d'évaluation multipoint et d'interpolation rapide de polynômes.

Références[modifier | modifier le code]

  • D. J. Bernstein. Fast multiplication and its applications. In J. Buhler and P. Stevenhagen, editors, Algorithmic Number Theory, pages 325--384. Cambridge University Press, 2008. [lire en ligne]
  • Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Bruno Salvy et Éric Schost, Algorithmes efficaces en calcul formel (support de cours, Master parisien de recherche en informatique) [lire en ligne]