Coxeter
CoxeterUn des points forts de la version 3 de Coxeter est qu'il contient une implémentation complète de l'algorithme des racines minimales (ou élémentaires) de Brink et Howlett [1] (voir aussi ce cours de Bill Casselman). Grâce à cet algorithme, on peut réduire, et aussi trouver l'expression lexicographiquement minimale, pour un ordre donné sur les générateurs, de tout mot en les générateurs.
Le programme le fait pour tout groupe dont le rang ne dépasse pas la moitié du nombre de bits d'un mot machine (donc 16 sur une machine 32 bits, et 32 sur une machine 64 bits), dont les coefficients de la matrice de Coxeter ne dépassent pas 32763 (s'ils sont finis; les coefficients infinis sont permis), et pour lesquels la construction de l'ensemble des racines minimales ne conduit pas à un débordement de la mémoire (en pratique, l'ensemble des racines minimales pour les groupes qu'on rencontre semble toujours être assez petit; par exemple, pour les groupes finis il se confond avec l'ensemble des racines positives, et pour les groupes affines il est en bijection avec l'ensemble de toutes les racines, positives et négatives, du groupe de Weyl fini correspondant.)
En plus des normalisations ci-dessus, le programme effectue des opérations élémentaires comme le calcul de l'ensemble de descente d'un élément du groupe, et la comparaison de deux éléments dans l'ordre de Bruhat par l'algorithme élémentaire bien connu [2].
A cause de cette possibilité de réduire et de comparer les mots, la représentation par défaut des éléments d'un groupe de Coxeter à l'intérieur du programme est sous forme d'expressions réduites (sauf en ce qui concerne la partie énumérée du groupe.) En plus de cette numérotation de la partie énumérée (désignée par un signe % en sortie, et qui peut dépendre de la session), il y a pour les groupes finis dont le cardinal ne dépasse pas le plus grand unsigned long représentable en machine, une numérotation canonique des éléments du groupe, indiquée par un signe #, et qui peut servir de raccourci en entrée à chaque fois que l'on doit entrer un élément (voir l'aide de la commande compute pour plus de détails sur les conventions d'entrée.) En type A, il est possible aussi d'entrer un élément sous forme de permutation.
| [1] | B. Brink and R. Howlett, A finiteness property and an automatic structure for Coxeter groups, Math. Annalen 296, 1993, pp. 179-190. |
| [2] | J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, UK, 1990. |