Arbre de produits
# Arbre de produits

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 $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 $p_{0}$ et $p_{1}$ tels que $p=p_{0}p_{1}$ ; et ainsi de suite jusqu'aux feuilles qui portent les éléments $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 $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 $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 $p$ est plus efficace que la méthode consistant à former $q_{1}=a_{0}a_{1}$, $q_{2}=q_{1}a_{2}$, puis $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.

