#19075: Speedup creation of Kleber tree
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: combinatorics | Resolution:
Keywords: rigged | Merged in:
configurations, kleber tree | Reviewers:
Authors: Travis Scrimshaw | Work issues:
Report Upstream: N/A | Commit:
Branch: | f9da27b2e6e3a5ecf891001c184d4201532c3d01
public/rigged_configurations/speedup_kleber_tree-19075| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by tscrim):
To note, from looking over the profiling data, the majority of time is
devoted to doing arithmetic using combinatorial free modules and just
taking so long due to the sheer number of calculations.
It seems like on small rank, this is slower change is ~3-5x slower:
{{{
sage: RC = RiggedConfigurations(['D',4,1], [[4,2], [1,3], [2,4]])
sage: %time len(RC.module_generators)
CPU times: user 928 ms, sys: 84 ms, total: 1.01 s
Wall time: 1.47 s
586
}}}
vs the current version:
{{{
sage: %time len(RC.module_generators)
CPU times: user 340 ms, sys: 4 ms, total: 344 ms
Wall time: 348 ms
586
}}}
But for larger rank, it still is faster:
{{{
sage: RC = RiggedConfigurations(['D',8,1], [[4,2], [1,3], [2,4]])
sage: %time len(RC.module_generators)
CPU times: user 38.4 s, sys: 148 ms, total: 38.6 s
Wall time: 40.7 s
19234
}}}
vs I didn't have the patience to wait.
More data:
{{{
sage: RC = RiggedConfigurations(['D',6,1], [[4,6]])
sage: %time len(RC.module_generators)
CPU times: user 392 ms, sys: 56 ms, total: 448 ms
Wall time: 648 ms
28
}}}
previous:
{{{
sage: %time len(RC.module_generators)
CPU times: user 1.46 s, sys: 0 ns, total: 1.46 s
Wall time: 1.52 s
28
}}}
For F,,4,,^(1)^, I get the new version is 2-20x faster for B^i,1^, where i
= 1,2,3,4.
The question then becomes should we deal with the slowdown in small ranks,
or keep both algorithms and have a heuristic which chooses between the
two?
--
Ticket URL: <http://trac.sagemath.org/ticket/19075#comment:2>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
