Hi Andrew,
On Thu, Feb 16, 2012 at 08:39:14PM -0800, Andrew Mathas wrote:
> OK, it looks like permutations might be innocent and the real culprit
> might be e rational functions as suggested by Dima.
I profiled the last calculation with run_snake:
sage: run_snake("prod( (L[k]-x**c)/(x**content[k]-x**c) for k in
xrange(len(content)) for c in xrange(-k,k+1) if c<>content[k]")
and with a bit of work got a 10 times speedup. While actually reducing
the number of lines of code in Sage :-) In other words: example like
yours are very useful because they can point to the right spots that
need to be optimized, and thanks to the modularity of the code, those
optimizations can benefit many others.
At the end of the day, the main culprit was the Weyl group. Using
SymmetricGroup(4) instead took the time down from 14s to 4.5s. Then,
most of the computation time is spent in CombinatorialFreeModule:
products in H involves a lot of tiny linear combinations, and for
those CombinatorialFreeModule still needs a lot of little
optimizations here and there. With a couple of them I could go down to
2.26s:
sage: W = SymmetricGroup(4)
sage: W.cartan_type = lambda: CartanType("A3") # temporary workaround
sage: R=FractionField(PolynomialRing(ZZ,'x')); x=R.gen()
sage: H=IwahoriHeckeAlgebraT(W,x,base_ring = R)
sage: L=[H.one()]; # define Jucys-Murphy elements
sage: for k in xrange(1,4):
L.append(H._q1**-1*H.algebra_generators()[k]*L[k-1]*H.algebra_generators()[k])
sage: content=[0,1,-1,0] # content vector for Tableau([[1,2],[3,4]])
sage: %time prod( (L[k]-x**c)/(x**content[k]-x**c) for k in
xrange(len(content)) for c in xrange(-k,k+1) if c<>content[k])
CPU times: user 2.26 s, sys: 0.00 s, total: 2.27 s
Wall time: 2.27 s
This is now #12528. You are welcome to do a review of the small change
in the Iwahori Hecke file (or more!).
At this point, fraction field arithmetic is still mostly
negligible. Still I saved just a bit there by transforming the
is_exact() method into a cached_method, instead of handling the cache
by hand. See #12527.
One further optimization you may want to turn on is to put a cache
IwahoriHeckeAlgebraT.product_on_basis and
product_by_generator_on_basis (just insert a @cached_method just above
them). Then the above example goes down to 1.29 s. I am not so sure
about enabling this cache by default, since it may use up a lot of
memory memory for large groups.
Does this start to be acceptable?
There remains to optimize weyl group elements and to add a proper
cartan_type method to the symmetric group.
For the longer run, another potential issue is that Weyl group
elements (as those of WeylGroup("A3") used by default by
IwahoriHeckeAlgebraT) currently all have the same hash value:
sage: [hash(w) for w in WeylGroup("A3")]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Since the datastructure of elements of the IwahoriHeckeAlgebraT
(i.e. CombinatorialFreeModule) is a hash function, this can be really
bad for large linear combinations. This is worked around by this patch
in the Sage-Combinat queue:
- trac_10950-hash_matrices-nt.patch
but it needs a proper implementation before going into Sage. See also:
http://groups.google.com/group/sage-devel/browse_thread/thread/b5e63b24cd8f48e6/
Any volunteer?
> This was actually the first step in the calculations that I wanted to
> do, which involved taking certain sums of these idempotents reducing
> the coefficients modulo an ideal and seeing what happened to them. To
> do this I wanted to look the Hecke over the field of fractions of Z[x,
> \xi], where \xi is a primitive root of unity.
So you probably want to take as ground field:
sage: CyclotomicField(5)['xi'].fraction_field()
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-devel@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.
