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:

Status badges

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)

subgroups.sage (3.1 KB) - added by thome 11 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 11 years ago by thome

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

E.

Changed 11 years ago by thome

comment:2 Changed 11 years ago by thome

  • 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: Changed 11 years ago 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

comment:4 in reply to: ↑ 3 Changed 11 years ago by thome

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 jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.