Arbre de produits

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (avril 2016).

Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.

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 ${\displaystyle p}$ 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 ${\displaystyle p_{0}}$ et ${\displaystyle p_{1}}$ tels que ${\displaystyle p=p_{0}p_{1}}$ ; et ainsi de suite jusqu'aux feuilles qui portent les éléments ${\displaystyle a_{0},a_{1},\dots a_{n-1}}$ à multiplier. Ainsi, les nœuds de l'arbre correspondent aux résultats intermédiaires dans le calcul du produit ${\displaystyle p=a_{0}a_{1}\dots a_{n-1}}$ 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 ${\displaystyle a_{0},a_{1},\dots ,a_{n-1}}$. 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 ${\displaystyle p}$ est plus efficace que la méthode consistant à former ${\displaystyle q_{1}=a_{0}a_{1}}$, ${\displaystyle q_{2}=q_{1}a_{2}}$, puis ${\displaystyle q_{3}=q_{2}a_{3}}$, 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.

• 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]

• Portail de l'informatique théorique