Opened 11 years ago
Last modified 7 years ago
#10181 new enhancement
speed up AbelianGroup().subgroups()
Reported by: | zimmerma | Owned by: | joyner |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.4 |
Component: | group theory | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This was reported by Emmanuel Thome:
---------------------------------------------------------------------- | Sage Version 4.5.2, Release Date: 2010-08-05 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- sage: time len(AbelianGroup([2,4,8]).subgroups()) CPU times: user 2.35 s, sys: 0.14 s, total: 2.49 s Wall time: 14.75 s 81
With Magma:
Magma V2.16-10 Thu Oct 28 2010 11:25:26 on andouille [Seed = 3141449269] Type ? for help. Type <Ctrl>-D to quit. Loading startup file "/users/caramel/zimmerma/.magmarc" > time #Subgroups(AbelianGroup([2,4,8])); 81 Time: 0.020
Maybe #9773 helps, I did not try.
Paul Zimmermann
Attachments (1)
Change History (9)
comment:1 Changed 11 years ago by
Changed 11 years ago by
comment:2 Changed 11 years ago by
- Priority changed from major to minor
The culprit is really the constructor AbelianGroup_subgroup. It does the work again and again and again... Only for expository purpose, in the attached code (which does about the same thing as the subgroups() method anyway), the data shipped to the constructor is already in smith form, yet it takes ages to chat with gap, have it compute the smith form again, parse, etc, etc.
comment:3 follow-up: ↓ 4 Changed 11 years ago by
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
comment:4 in reply to: ↑ 3 Changed 11 years ago by
Replying to rbeezer:
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).
In fact, I realize I've been considering both as a combo. So maybe indeed subgroup_reduced, which is the middle man between subgroups() and the ctor, is responsible for the computation time. I'm not claiming the contrary. I just haven't tried to tell apart the subgroup_reduced() part and the AbelianGroup_subgroup part, w.r.t. timings.
comment:5 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 7 years ago by
- Milestone changed from sage-6.3 to sage-6.4
Just a comment. I did notice the oddity, but OTOH I'm not yelling to have it fixed.
E.