I have what seems to be a working patch to compute Kazhdan Lusztig polynomials at:
http://sporadic.stanford.edu/bump/patches/kazhdan_lusztig.patch This implements the Bruhat order, Bruhat interval and Kazhdan-Lusztig polynomials for Weyl groups. The patch adds three optional parameters to WeylGroup. The first is prefix, which modifies the behavior of the __repr__ method. This defaults to None and if you do not change it, the behavior is the same as the old behavior. Weyl group elements are represented as matrices. On the other hand, you can do this: sage: W = WeylGroup("B3",prefix="s") sage: [s1,s2,s3]=W.simple_reflections() Then you do things like this: sage: (s1*s2*s3)^4 s3*s2*s3*s1*s2*s1 sage: (s1*s2*s3).order() 6 The other two parameters are cache_results and kl_parameter. If you set cache_results=True, then results of intermediate calculations are cached. Specifically, the Bruhat order, Kazhdan-Lusztig R-polynomials and Kazhdan-Lusztig P-polynomials are cached. This is necessary because the algorithms are highly recursive. The last parameter kl_parameter must be set to be an indeterminate, if you want Kazhdan-Lusztig polynomials. In the literature it is q. The patch implements the Bruhat order, Bruhat intervals, and Kazhdan-Lusztig R and P polynomials. It is a little slow. sage: W = WeylGroup("A3",prefix="s",cache_results=True,kl_parameter=q) sage: [s1,s2,s3]=W.simple_reflections() sage: W.kazhdan_lusztig_P(s2,s2*s1*s3*s2) q + 1 That took 12 seconds, which might seem unacceptably slow, but due to the caching, if you do several of these calculations, it gets faster. It is not unacceptably slow to compute all 288 KL polynomials for A3. I checked that it gives the right answer for all Kazhdan Lusztig polynomials in the case of A3. There are only six interesting pairs u,v with u<=v and P(u,v) != 1. In each of these either v = s2 s1 s3 s2 and u<=s2 or v = s1 s3 s2 s1 s3 and u<=s1 s3. Further testing is needed to see if is working right for Type B. I do not know if the program will work without modification for affine Weyl groups, but I hope that it does. The algorithm is explained in a paper of Brenti at: http://www.emis.de/journals/SLC/wpapers/s49brenti.html . There are also various papers of Fokko du Cloux about computing KL polynomials. However coxeter3 produces the same result essentially instantly. Thus speed is one issue with this patch. Other issues: (1) The algorithms should be moved to coxeter_groups.py. They are applicable to arbitrary coxeter groups. I put them in weyl_groups.py because I'm more familiar with that file and wanted to get a fast prototype. (2) If Mike Hansen's coxeter3 wrapper can be made a standard package, these algorithms may not be needed. Coxeter3 is GPL so there are no licensing issues. (3) There is one doctest failure in weyl_groups.py. I was unable to debug it. I am doing something wrong with unique_representation that I wasn't able to track down. I can make a trac patch, but I think these issues need to be discussed first so I'm starting with this email. Dan -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
