class group iterator is too slow

[emmanuelthome]

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.

Component: number fields

Keywords: sd51

Author: Emmanuel Thome

Branch/Commit: 9fe600e

Reviewer: Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton

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

[emmanuelthome]

Attachment: classgroup_iterator.patch.gz

[roed314]

comment:1

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

[emmanuelthome]

comment:2

Hi David,

Replying to @roed314:

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

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

Cheers,

E.

[roed314]

comment:3

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.

[jdemeyer]

comment:4

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.

[aghitza]

Author: Emmanuel Thome

[sagetrac-ssharif]

Attachment: classgroup_iterator_2.patch.gz

[sagetrac-ssharif]

comment:6

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

[sagetrac-ssharif]

Reviewer: Shahed Sharif

[sagetrac-ssharif]

Changed keywords from none to sd51

[loefflerd]

comment:7

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?

[sagetrac-ssharif]

comment:8

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

[aghitza]

comment:9

Replying to @sagetrac-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?

[emmanuelthome]

comment:10

Attachment: classgroup_iterator_3.patch.gz

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.

[sagetrac-ssharif]

comment:11

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.

[fchapoton]

comment:15

I made a branch.

---

New commits:

568cc95

trac 10184 faster iteration over class groups

[fchapoton]

Branch: public/10184

[fchapoton]

Commit: 568cc95

[sagetrac-git]

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

f0ccaa0	Merge branch 'public/10184' of git://trac.sagemath.org/sage into public/class_group_iter-10184
9fe600e	Some small reviewer changes.

[sagetrac-git]

Changed commit from 568cc95 to 9fe600e

[tscrim]

comment:18

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.

[tscrim]

Changed reviewer from Shahed Sharif to Shahed Sharif, Travis Scrimshaw

[fchapoton]

comment:19

Looks good to me. Let it be.

[fchapoton]

Changed reviewer from Shahed Sharif, Travis Scrimshaw to Shahed Sharif, Travis Scrimshaw, Frédéric Chapoton

[vbraun]

Changed branch from public/10184 to 9fe600e