#20165: Speedup CrystalOfLSPaths
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.1
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/speedup_crystal_LSPaths-20165|
f94651ea2c2f0112e277f90bafda389f4527e4a8
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
I have pushed to `public/combinat/backend_LS_paths-20165` another branch
which does a much more extensive rewrite of the Littelmann path model by
implementing a Cython backend which uses lists to represent dense vectors.
Doing this brings this example:
{{{
sage: La = RootSystem(['B',4]).weight_space().fundamental_weights()
sage: B = crystals.LSPaths(La[1]+La[2]+La[3])
sage: B.cardinality()
9009
sage: %time len(list(B))
CPU times: user 3.34 s, sys: 49.6 ms, total: 3.39 s
Wall time: 3.31 s
9009
}}}
down from around ~21 seconds. Compare this to some other models:
{{{
sage: La = RootSystem(['B',4]).weight_lattice().fundamental_weights()
sage: B = crystals.NakajimaMonomials('B4', La[1]+La[2]+La[3])
sage: %time len(list(B))
CPU times: user 16 s, sys: 44.2 ms, total: 16 s
Wall time: 16 s
9009
sage: B = crystals.RiggedConfigurations('B4', La[1]+La[2]+La[3])
sage: %time len(list(B))
CPU times: user 57 s, sys: 68.1 ms, total: 57.1 s
Wall time: 57 s
9009
sage: B = crystals.Tableaux('B4', shape=[3,2,1])
sage: %time len(list(B))
CPU times: user 1.7 s, sys: 16.1 ms, total: 1.72 s
Wall time: 1.7 s
9009
sage: B = crystals.AlcovePaths(La[1]+La[2]+La[3])
sage: %time len(list(B))
CPU times: user 2min 12s, sys: 364 ms, total: 2min 13s
Wall time: 2min 13s
9009
}}}
The drawback of this alternative implementation is that the only works
when the weight is given in the weight space. I think, in principle, it
should be possible to support other weight lattice realizations (e.g., the
ambient spaces), but I'm not sure we want to support that. Another option
would be to keep the old implementation around for when we are using
another weight lattice realization. The last option would be to push the
necessary data to the backend, but this would likely lead to code
duplication and a performance penality compared to the current version.
Before I finish this alternative implementation (including doc(tests),
looking for code cleanup, making sure it works for the projected level-
zero crystal, and/or further optimization), I wanted to get some feedback.
For the record, my opinion is option 1: drop support for non-weight-space
input.
--
Ticket URL: <http://trac.sagemath.org/ticket/20165#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
