Dear Dan, dear Sage developers, Sage developers: please see the first point below.
On Sun, Dec 20, 2009 at 09:22:03PM -0800, Daniel Bump wrote: > 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. Excellent! > 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 Nice. We will want other representations as well (permutation representation, compact reduced word, ...). So this calls for some option like: sage: W = WeylGroup("B3", element_print_style = "reduced_word") Customizing the way the elements of a given parent are printed is a feature that we need in many other situations. So we want a standard user interface. I remember David Roe mentioning a couple months ago he had done something like this for some parent of his but I did not find back his e-mail. Pointers anyone? Call for votes / suggestions: what option name should we use? - element_print? - element_print_style? (this is long)? - element_repr? (this is not only about repr, but also latex/...) In practice, it will also be useful to have a method allowing for customizing this after the parent's creation, with a consistent name: sage: P = MyParent(...) sage: P.set_element_print_style() The rest of the discussion is specific to Coxeter groups. > 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. Yep. I would be perfectly fine just putting a systematic cache on all those methods. At least for the moment. If someone comes up with a use case where caching actually hurts, then it will still be time to go the extra mile. > The last parameter kl_parameter must be set to be an indeterminate, > if you want Kazhdan-Lusztig polynomials. In the literature it is q. It would feel more natural to me to set this as an option of the KL methods. Or would this be too heavy notation wise? An alternative approach would be to add a separate parent modeling the set of all KL polynomials: sage: W = WeylGroup("A3") sage: KL = KazhdanLusztigPolynomials(W, q = ...) (or W.kazhdan_luztig_polynomials(q)) sage: KL.P(u,v) ... That definitely would make sense if this set has some useful algebraic structure; but I am too much of an ignorant in the subject to have any point of view. > 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. Could you try how it is with weyl_group_optimizations-nt.patch? > 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. Ok. I can't promise to work on this shortly, so I'd suggest you give it a shot yourself. It's mostly a question of putting the methods for the parent in ParentMethods, and the methods for the elements in ElementMethods in the CoxeterGroups class (leaving for the moment the option handling to the constructor of WeylGroup). > (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. Even if Coxeter3 got included by default in Sage, your code could play a useful role as illustrative implementation of the algorithms you cite above: allowing the curious to learn about the algorithms in the topic by using introspection. And also for cross testing different implementations. > (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 assume it's related to the argument preprocessing. You may want to have a look at the section "Argument preprocessing" of UniqueRepresentation". > I can make a trac patch, but I think these issues need to be > discussed first so I'm starting with this email. Thanks! If you don't mind the overhead, I'd suggest to put your code on the Sage-Combinat patch server to ease playing around with it and merging/coordinating with related patches on the topic. Thanks for all your work on that topic! Cheers, Nicolas -- Nicolas M. Thiéry "Isil" <[email protected]> http://Nicolas.Thiery.name/ -- To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
