Dear Dan, On Fri, Dec 18, 2009 at 08:53:27AM -0800, bump wrote: > Here is the patch: > > http://sporadic.stanford.edu/bump/patches/bruhat_order.patch > > You use it like this: > > W = WeylGroup("E6") > W.bruhat_ordered(x,y) > > where x and y are Weyl group elements. It returns true if x<=y.
Ah ah, I had not realized one could to Bruhat order this way. Thanks, I learned something today. It is essentially linear in the length of x * rank(group), right? That's pretty cool actually! Suggestions: - Calling it bruhat_le ? - Putting it in sage/categories/coxeter_groups.py Maybe as a method on elements? - Using y.first_descent() / x.has_descent(i) and possibly x.apply_simple_reflection(i) See e.g. bruhat_lower_covers when root_systems-bruhat_order-nt.patch is applied. > Note that it is recursive and therefore slow. So the bruhat order > needs to be cached. This kind of caching is one of the purposes of the bruhat_poset() thingy: sage: W = WeylGroup(["C",3]) sage: P = W.bruhat_poset() sage: s = W.simple_reflections() sage: P(s[2]) < P(s[1]*s[2]*s[1]) True However, this currently precomputes the full poset, which is not acceptable for large/infinite groups. We really need lazy posets! See also my e-mail from Oct. 21. In any cases, with the algorithm you implemented it's simpler to just set a cache directly on the method. One can do this by just adding @cached_method on top of it if one does not mind if the caching occurs for all groups. Otherwise, see below. > An untested implementation of this caching is in the > second patch: > > http://sporadic.stanford.edu/bump/patches/bruhat_order_cache.patch > > The second patch goes on top of the first and (assuming it works) > > W = WeylGroup("E6",cache_results=True) > > should create a Weyl group with faster Bruhat order. > > The first patch works. I don't know if it works for affine Weyl > groups. The second patch could still be buggy. Ah ah, an excellent occasion to exercise an old idea of mine to solve generically this kind of issue. Please give a try to the attached patch add_cache-nt.patch (it requires the category patches; I'll put it into the Sage-Combinat queue when it will be back online), and have a look at the documentation of Sets.ParentMethods.cache_element_methods in categories/sets_cat.py. In principle, you should then be able to do: W = WeylGroup("E6") W.cache_element_methods("bruhat_le") It currently only handles methods of elements though, so you would need to adapt your patch to make bruhat_le a method of the elements. It also does some black magic under the scene (changing the class of the elements), so if you call cache_element_methods after having created elements, you could get compatibility issues between old and new elements. That's precisely what I want to exercise to see if it's a bother in practice or not. Cheers, Nicolas -- Nicolas M. Thiéry "Isil" <nthi...@users.sf.net> http://Nicolas.Thiery.name/ -- 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.
