Coxeter

English version

Polynômes de Kazhdan-Lusztig

L'algorithme pour le calcul des polynômes de Kazhdan-Lusztig est toujours l'algorithme original de [1], qui donne une formule de récurrence pour le calcul des polynômes. Le secret de l'efficacité du programme est dans l'implémentation.

L'approche de la version 1 de Coxeter consistait, étant donné un groupe de Coxeter fini W, à calculer la table compète des P_x,y pour tous les couples x <= y dans W, et qui sont en "position extrémale" (cela signifie que l'ensemble de descente bilatère de y est contenu dans celui de x); trouver un polynôme donné se réduit alors à une opération de mise en position extrémale, qui est élémentaire.

L'approche suivie dans Coxeter3 est celle d'un calcul "à la demande". Comme nous l'avons expliqué ici, le groupe possède une partie énumérée P, pour laquelle on a tabulé les actions des générateurs et les ensembles de descente (ces éléments étaient tabulés pour le groupe tout entier dans la version 1). Si on doit calculer P_x,y pour un y qui ne se trouve pas dans P, on commence par étendre P pour qu'il contienne y (si la mémoire le permet bien sûr; sinon, on abandonne). Le programme maintient également un tableau de polynômes déjà calculés, qui contient une case (virtuelle) pour chaque paire extrémale (x,y). Au début, toutes les lignes du tableau sont vides (non allouées). Si on veut remplir la case (x,y), et que la ligne y est encore vide, on commence par l'allouer, en trouvant l'ensemble des paires extrémales pour y. Puis on remplit la case (x,y), en utilisant la formule de récurrence; si dans cette formule apparaissent des polynômes non encore calculés, on les remplit souvent la même procédure.

Pour les calculs de polynômes individuels, on essaie de ne remplir que les cases dont on a strictement besoin; cela conduit à un calcul relativement lent, où l'on passe beaucoup de temps à traverser des intervalles de Bruhat (pour appliquer la formule de récurrence.) On peut faire de façon beaucoup plus efficace le calcul de toute une ligne du tableau (c'est ce dont on a besoin, par exemple, si l'on veut calculer un élément de la base de Kazhdan-Lusztig.) Dans ce cas, les traversées peuvent être "mises en facteur", et au bout du compte le calcul d'une ligne va souvent presque aussi vite que de simplement remplir une case (mais consomme plus de mémoire bien sûr).

Une autre nouveauté intéressante de Coxeter3 est la fonction show. Elle permet d'ouvrir un peu la boîte noire de l'ordinateur, et de lui faire détailler un niveau de la formule de récurrence; par applications répétées, on arrive ainsi à parfois suivre assez bien le calcul.