`Coxeter`

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.

[1] | D. Kazhdan and G. Lusztig, Representations of Coxeter Groups and Hecke
Algebras, Invent. math. 53, 1979, pp. 165-184. |

Back to the Coxeter home page.