#10181: speed up AbelianGroup().subgroups()
----------------------------+-----------------------------------------------
Reporter: zimmerma | Owner: joyner
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.6
Component: group theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Comment(by rbeezer):
In response to a question by Paul Zimmerman on #9773, the implementation
of finitely-generated abelian groups there could possibly speed up
subgroup generation by something like 8x. Current {{{subgroups()}}}
routine calls {{{subgroups_reduced())}}}, I think once per subgroup, maybe
more. It would appear to be responsible for most of the computation time.
this does not exactly jibe with the observations of thome, but I have not
spent the time to follow his explanation (though it wouldn't surprise me
if it was similar, plausible or the same as what I'm presenting).
{{{
sage: G=AbelianGroup([2,4,8])
sage: len(G.subgroups())
81
sage: G.subgroup_reduced( [ [1,0,4], [1,2,4] ])
Multiplicative Abelian Group isomorphic to C2 x C2, which is the subgroup
of
Multiplicative Abelian Group isomorphic to C2 x C4 x C8
generated by [f1^2, f0*f2^4]
sage: timeit("G.subgroup_reduced( [ [1,0,4], [1,2,4] ])")
5 loops, best of 3: 81.2 ms per loop
sage: timeit("G.subgroups()")
5 loops, best of 3: 7.52 s per loop
}}}
Draft patch at #9773 builds on finitely-generated modules, so the
"reduction" to invariants is computed there, about 8x faster it would
appear. Patch does not have a {{{subgroups()}}} routine yet, but could be
easy to add. Maybe more efficiencies could be found. Using code in
#9773:
{{{
sage: G=AdditiveAbelianFGGroup([2,4,8])
sage: H=G.subgroup([[1,0,4],[1,2,4]])
sage: H
Additive abelian group of order 4, isomorphic to Z_2 + Z_2 with
generator(s): (0, 2, 0), (1, 0, 4)
sage: timeit("G.subgroup([[1,0,4],[1,2,4]])")
25 loops, best of 3: 10.2 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10181#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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
