There is a number of programs in CHEVIE for computing Kazhdan-Lusztig polynomials, left cells, and the various Kazhdan-Lusztig bases of Iwahori-Hecke algebras (see KL79).
From a computational point of view, Kazhdan-Lusztig polynomials are quite a challenge. It seems that the best approach still is by using the recursion formula in the original article KL79. One can first run a number of standard checks on a given pair of elements to see if the computation of the corresponding polynomial can be reduced to a similar computation for elements of smaller length, for example. One such check involves the notion of critical pairs (cf. Alv87): We say that a pair of elements w_1,w_2 in W such that w_1 leq w_2 is critical if {mathcal{L}}(w_2) subseteq {mathcal{L}}(w_1) and {mathcal{R}}(w_2) subseteq {mathcal{R}}(w_1), where {mathcal{L}} and {mathcal{R}} denote the left and right descent set, respectively.
Now if y,w in W are arbitrary elements with y leq w then there
always exists a critical pair (w_1,w_2) such that the Kazhdan-Lusztig
polynomials P_{y,w} and P_{w_1,w_2} are equal. Given two elements y
and w, such a critical pair is found by the function CriticalPair.
The CHEVIE programs for computing Kazhdan-Lusztig polynomials are
organized in such a way that whenever the polynomial corresponding to a
critical pair is computed then this pair and the polynomial are stored in
the component criticalPairs of the record of the underlying Coxeter
group. (This is different to earlier versions of CHEVIE.)
A good example to see how long the programs will take for computations in big Coxeter groups is the following:
LeftCells( CoxeterGroup( "F", 4 ) );
which takes 20 minutes cpu time on a SPARCstation 5 computer. The computation of all Kazhdan-Lusztig polynomials for type F_4 takes a bit more than~1 hour.
However, it still seems to be out of range to re-do Alvis' computation of the Kazhdan--Lusztig polynomials of the Coxeter group of type H_4 in a computer algebra system like GAP. For such applications, it is probably more efficient to use a special purpose program like the one provided by F. DuCloux DuC91.
The code for the Kazhdan-Lusztig bases C, D and their primed versions
has been written by Andrew Mathas. Some other bases (e.g., the Murphy
basis) can be found in his package Specht.
GAP 3.4.4