Coxeter
CoxeterLe programme fournit des commandes pour le calcul et l'affichage des cellules de Kazhdan-Lusztig et des W-graphes correspondants, pour les groupes de Coxeter finis. Le calcul est possible pour les cellules à gauche, à droite et bilatères. Il faut distinguer entre le simple calcul de la partition en cellules, qui pour certains groupes peut se faire sans aucun calcul de polynômes de Kazhdan-Lusztig, et la détermination du W-graphe correspondant.
Le programme peut aussi imprimer la relation d'ordre sur l'ensemble des cellules de chaque type. Pour les groupes de Weyl finis, par exemple, on sait que l'ensemble ordonné des cellules à gauche est isomorphe à l'ensemble des idéaux primitifs de l'algèbre enveloppante de l'algèbre semisimple correspondante.
L'algorithme utilisé calcule d'abord deux partitions du groupe dont on sait qu'elles "encadrent" la partition en cellules, et qui sont définies de façon élémentaire (voir les commentaires en tête du fichier cells.cpp). Si les deux partitions coïncident (ce qui est le cas, par exemple, en type A), on peut conclure immédiatement. Sinon, on doit raffiner chaque classe de la partition la plus grossière (dite "de l'invariant tau généralisé de Vogan") en cellules à gauche, en calculant les coefficients mu nécessaires. Ce calcul des classes à gauche ou à droite est assez satisfaisant; en revanche le calcul des classes bilatères, en principe beaucoup plus facile, devrait être repris. Il est actuellement fait "par la force brute", en déterminant le W-graphe.
Les trois types de cellules sont déterminés aussi pour la situation à paramètres inégaux; là, il faut directement déterminer la relation de préordre analogue à celle qui définit le W-graphe dans le cas des paramètres égaux (même si ici on n'a pas de W-graphe), et déterminer les cellules. Le programme utilise l'algorithme classique, dû à Tarjan, pour déterminer la relation d'équivalence (et la relation d'ordre) associées à la relation de préordre associée à un graphe orienté. C'est aussi cet algorithme qui est utilisé pour déterminer la relation d'ordre sur les cellules dans le cas des paramètres égaux.