Les contradictions de tenseur sont essentielles pour r\u00e9soudre divers probl\u00e8mes de recherche incluant le comptage de mod\u00e8les, les circuits quantiques, les probl\u00e8mes de graphes et l’apprentissage automatique. Cependant, pour minimiser le co\u00fbt de calcul, il est crucial de trouver un ordre de contraction optimal. Par exemple, bien que la multiplication de matrices suive un m\u00eame r\u00e9sultat final, les co\u00fbts de calcul varient selon leurs dimensions. Plus le nombre de tenseurs cro\u00eet, plus le co\u00fbt de contraction augmente \u00e9galement.<\/p>\n
Les travaux pr\u00e9c\u00e9dents se sont focalis\u00e9s sur des chemins de contraction (CP) efficaces pour les hyperr\u00e9seaux de tenseurs. L’une des m\u00e9thodes repose sur le recuit simul\u00e9 et un algorithme g\u00e9n\u00e9tique, surpassant l’approche cupide standard pour les r\u00e9seaux plus petits. Une autre m\u00e9thode, la d\u00e9composition de graphe, utilise les m\u00e9thodes Line-Graph (LG) et Factor-Tree (FT), LG cherchant l’ordre de contraction via l’analyse structur\u00e9e de graphes, tandis que FT g\u00e8re les tenseurs de haut rang en phase de pr\u00e9traitement. Une troisi\u00e8me m\u00e9thode combine l’apprentissage par renforcement (RL) et les r\u00e9seaux de neurones de graphes (GNN) pour d\u00e9couvrir un chemin efficace, applicable aux circuits quantiques r\u00e9els et synth\u00e9tiques.<\/p>\n
Un groupe de chercheurs a introduit une m\u00e9thodologie novatrice pour optimiser les chemins de contraction en am\u00e9liorant l\u2019algorithme cupide standard (SGA) par une fonction de co\u00fbt avanc\u00e9e. Cette fonction de co\u00fbt am\u00e9lior\u00e9e utilise davantage d’informations pour estimer les co\u00fbts de contractions paires, contrairement au SGA qui se base uniquement sur la taille des tenseurs d’entr\u00e9e et de sortie. Cette approche surpasse les impl\u00e9mentations de pointe par Optimized Einsum (opt_einsum), et dans certains cas, elle \u00e9clipse les m\u00e9thodes comme la partition hypergraphique combin\u00e9e avec le cupide.<\/p>\n
Trois phases caract\u00e9risent la m\u00e9thode propos\u00e9e pour le calcul des CP avec SGA dans opt_einsum :<\/p>\n
– Calcul des produits de Hadamard, soit la multiplication \u00e9l\u00e9ment par \u00e9l\u00e9ment de tenseurs avec le m\u00eame jeu d’indices.
\n– Contraction des tenseurs restants jusqu’\u00e0 \u00e9puisement des indices de contraction en s\u00e9lectionnant la paire de plus faible co\u00fbt \u00e0 chaque \u00e9tape.
\n– Calcul des produits ext\u00e9rieurs par s\u00e9lection de la paire minimisant la somme des tailles d’entr\u00e9e \u00e0 chaque \u00e9tape.<\/p>\n
De plus, l’algorithme cupide modifi\u00e9 utilise des fonctions de co\u00fbt comme param\u00e8tres au lieu de se limiter \u00e0 une seule fonction. Ces diff\u00e9rentes fonctions sont utilis\u00e9es en temps r\u00e9el et la plus adapt\u00e9e est s\u00e9lectionn\u00e9e pour g\u00e9n\u00e9rer les CP ult\u00e9rieurs.<\/p>\n
Des CP ont \u00e9t\u00e9 calcul\u00e9s pour r\u00e9soudre dix probl\u00e8mes, utilisant une approche \u00e0 multiples fonctions de co\u00fbt, avec comparaison de divers algorithmes et mesure des flottants d’op\u00e9rations (flops) pour chaque. Deux exp\u00e9riences ont \u00e9t\u00e9 men\u00e9es : la premi\u00e8re calculant 128 chemins par algorithme sans tenir compte du temps de calcul pour \u00e9valuer la qualit\u00e9 des solutions ; la seconde limitant le temps de calcul \u00e0 une seconde pour \u00e9valuer l’\u00e9quilibre entre temps et qualit\u00e9 dans des sc\u00e9narios pratiques.<\/p>\n
En somme, les chercheurs ont propos\u00e9 une approche innovante am\u00e9liorant les chemins de contraction de tenseur en utilisant un algorithme cupide standard modifi\u00e9. L’utilisation de multiples fonctions de co\u00fbt permet de trouver efficacement des CP optimaux en moins de temps, surpassant les m\u00e9thodes existantes pour r\u00e9soudre des probl\u00e8mes complexes.<\/p>\n","protected":false},"excerpt":{"rendered":"
Les contradictions de tenseur sont essentielles pour r\u00e9soudre divers probl\u00e8mes de recherche incluant le comptage de mod\u00e8les, les circuits quantiques, les probl\u00e8mes de graphes et l’apprentissage automatique. Cependant, pour minimiser le co\u00fbt de calcul, il est crucial de trouver un ordre de contraction optimal. Par exemple, bien que la multiplication de matrices suive un m\u00eame […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-28","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"\n