speed up AbelianGroup().subgroups()

[zimmermann6]

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

Component: group theory

Issue created by migration from https://trac.sagemath.org/ticket/10181

[emmanuelthome]

comment:1

Just a comment. I did notice the oddity, but OTOH I'm not yelling to have it fixed.

E.

[emmanuelthome]

Attachment: subgroups.sage.gz

[emmanuelthome]

comment:2

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.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:3

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

[emmanuelthome]

comment:4

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.