Les contradictions de tenseur sont essentielles pour résoudre divers problèmes de recherche incluant le comptage de modèles, les circuits quantiques, les problèmes de graphes et l’apprentissage automatique. Cependant, pour minimiser le coût de calcul, il est crucial de trouver un ordre de contraction optimal. Par exemple, bien que la multiplication de matrices suive un même résultat final, les coûts de calcul varient selon leurs dimensions. Plus le nombre de tenseurs croît, plus le coût de contraction augmente également.
Les travaux précédents se sont focalisés sur des chemins de contraction (CP) efficaces pour les hyperréseaux de tenseurs. L’une des méthodes repose sur le recuit simulé et un algorithme génétique, surpassant l’approche cupide standard pour les réseaux plus petits. Une autre méthode, la décomposition de graphe, utilise les méthodes Line-Graph (LG) et Factor-Tree (FT), LG cherchant l’ordre de contraction via l’analyse structurée de graphes, tandis que FT gère les tenseurs de haut rang en phase de prétraitement. Une troisième méthode combine l’apprentissage par renforcement (RL) et les réseaux de neurones de graphes (GNN) pour découvrir un chemin efficace, applicable aux circuits quantiques réels et synthétiques.
Un groupe de chercheurs a introduit une méthodologie novatrice pour optimiser les chemins de contraction en améliorant l’algorithme cupide standard (SGA) par une fonction de coût avancée. Cette fonction de coût améliorée utilise davantage d’informations pour estimer les coûts de contractions paires, contrairement au SGA qui se base uniquement sur la taille des tenseurs d’entrée et de sortie. Cette approche surpasse les implémentations de pointe par Optimized Einsum (opt_einsum), et dans certains cas, elle éclipse les méthodes comme la partition hypergraphique combinée avec le cupide.
Trois phases caractérisent la méthode proposée pour le calcul des CP avec SGA dans opt_einsum :
– Calcul des produits de Hadamard, soit la multiplication élément par élément de tenseurs avec le même jeu d’indices.
– Contraction des tenseurs restants jusqu’à épuisement des indices de contraction en sélectionnant la paire de plus faible coût à chaque étape.
– Calcul des produits extérieurs par sélection de la paire minimisant la somme des tailles d’entrée à chaque étape.
De plus, l’algorithme cupide modifié utilise des fonctions de coût comme paramètres au lieu de se limiter à une seule fonction. Ces différentes fonctions sont utilisées en temps réel et la plus adaptée est sélectionnée pour générer les CP ultérieurs.
Des CP ont été calculés pour résoudre dix problèmes, utilisant une approche à multiples fonctions de coût, avec comparaison de divers algorithmes et mesure des flottants d’opérations (flops) pour chaque. Deux expériences ont été menées : la première calculant 128 chemins par algorithme sans tenir compte du temps de calcul pour évaluer la qualité des solutions ; la seconde limitant le temps de calcul à une seconde pour évaluer l’équilibre entre temps et qualité dans des scénarios pratiques.
En somme, les chercheurs ont proposé une approche innovante améliorant les chemins de contraction de tenseur en utilisant un algorithme cupide standard modifié. L’utilisation de multiples fonctions de coût permet de trouver efficacement des CP optimaux en moins de temps, surpassant les méthodes existantes pour résoudre des problèmes complexes.