[marc.van-leeu...@math.univ-poitiers.fr: Re: [sage-combinat-devel] Re: [sage-devel] Re: [Cython] LiE in Cython]
Please find below a first answer from Marc van Leeuwen who is travelling abroad and can't yet post to the mailing lists. - Forwarded message from Marc van Leeuwen - Quoting Daniel Bump : > William Stein has stated that LiE would not be made a > standard package because it is no longer supported. See: > > http://groups.google.com/group/sage-devel/msg/613cc5aa78c89f3d?hl=en Just for the record I should like to correct that to say it is no longer being developed, but it is still supported. You can address any bug reports to me, and I will correct them. That this hasn't happened for more than a decade doesn't imply that LiE is no longer working, rather to the contrary (and it even computes quite a bit faster than it used to;-). Anyone know when was the last change to the core TeX program? > My belief is that this is the right decision and that > the functionality in LiE should be redone natively in > sage. I can agree with that, if you can find someone to do it. I presume it is quite a it of work, but it may help that the mathematically relevant part is well separated from the rest, and almost completely done in Literate Programming. > It can do quite a few things and people have found it > very useful. > > One important thing LiE can so is to compute > Kazhdan-Lusztig polynomials. However it is slow and > can't get much past around B3. Here I agree; in fact doing Kazhdan-Lusztig polynomials does not blend well with the design of LiE where almost no information retained between computations. I was in fact against including these half-hearted procedures in LiE, but they were done anyway. > Coxeter3 is a better > program for this. KL polynomials are quite important > and it should be a priority to get them in Sage. When > I needed them I wrote my own routines, but only for > type A. > > Before KL Polynomials can be implemented Bruhat order > must be implemented in Sage. The root system patch does > not do this. Currently Bruhat order is in Sage but only > for Type A. I think a good way to give a fast recusive > definition would be to use Proposition 1.1 in > Stembridge, A Short Derivation of the Möbius Function > for the Bruhat Order, Journal of Algebraic Combinatorics > 25, (2007). Coxeter does KL Polynomials using the Bruhat order, and this is important for doing things like infinite Coxeter groups. Computing this order is not absolutely essential though; one can set up the recursion without knowing the Bruhat order beforehand, and find out what it is as result of the computation, with as main drawback that one is sometimes adding zeroes that could have been predicted if the Bruhat order had been known. Atlas works this way for computing the more general KLV polynomials, which is more or less inevitable because there is not really a clear Bruhat order around in its setting (an order can be defined, but it does not precisely predict the support of the KLV polynomials). > > Kazhdan-Lusztig polynomials can be computed quickly if > one is willing to cache a large number of results. If > one just caches everything computed, the main limitation > is the size of the Weyl group. Coxeter3 takes a more > intelligent approach by deciding carefully what to > cache. My understanding is that apart from polynomials that are immediate copies of other ones, it is more or less imperative to cache everything computed or else computation time increases exponentially. Coxeter3 however is more intelligent in not insisting (like atlas does) that every KL polynomial be computed if any one of them needed, which makes doing infinite groups possible. -- Marc van Leeuwen > Dear Dan, Marc, David, Steve, Mike, ... > > On Tue, Oct 20, 2009 at 09:53:01AM -0700, Daniel Bump wrote: >> > By the way: what's the status of this spkg? Is there some >> > documentation somewhere of what can be done with it from Sage? (I just >> > tried lie-2.2.2.p3 but it does not seem compile on my 32bits i686 >> > ubuntu box). >> >> William Stein has stated that LiE would not be made a >> standard package because it is no longer supported. See: >> >> http://groups.google.com/group/sage-devel/msg/613cc5aa78c89f3d?hl=en >> >> My belief is that this is the right decision and that the >> functionality in LiE should be redone natively in sage. It can do >> quite a few things and people have found it very useful. > > Dan: Thanks for sharing your view on this! > > Marc: what is your opinion? > > By the way: we are organizing Sage days 20 at CIRM at the end of > February with combinatorics as main theme. We will update the web page > soon: http://www.lirmm.fr/arith/wiki/MathInfo2010/SageDays. But > unofficially, I can already tell that root systems and friends are one > of the main themes. In particular, we will host at least one Chevie > developer (M. Geck) and with some chances A. Mathas and C. Hohlweg > will join as well. > > Marc: would you be willing to join and offer us insight on how best to > integrate / reuse / port /
Re: [sage-combinat-devel] Re: [sage-devel] Re: [Cython] LiE in Cython
Dear Dan, Marc, David, Steve, Mike, ... On Tue, Oct 20, 2009 at 09:53:01AM -0700, Daniel Bump wrote: > > By the way: what's the status of this spkg? Is there some > > documentation somewhere of what can be done with it from Sage? (I just > > tried lie-2.2.2.p3 but it does not seem compile on my 32bits i686 > > ubuntu box). > > William Stein has stated that LiE would not be made a > standard package because it is no longer supported. See: > > http://groups.google.com/group/sage-devel/msg/613cc5aa78c89f3d?hl=en > > My belief is that this is the right decision and that the > functionality in LiE should be redone natively in sage. It can do > quite a few things and people have found it very useful. Dan: Thanks for sharing your view on this! Marc: what is your opinion? By the way: we are organizing Sage days 20 at CIRM at the end of February with combinatorics as main theme. We will update the web page soon: http://www.lirmm.fr/arith/wiki/MathInfo2010/SageDays. But unofficially, I can already tell that root systems and friends are one of the main themes. In particular, we will host at least one Chevie developer (M. Geck) and with some chances A. Mathas and C. Hohlweg will join as well. Marc: would you be willing to join and offer us insight on how best to integrate / reuse / port / reimplement or otherwise recycle the features in LiE, and coordinate with the LiE community? David: you would be most welcome as well! > One important thing LiE can do is to compute Kazhdan-Lusztig > polynomials. However it is slow and can't get much past around > B3. Coxeter3 is a better program for this. KL polynomials are quite > important and it should be a priority to get them in Sage. When I > needed them I wrote my own routines, but only for type A. > Before KL Polynomials can be implemented Bruhat order must be > implemented in Sage. The root system patch does not do > this. Currently Bruhat order is in Sage but only for Type A. I think > a good way to give a fast recusive definition would be to use > Proposition 1.1 in Stembridge, A Short Derivation of the Möbius > Function for the Bruhat Order, Journal of Algebraic Combinatorics > 25, (2007). Thanks to Steve, the Bruhat poset for all (finite) types has been in the Sage-Combinat queue since May or June. With root_systems-bruhat_order-nt.patch and preferably weyl_group_optimizations-nt.patch, you can do things like: sage: W = WeylGroup(["D", 4]) sage: B = W.bruhat_poset() sage: u = B[0] sage: v = B[50] sage: B.mobius_function(u,v) -1 Everything is based on the following recursive implementation of lower covers for Bruhat order, which also works for infinite groups, and uses the same approach as Stembridge's implementation (so I assume as in his paper): @cached_in_parent_method def bruhat_lower_covers(self): desc = self.first_descent() if desc is not None: ww = self.apply_simple_reflection(desc) return [u.apply_simple_reflection(desc) for u in ww.bruhat_lower_covers() if not u.has_descent(desc)] + [ww] else: return [] (by the way: Steve: could you add a ref to Stembridge's paper in the doc, and use `descent` rather than `desc`?) And with #7004 (also in the queue) + graphviz + the dot2tex spkg, you can further do: sage: G = B.hasse_diagram() sage: G.set_latex_options(format="dot2tex") sage: view(G, tightpage = True, pdflatex=True) There are still lots of rough corners, so this won't be integrated instantly into Sage. It also badly needs further optimizations in CombinatorialFreeModules, Weyl groups, ... > Kazhdan-Lusztig polynomials can be computed quickly if one is > willing to cache a large number of results. If one just caches > everything computed, the main limitation is the size of the Weyl > group. Coxeter3 takes a more intelligent approach by deciding > carefully what to cache. Using Coxeter3 sounds definitely like the way to go for KL. Thanks Mike for your work on that! Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ --~--~-~--~~~---~--~~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -~--~~~~--~~--~--~---
Re: [sage-combinat-devel] Re: [sage-devel] Re: [Cython] LiE in Cython
> By the way: what's the status of this spkg? Is there some > documentation somewhere of what can be done with it from Sage? (I just > tried lie-2.2.2.p3 but it does not seem compile on my 32bits i686 > ubuntu box). William Stein has stated that LiE would not be made a standard package because it is no longer supported. See: http://groups.google.com/group/sage-devel/msg/613cc5aa78c89f3d?hl=en My belief is that this is the right decision and that the functionality in LiE should be redone natively in sage. It can do quite a few things and people have found it very useful. One important thing LiE can so is to compute Kazhdan-Lusztig polynomials. However it is slow and can't get much past around B3. Coxeter3 is a better program for this. KL polynomials are quite important and it should be a priority to get them in Sage. When I needed them I wrote my own routines, but only for type A. Before KL Polynomials can be implemented Bruhat order must be implemented in Sage. The root system patch does not do this. Currently Bruhat order is in Sage but only for Type A. I think a good way to give a fast recusive definition would be to use Proposition 1.1 in Stembridge, A Short Derivation of the Möbius Function for the Bruhat Order, Journal of Algebraic Combinatorics 25, (2007). Kazhdan-Lusztig polynomials can be computed quickly if one is willing to cache a large number of results. If one just caches everything computed, the main limitation is the size of the Weyl group. Coxeter3 takes a more intelligent approach by deciding carefully what to cache. Dan --~--~-~--~~~---~--~~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org -~--~~~~--~~--~--~---
