Opened 9 years ago

Closed 2 years ago

#10184 closed enhancement (fixed)

class group iterator is too slow

Reported by: thome Owned by: davidloeffler
Priority: minor Milestone: sage-8.1
Component: number fields Keywords: sd51
Cc: Merged in:
Authors: Emmanuel Thome Reviewers: Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 9fe600e (Commits) Commit: 9fe600ed3691d52d3e3f981e09283e1bf863ead7
Dependencies: Stopgaps:

Description (last modified by AlexGhitza)

the class group iterator takes evey element in turn, and computes the product of the g^i's. Sure powers are computed by repeated squaring, but for iterators this is suboptimal.

On my laptop, from this situation...

sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
sage: OK=K.maximal_order()
sage: G=K.class_group()                        
sage: time _=G.list()
CPU times: user 2.48 s, sys: 0.05 s, total: 2.53 s
Wall time: 2.53 s

the attached patch improves to...

sage: K.<v>=NumberField(x^4 + 514*x^2 + 64321)
sage: OK=K.maximal_order()
sage: G=K.class_group()                        
sage: time _=G.list()
CPU times: user 0.45 s, sys: 0.00 s, total: 0.45 s
Wall time: 0.44 s

which is a tad better.

doctest included (actually the previous doctest wasn't doing much, this one is slightly more thorough).

Note: while the code would work for any abelian group, I believe it makes sense only when the group operation is sufficiently non-trivial.

Attachments (3)

classgroup_iterator.patch (5.0 KB) - added by thome 9 years ago.
classgroup_iterator_2.patch (4.4 KB) - added by ssharif 6 years ago.
classgroup_iterator_3.patch (5.4 KB) - added by thome 6 years ago.

Download all attachments as: .zip

Change History (23)

Changed 9 years ago by thome

comment:1 follow-up: Changed 7 years ago by roed

Is this waiting on something, or does it just need review?

comment:2 in reply to: ↑ 1 Changed 7 years ago by thome

Hi David,

Replying to roed:

Is this waiting on something, or does it just need review?

I think it just hasn't been reviewed by anyone.

Cheers,

E.

comment:3 Changed 7 years ago by roed

  • Status changed from new to needs_review

I'll mark it as needs review then. I don't have time to review it at the moment, though I may be able to eventually.

comment:4 Changed 7 years ago by jdemeyer

  • Status changed from needs_review to needs_work

There are some formatting problems. The "sage:" indentation should be left as it was:

TESTS::

    sage: ...

And you really should put a blank line between 2 functions, lines 213--214.

Also: please put your real name in the Author field on the ticket.

comment:5 Changed 6 years ago by AlexGhitza

  • Authors set to Emmanuel Thome
  • Description modified (diff)

Changed 6 years ago by ssharif

comment:6 Changed 6 years ago by ssharif

  • Keywords sd51 added
  • Milestone set to sage-5.12
  • Reviewers set to Shahed Sharif

Rebased to 5.11b3. This included adjusting line numbers. Also, last example had to be changed---the order of the class group elements is different.

Lastly, the new iterator __iter_inner__ needs a documentation string and a doc test

comment:7 Changed 6 years ago by davidloeffler

Shahed: I am puzzled by the constructs such as

[l for l in reflist[k]]

in the doctests in your patch. This is completely equivalent to reflist[k]. Why the list comprehension?

comment:8 follow-up: Changed 6 years ago by ssharif

Hi David,

This is unchanged from Emmanuel's patch, but I can simplify it in a new version. Also, it has been brought to my attention (by you and J. Cremona) that Pari produces the generators for the class group in a different order depending on the implementation. The given doctests were tested on my 32-bit system running sage 5.11b3; someone (probably me given time) will need to test this on a 64-bit system and put in the relevant doc test.

Shahed

comment:9 in reply to: ↑ 8 Changed 6 years ago by AlexGhitza

Replying to ssharif:

This is unchanged from Emmanuel's patch, but I can simplify it in a new version. Also, it has been brought to my attention (by you and J. Cremona) that Pari produces the generators for the class group in a different order depending on the implementation. The given doctests were tested on my 32-bit system running sage 5.11b3; someone (probably me given time) will need to test this on a 64-bit system and put in the relevant doc test.

Is it only the order that is different between 32- and 64-bit? In other words, if the output of the function is sorted, would 32- and 64-bit machines produce the same list of generators?

Changed 6 years ago by thome

comment:10 Changed 6 years ago by thome

Hi.

Thanks for your feedback. I just posted another version of the patch which fixes indentation, and adds documentation and doctests to _iter_inner_.

Looking back at this, and considering your warning on the generators returned by pari, I think that the doctest for the iterator is probably too fragile. What do you think ?

E.

comment:11 Changed 6 years ago by ssharif

Alex and Emmanuel:

Yes, the order is exactly the problem---the output of G.list() is permuted between the 2 cases. Also (though I haven't tested this on 64-bit), I believe the representative ideal in each class is also different; but this should not pose a problem, since G(I) for example returns the class of I. I tried using set() to fix the issue, but that didn't work; not sure why.

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 2 years ago by chapoton

  • Branch set to public/10184
  • Commit set to 568cc957900189761105c28e702f65d16fb805b0
  • Status changed from needs_work to needs_review

I made a branch.


New commits:

568cc95trac 10184 faster iteration over class groups

comment:16 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-8.1

comment:17 Changed 2 years ago by git

  • Commit changed from 568cc957900189761105c28e702f65d16fb805b0 to 9fe600ed3691d52d3e3f981e09283e1bf863ead7

Branch pushed to git repo; I updated commit sha1. New commits:

f0ccaa0Merge branch 'public/10184' of git://trac.sagemath.org/sage into public/class_group_iter-10184
9fe600eSome small reviewer changes.

comment:18 Changed 2 years ago by tscrim

  • Reviewers changed from Shahed Sharif to Shahed Sharif, Travis Scrimshaw

I made some small additional changes for speed and safety (in case inplace multiplication actually becomes inplace, really this does what the previous code was doing). This is really the same algorithm but using less multiplication. So if my changes look good, then positive review.

comment:19 Changed 2 years ago by chapoton

  • Reviewers changed from Shahed Sharif, Travis Scrimshaw to Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton
  • Status changed from needs_review to positive_review

Looks good to me. Let it be.

comment:20 Changed 2 years ago by vbraun

  • Branch changed from public/10184 to 9fe600ed3691d52d3e3f981e09283e1bf863ead7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.