Coxeter

Version française

Kazhdan-Lusztig polynomials

The algorithm we use for the computation of Kazhdan-Lusztig polynomials is still the original one from [1], which yields a recursion formula for their computation by induction on the length of the larger element. The secret of the program's efficency is in the implementation.

Given a finite Coxeter group W, the approach in version 1 of Coxeter was to compute once and for all the full table of Kazhdan-Lusztig polynomials, for all x <= y in W in "extremal position" (this means that the descent set of y is contained in that of x); finding a Kazhdan-Lusztig polynomial then reduces to an elementary extremalization and a table lookup.

Of course such an approach is impossible for infinite Coxeter groups, or even for large finite ones. The view taken in Coxeter3 is therefore one of "on demand" computation. As we explained here, the group posesses an enumerated part P, for which the actions of the generators and the descent seets have been tabulated (they had been tabulated for the full group in version 1.) To compute P_x,y for an element y not already in P, one starts out by extending P so that it contains y (memory permitting of course; otherwise the program gives up.) The program also maintains a table of computed polynomials, which has a (virtual) entry for each extremal pair (x,y). Initially, all rows in the table are empty (indeed, not allocated.) If the polynomial for (x,y) is requested, and the row for y is still empty, we first allocate it, by finding the list of extremal x w.r.t. y (this can be done very efficiently by bitmap intersections.) Then we fill in the entry for (x,y), using the recursion formula; each time we encounter a polynomial which has not been computed yet, we get it using the same procedure.

For the computation of individual polynomials, we try to fill as few entries as possible. this leads to a relatively slow computation, where a lot of time is spent traversing Bruhat intervals (often repeatedly.) The computation of a whole row in the table can be done much more efficiently --- this is what is needed, for instance, when we want to find one element of the Kazhdan-Lusztig basis of the Hecke algebra. In this case, many interval traversals may be "factored out", and in the end the computation of a full row is often almost as fast as the computation of a single entry (but consumes more memory of course.)

Another interesting novelty of Coxeter3 is the show command. This will open up a little the black box surrounding the computation of a polynomial, spelling out exactly what terms effectively appear in the recursion formula. Repeated applications of show sometimes makes it possible to follow a computation rather nicely.