Algorithmes – disons rapides – pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionnelles

Résumé. Nous décrivons dans cet article deux algorithmes qui construisent les décompositions irréductible et équidimensionnelle d’une variété algébrique affine (ou projective), définie par un ensemble fini de polynômes. Le premier calcule les composantes irréductibles, donc dépend d’un algorithme de factorisation, et en conséquence ne peut se paralléliser que partiellement, du moins à notre connaissance. Le second correspond aux composantes équidimensionelles, et est susceptible d’une parallélisation totale. Comme applications, le lecteur trouvera en appendice un calcul de la forme de Chow d’une variété projective quelconque, dû à T. Krick et P. Solerno, et un calcul du degré d’une variété affine.Ces algorithmes sont décrits par des réseaux arithmétiques, ce qui permet un déroulement séquentiel ou parallèle (avec la restriction concernant la factorisation). En séquentiel, leurs complexités admettent une borne supérieure simplement exponentielle en la taille des polynômes d’entrée (quantité, degré, nombre de variables et éventuellement taille arithmétique). En parallèle, la complexité du deuxième algorithme devient polynomiale en cette taille.