Opened 6 years ago
Closed 6 years ago
#18152 closed enhancement (fixed)
Universal Cyclotomic Field implementation using libgap
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  number fields  Keywords:  
Cc:  nthiery, stumpc5, tscrim, vbraun  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  b818c83 (Commits)  Commit:  b818c83bc329581c6af225dcf7b54d120e6e1e7c 
Dependencies:  #18153  Stopgaps: 
Description (last modified by )
Sage ships an implementation of the Universal Cyclotomic Field (in sage.rings.universal_cyclotomic_field.*
) that is slower and less reliable than what is in gap. We propose in this ticket an implementation based on libgap.
It fixes some issues about the old implementation:
 #14240: Universal cyclotomic field breaks for moderate order
 #16631: Universal Cyclotomic Field doesn't handle int and Integer the same
 #16130: Matrices over Universal Cyclotomic field failing to echelonize/inverse
 #17117: UniversalCyclotomicField elements considered real
And is about 10x faster (see comment:10) except for operations on very sparse elements with very large conductors (see e.g. comment:23, comment:27 and comment:28).
Possible follow up:
 switch to Cython
 implement dense matrices by wrapping libgap matrices (see also #16116)
 slowness in conjugation? #18207 (see also comment:28, this is unavoidable because gap uses a dense representation of elements)
 interface with libgap polynomials (#18266)
Attachments (1)
Change History (50)
comment:1 Changed 6 years ago by
 Description modified (diff)
comment:2 Changed 6 years ago by
 Branch set to u/vdelecroix/18152
 Dependencies set to #18153
comment:3 Changed 6 years ago by
 Commit set to 7d957347ccfeaba97438c92f6c04cbf79180f0fc
comment:4 Changed 6 years ago by
 Cc nthiery stumpc5 tscrim vbraun added
 Status changed from new to needs_review
comment:5 Changed 6 years ago by
 Description modified (diff)
comment:6 Changed 6 years ago by
 Commit changed from 7d957347ccfeaba97438c92f6c04cbf79180f0fc to e34e9ca6da48db87eb7ec594e6cc56e940a9aff2
comment:7 Changed 6 years ago by
 Commit changed from e34e9ca6da48db87eb7ec594e6cc56e940a9aff2 to 376bcc2dd953ebe96ed5594d99ce4155ccbd883c
Branch pushed to git repo; I updated commit sha1. New commits:
376bcc2  Trac 18152: fix constructor in rings.number_field.number_field

comment:8 Changed 6 years ago by
Now all test pass!
comment:9 Changed 6 years ago by
 Commit changed from 376bcc2dd953ebe96ed5594d99ce4155ccbd883c to e96846846f65b0a914d276f34725f97bfd974f4a
Branch pushed to git repo; I updated commit sha1. New commits:
e968468  Trac 18152: better cmp + 32 vs 64 bits in doctest

comment:10 Changed 6 years ago by
I did some concrete timings and the conclusion is that in all cases the new implementation is faster by a factor of at least x8 (and it can be up to x20).
comment:11 Changed 6 years ago by
 Commit changed from e96846846f65b0a914d276f34725f97bfd974f4a to 9dd74336bd11d44758340905055c37d04749051b
Branch pushed to git repo; I updated commit sha1. New commits:
9dd7433  Trac 12158: add a _sub_ method

comment:12 Changed 6 years ago by
 Commit changed from 9dd74336bd11d44758340905055c37d04749051b to e58f75501bdd8dfd4b20bc751a6040e5b10f0844
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e58f755  Trac 18152: add a _sub_ method

comment:13 Changed 6 years ago by
 Commit changed from e58f75501bdd8dfd4b20bc751a6040e5b10f0844 to e4a352468cf9c018b9bdf148a3de03793a111b9e
Branch pushed to git repo; I updated commit sha1. New commits:
e4a3524  Trac 18152: speedup (use X._add_(Y) instead of X+Y)

comment:14 followup: ↓ 15 Changed 6 years ago by
Hi!
Did you have a look at #16116? Does it improve also the multiplication of generic cyclotomic matrices?
JeanPhilippe
comment:15 in reply to: ↑ 14 Changed 6 years ago by
Hello JeanPhilippe,
Replying to jipilab:
Did you have a look at #16116? Does it improve also the multiplication of generic cyclotomic matrices?
I guess so. Should be ten times faster. But I copiedpasted the GAP documentation in the top of the file:
Arithmetical operations are quite expensive, so the use of internally represented cyclotomics is not recommended for doing arithmetic over number fields, such as calculations with matrices of cyclotomics.
Best, Vincent
comment:16 Changed 6 years ago by
 Description modified (diff)
comment:17 Changed 6 years ago by
 Milestone changed from sage6.6 to sage6.7
comment:18 followup: ↓ 19 Changed 6 years ago by
Hi there!
I kind of feel bad that you plan to remove that much code I wrote in weeks of work  but I guess that's the way it goes if there is something better...
Anyway my first question would be whether it is really desired to remove an algorithm from Sage and instead use the same algorithm from Gap? Don't you think that working on the cython part of my implementation (maybe even moving to plain C of some core functionality) could get it beyond the speed of the black box (from a Sage point of view) Gap implementation?
Secondly, I remember that I did quite some tests back when I implemented the UCF. And that in the end, the Sage implementation was slower on some parts, while faster on others (one I remember where Sage was quicker was the computation of the Galois conjugates of big elements, in case you want to test, one example might be E( 2^11 * 3^4 )
). I would really like to redo these tests, but haven't yet been able to get your branch running on my computer. I will get back once that worked out.
I also remember to have found a few bugs in the Gap implementation while implementing UCFs in Sage. That would also not be possible anymore when only relying on the implementation in Gap.
Cheers, Christian
comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 6 years ago by
Hello Christian,
Thanks for having a look!
Replying to stumpc5:
I kind of feel bad that you plan to remove that much code I wrote in weeks of work  but I guess that's the way it goes if there is something better...
Me too. I wondered if something were better with your code. But except the documentation I did not find any case were it was faster.
Anyway my first question would be whether it is really desired to remove an algorithm from Sage and instead use the same algorithm from Gap?
Sage should not reinvent the wheel. Gap is now interfaced as a fairly good level and we should try to maximize its usage at what it is good for.
That being said, it would makes sense to keep your implementation somewhere with more comparisons to the libgap implementation. Especially if you found that the Gap implementation has some bug! But I did not find any relevant example since all tests pass with my branch applied.
Don't you think that working on the cython part of my implementation (maybe even moving to plain C of some core functionality) could get it beyond the speed of the black box (from a Sage point of view) Gap implementation?
No idea. And I will not try. It is much more work than proposing what I did. And if you ask me what I would do if I want even more speed, I would link to Gap at an even lower level.
Secondly, I remember that I did quite some tests back when I implemented the UCF. And that in the end, the Sage implementation was slower on some parts, while faster on others (one I remember were Sage was quicker was the computation of the Galois conjugates of big elements, in case you want to test, one example might be
E( 2^11 * 3^4 )
). I would really like to redo these tests, but haven't yet been able to get your branch running on my computer. I will get back once that worked out.
Great! I will add this to the ucf_test.py
that I wrote. If you have other examples in mind, please propose. I am not sure it will make a difference now since big numbers with pexpect implies a lot of parsing and computation. With libgap it is not the case anymore.
I also remember to have found a few bugs in the Gap implementation while implementing UCFs in Sage. That would also not be possible anymore when only relying on the implementation in Gap.
You do not remember what they are? Did you report them to Gap?
Cheers Vincent
comment:20 in reply to: ↑ 19 Changed 6 years ago by
Hi Vincent,
Replying to vdelecroix:
Me too. I wondered if something were better with your code. But except the documentation I did not find any case were it was faster.
Did you already redo the Galois conjugate test which I remember was slower in Gap back then?
Great! I will add this to the
ucf_test.py
that I wrote. If you have other examples in mind, please propose. I am not sure it will make a difference now since big numbers with pexpect implies a lot of parsing and computation. With libgap it is not the case anymore.
I just did
sage: a = E( 2^11 * 3^4 ) sage: %time x = a.galois_conjugates() CPU times: user 5.52 s, sys: 159 ms, total: 5.68 s Wall time: 5.66 s sage: %time x = a.galois_conjugates() CPU times: user 6.81 s, sys: 170 ms, total: 6.98 s Wall time: 6.99 s
and compared it to
gap> a := E( 2^11 * 3^4 );; gap> L := PrimeResidues(165888);; gap> for i in L do > x := GaloisCyc(a,i); > od;
which I had running for 30 sec before I ctrcc'ed it. (I also believe that in Sage, a big portion of the time is spend of computing the list of coprimes.)
You do not remember what they are? Did you report them to Gap?
I did report them, and they were fixed.
Once I get your branch running, I try to get back other tests I did.
Cheers, Christian
comment:21 Changed 6 years ago by
Hi there!
I will also do some tests on the ticket and let you know.
One thing not to forget is also the number of tickets repaired by this new implementation. If the ticket repairs them and is faster... It's difficult to say no to that.
Grüsse, JP
comment:22 Changed 6 years ago by
Hello,
I pushed an experimental branch with both implementations at public/18152
. It is certain that most doctest fail but it is not the purpose. With it you can do
sage: UCF_native.<E_native> = UniversalCyclotomicField_native() sage: UCF_libgap.<E_libgap> = UniversalCyclotomicField_libgap() sage: UCF_native Universal Cyclotomic Field (native) sage: UCF_libgap Universal Cyclotomic Field (libgap)
and play around with both implementations.
Replying to 20: it is true that GaloisCyc
is slow in GAP (and it is not PrimeResidues
which takes time). I got with a little bit smaller example
sage: a = E_libgap( 2^9 * 3^4 ) sage: b = E_native( 2^9 * 3^4 ) sage: %time l = a.galois_conjugates() CPU times: user 6.92 s, sys: 4 ms, total: 6.92 s Wall time: 6.9 s sage: %time l = b.galois_conjugates() CPU times: user 352 ms, sys: 52 ms, total: 404 ms Wall time: 387 ms
Replying to 21: I do not think that the issues in the four tickets mentioned in the description are that big (and one of them has a fix).
Vincent
comment:23 Changed 6 years ago by
the branch runs now...
One issue I see is that it would if my code would not break because a few methods disappeared (such as field_order
and min_poly
. But this problem is minor and easy to fix  worst case is I update my code.
Redoing the following tests Sage
vs. libgap
:
1.
sage: a = E(5) sage: %timeit a.conjugate() 10000 loops, best of 3: 62.4 µs per loop
vs.
sage: a = E(5) sage: %timeit a.conjugate() 10000 loops, best of 3: 39.9 µs per loop
2.
sage: a = E( 2^10 ) sage: %timeit a.conjugate() 10000 loops, best of 3: 69.1 µs per loop
vs.
sage: sage: a = E( 2^10 ) sage: sage: %timeit a.conjugate() 10000 loops, best of 3: 75.1 µs per loop
3.
sage: a = E( 2^11 * 3^4 ) sage: %timeit a.conjugate() 10000 loops, best of 3: 118 µs per loop
vs.
sage: a = E( 2^11 * 3^4 ) sage: sage: %timeit a.conjugate() 100 loops, best of 3: 9.15 ms per loop
For the Galois conjugation, the libgap
implementation doesn't finish in very finite time, see also your example above.
comment:24 followup: ↓ 25 Changed 6 years ago by
conjugate
actually uses GaloisCyc
as in http://www.math.rwthaachen.de/~Greg.Gamble/gap4r3/doc/htm/ref/CHAP058.htm#SSEC002.4.
comment:25 in reply to: ↑ 24 ; followup: ↓ 26 Changed 6 years ago by
I opened #18207 for this slowness.
comment:26 in reply to: ↑ 25 Changed 6 years ago by
Replying to vdelecroix:
I opened #18207 for this slowness.
(most time seems to be spent in the function ConvertToBase
in cyclotom.c
)
comment:27 Changed 6 years ago by
On the other hand your code becomes slower when the element is more complicated
sage: a = sum(E_libgap( 2^8 * 3^4, i) for i in range(0, 2**12, 37)) sage: b = sum(E_native( 2^8 * 3^4, i) for i in range(0, 2**12, 37)) sage: %timeit _ = a.conjugate() 1000 loops, best of 3: 262 µs per loop sage: %timeit _ = b.conjugate() 1000 loops, best of 3: 793 µs per loop
So I would not say that conjugate
is slower.
comment:28 Changed 6 years ago by
Ok. The whole thing about conjugation just reflects the fact that Gap is using a dense representation where yours is sparse. In a.conjugate()
Gap just run through all coefficients, looking for the nonzero ones. For cyclotomic elements with large conductor and few nonzero coefficients, it makes a big difference.
Is there a use case for sparse cyclotomic elements with large conductor?
comment:29 followup: ↓ 30 Changed 6 years ago by
 Branch changed from u/vdelecroix/18152 to u/jipilab/18152
comment:30 in reply to: ↑ 29 ; followup: ↓ 35 Changed 6 years ago by
 Commit changed from e4a352468cf9c018b9bdf148a3de03793a111b9e to 29cb0a7663d9303022ce9251534e53a66fac11ec
 Reviewers set to JeanPhilippe Labbé
Hi,
So, all test pass on my 6.6.rc3. I went through the files and removed some trailing spaces and blank lines.
Replying to 28: I do not have a use case for sparse cyclotomic out of my head. It is also difficult to guess for the use I have in mind (mainly representation of Coxeter groups). Nonetheless, the matrices will not have large conductor. Thus I would say it is not too bad as it is for the purpose of Coxeter groups.
Going through the discussion, the current state of affairs is:
The following tickets are fixed: #14240, #16130, #16631, #17117
The following tickets are followups: #16116,#18207
The ticket looks good to me. It is well doctested with many examples. I would put positive review, nevertheless it would be good if someone else also go over the ticket too, Christian?
Best, JP
New commits:
591409b  Merge branch 'develop' into cyclotomic

29cb0a7  Corrected some blank lines and trailing spaces

comment:31 Changed 6 years ago by
There are merged conflicts on the last beta... Wait a minute, I am doing a rebase. I am doing a rebase.
comment:32 Changed 6 years ago by
Oops, my bad... Should have done it with the 6.6 ...
comment:33 Changed 6 years ago by
 Branch changed from u/jipilab/18152 to u/vdelecroix/18152
 Commit changed from 29cb0a7663d9303022ce9251534e53a66fac11ec to b8e369b03f2f444c6af07b77038610e43e625db8
Salut JeanPhillippe,
Thanks for your corrections! The branch is a fast forward. So you have to delete your previous branch. Your commit is preserved (it is now 08df5b4). I added three commits for better compatibility with the previous version:
 adding a
minpoly
andfield_order
methods as it was requested in comment:23 (see also #18266 for a potential improvement)  adding a
__neg__
(it is now faster to doE(3)
)
Vincent
New commits:
0c8af9b  Trac 18152: universal cyclotomic field using libgap

509acf7  Trac 18152: remove the old implementation

519dc00  Trac 18152: Fix coxeter group import

08df5b4  Corrected some blank lines and trailing spaces

890151f  Trac 18152: add a minpoly method to UCF elements

70f7895  Trac 18152: field_order as a deprecated alias of conductor

b8e369b  Trac 18152: __neg__ for UCF elements

comment:34 Changed 6 years ago by
 Description modified (diff)
comment:35 in reply to: ↑ 30 Changed 6 years ago by
comment:36 followup: ↓ 39 Changed 6 years ago by
But there is still the most important question: do we keep both versions (one being sparse the other being dense)?
Vincent
comment:37 Changed 6 years ago by
 Commit changed from b8e369b03f2f444c6af07b77038610e43e625db8 to 28c23ce280985112ea43f0bea36a76952a64ff8e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ccfc26e  Trac 18152: universal cyclotomic field using libgap

1b2d04a  Trac 18152: remove the old implementation

f3ef31a  Trac 18152: Fix coxeter group import

bb42614  Corrected some blank lines and trailing spaces

e3f714e  Trac 18152: add a minpoly method to UCF elements

8149677  Trac 18152: field_order as a deprecated alias of conductor

28c23ce  Trac 18152: __neg__ for UCF elements

comment:38 Changed 6 years ago by
All right. Updated on the very last 6.7.beta2!
comment:39 in reply to: ↑ 36 ; followup: ↓ 40 Changed 6 years ago by
Replying to vdelecroix:
But there is still the most important question: do we keep both versions (one being sparse the other being dense)?
IMO, we should keep both with the default being the dense.
comment:40 in reply to: ↑ 39 Changed 6 years ago by
Replying to tscrim:
Replying to vdelecroix:
But there is still the most important question: do we keep both versions (one being sparse the other being dense)?
IMO, we should keep both with the default being the dense.
I was implictely requiring arguments. We will not keep it just because you think it has to ;) I do have arguments for both sides, but as I am the ticket author I better not participate.
comment:41 Changed 6 years ago by
The main argument I could see for keeping the code around is as follow: The speed balance may evolve in the future, typically if free modules in Sage get optimized, or if new use cases emerge. Of course we could always revive the code then, but it would probably have rotten in the mean time, and we may have completely forgotten about it. It also can be used for testing purposes for comparing two independent implementations of UCF.
Those are not super strong arguments.
The main argument for not keeping it is that we would not want is wasting time maintaining it.
A sensible approach might be to write a brief comment at the beginning of the file / class stating something like: "at this point this code is not used much (see ...). If maintaining it becomes a bother in the future, it's ok to discard it".
comment:42 followup: ↓ 43 Changed 6 years ago by
Perhaps one could add a comment/warning in the beginning of the file also to mention that GAP uses a dense representation and a link to the current ticket.
If there is a use case popping up in the future we could revive the code as Nicolas mentioned.
@Christian: In your actual usage (not tests), is sparse faster than the current dense representation of GAP?
Also: I just updated to 6.7.beta3 on my computer and pulled the ticket. There was a small conflict in the file
src/doc/en/reference/rings_standard/index.rst
Should I push the resolution of the conflict here?
comment:43 in reply to: ↑ 42 Changed 6 years ago by
Replying to jipilab:
Also: I just updated to 6.7.beta3 on my computer and pulled the ticket. There was a small conflict in the file
src/doc/en/reference/rings_standard/index.rst
Should I push the resolution of the conflict here?
Yes please.
comment:44 Changed 6 years ago by
 Branch changed from u/vdelecroix/18152 to u/jipilab/18152
comment:45 Changed 6 years ago by
 Commit changed from 28c23ce280985112ea43f0bea36a76952a64ff8e to dc3de84809792bde5e2cde8c8c579f42496e0647
Et voilà!
New commits:
dc3de84  Merge branch 'u/vdelecroix/18152' of trac.sagemath.org:sage into SageMath6.7.b3

comment:46 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hi,
All test passed on 6.7.beta3!
Could you add a comment/warning at the beginning of the file mentioning the old implementation and a link to the ticket?
Perhaps it would be good to mention this in the documentation as well?
comment:47 Changed 6 years ago by
 Branch changed from u/jipilab/18152 to u/vdelecroix/18152
 Commit changed from dc3de84809792bde5e2cde8c8c579f42496e0647 to b818c83bc329581c6af225dcf7b54d120e6e1e7c
 Status changed from needs_work to needs_review
comment:48 Changed 6 years ago by
 Status changed from needs_review to positive_review
Hi,
This looks good to go as I see it.
I set it to positive review.
comment:49 Changed 6 years ago by
 Branch changed from u/vdelecroix/18152 to b818c83bc329581c6af225dcf7b54d120e6e1e7c
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Trac 18153: int and infinity from libgap
Trac 18152: implementation of UCF using libgap
Trac 18152: remove the old implementation
Trac 18152: Fix coxeter group import