Universal Cyclotomic Field implementation using libgap #18152

videlec · 2015-04-09T21:41:20Z

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:

Universal cyclotomic field breaks for moderate order #14240: Universal cyclotomic field breaks for moderate order
Universal Cyclotomic Field doesn't handle int and Integer the same #16631: Universal Cyclotomic Field doesn't handle int and Integer the same
Matrices over Universal Cyclotomic field failing to echelonize/inverse #16130: Matrices over Universal Cyclotomic field failing to echelonize/inverse
UniversalCyclotomicField elements considered real #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 Multiplication of dense cyclotomic matrices should be faster #16116)
slowness in conjugation? Galois conjugation of cyclotomics is slow in GAP #18207 (see also comment:28, this is unavoidable because gap uses a dense representation of elements)
interface with libgap polynomials (Conversion from Sage polynomial to gap/libgap #18266)

Depends on #18153

CC: @nthiery @stumpc5 @tscrim @vbraun

Component: number fields

Author: Vincent Delecroix

Branch/Commit: b818c83

Reviewer: Jean-Philippe Labbé

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

The text was updated successfully, but these errors were encountered:

videlec · 2015-04-09T22:22:53Z

Dependencies: #18153

videlec · 2015-04-09T22:22:53Z

Branch: u/vdelecroix/18152

sagetrac-git · 2015-04-09T22:24:31Z

Commit: 7d95734

sagetrac-git · 2015-04-09T22:24:31Z

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

`31385f3`	`Trac 18153: int and infinity from libgap`
`23eb30c`	`Trac 18152: implementation of UCF using libgap`
`99c8d80`	`Trac 18152: remove the old implementation`
`7d95734`	`Trac 18152: Fix coxeter group import`

videlec · 2015-04-09T22:26:02Z

New commits:

`31385f3`	`Trac 18153: int and infinity from libgap`
`23eb30c`	`Trac 18152: implementation of UCF using libgap`
`99c8d80`	`Trac 18152: remove the old implementation`
`7d95734`	`Trac 18152: Fix coxeter group import`

sagetrac-git · 2015-04-10T04:54:41Z

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

`36fb6e5`	Trac 18153: better `__int__` and add support for -infinity
`e34e9ca`	`Trac 18152: fix documentation`

sagetrac-git · 2015-04-10T04:54:41Z

Changed commit from 7d95734 to e34e9ca

sagetrac-git · 2015-04-10T06:26:29Z

Changed commit from e34e9ca to 376bcc2

sagetrac-git · 2015-04-10T06:26:29Z

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

`376bcc2`	`Trac 18152: fix constructor in rings.number_field.number_field`

videlec · 2015-04-10T07:14:32Z

comment:8

Now all test pass!

sagetrac-git · 2015-04-10T11:26:58Z

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

`e968468`	`Trac 18152: better cmp + 32 vs 64 bits in doctest`

sagetrac-git · 2015-04-10T11:26:58Z

Changed commit from 376bcc2 to e968468

videlec · 2015-04-10T15:11:30Z

A test file to compare timings

videlec · 2015-04-10T15:12:20Z

comment:10

Attachment: ucf_test.py.gz

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).

sagetrac-git · 2015-04-10T15:21:13Z

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

`9dd7433`	Trac 12158: add a `_sub_` method

sagetrac-git · 2015-04-10T15:21:13Z

Changed commit from e968468 to 9dd7433

sagetrac-git · 2015-04-10T15:21:33Z

Changed commit from 9dd7433 to e58f755

sagetrac-git · 2015-04-10T15:21:33Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`e58f755`	Trac 18152: add a `_sub_` method

sagetrac-git · 2015-04-10T18:00:50Z

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

`e4a3524`	`Trac 18152: speedup (use X._add_(Y) instead of X+Y)`

sagetrac-git · 2015-04-10T18:00:50Z

Changed commit from e58f755 to e4a3524

jplab · 2015-04-11T06:13:54Z

comment:14

Hi!

Did you have a look at #16116? Does it improve also the multiplication of generic cyclotomic matrices?

Jean-Philippe

videlec · 2015-04-11T08:38:12Z

comment:15

Hello Jean-Philippe,

Replying to @jplab:

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 copied-pasted 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

sagetrac-git · 2015-04-21T15:31:01Z

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

videlec · 2015-04-21T15:31:40Z

comment:38

All right. Updated on the very last 6.7.beta2!

tscrim · 2015-04-21T16:01:38Z

comment:39

Replying to @videlec:

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.

videlec · 2015-04-21T16:05:42Z

comment:40

Replying to @tscrim:

Replying to @videlec:

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.

nthiery · 2015-04-22T09:18:36Z

comment:41

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".

jplab · 2015-04-29T09:26:30Z

comment:42

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?

videlec · 2015-04-29T09:29:27Z

comment:43

Replying to @jplab:

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.

jplab · 2015-04-29T16:08:40Z

Changed branch from u/vdelecroix/18152 to u/jipilab/18152

jplab · 2015-04-29T16:09:16Z

Changed commit from 28c23ce to dc3de84

jplab · 2015-04-29T16:09:16Z

comment:45

Et voilà!

New commits:

`dc3de84`	`Merge branch 'u/vdelecroix/18152' of trac.sagemath.org:sage into SageMath6.7.b3`

jplab · 2015-04-30T08:00:14Z

comment:46

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?

videlec · 2015-04-30T12:20:14Z

Changed commit from dc3de84 to b818c83

videlec · 2015-04-30T12:20:14Z

Changed branch from u/jipilab/18152 to u/vdelecroix/18152

videlec · 2015-04-30T12:20:14Z

comment:47

Done. I also simplified some imports.

New commits:

`ba5ed57`	`Trac 18152: add a note about the change of implementation`
`b818c83`	`Trac 18152: remove and simplify some imports`

jplab · 2015-05-06T09:02:21Z

comment:48

Hi,

This looks good to go as I see it.

I set it to positive review.

vbraun · 2015-05-06T23:57:45Z

Changed branch from u/vdelecroix/18152 to b818c83

videlec added this to the sage-6.6 milestone Apr 9, 2015

videlec added c: number fields labels Apr 9, 2015

This comment has been minimized.

Sign in to view

videlec added the s: needs review label Apr 9, 2015

This comment has been minimized.

Sign in to view

jplab added s: needs work and removed s: needs review labels Apr 30, 2015

videlec added s: needs review and removed s: needs work labels Apr 30, 2015

jplab added s: positive review and removed s: needs review labels May 6, 2015

vbraun removed the s: positive review label May 6, 2015

vbraun closed this as completed in 27a6e09 May 6, 2015

nthiery mentioned this issue Dec 29, 2022

Refactor Coxeter groups as matrix groups and non crystallographic root systems #15703

Open

videlec mentioned this issue Apr 11, 2015

Multiplication of dense cyclotomic matrices should be faster #16116

Open

tscrim mentioned this issue Nov 2, 2015

Create a class for Coxeter matrices and types #17798

Closed

videlec mentioned this issue Dec 29, 2022

Galois conjugation of cyclotomics is slow in GAP #18207

Open

stumpc5 mentioned this issue Jun 8, 2015

Galois conjugates in universal cyclotomic field miss the previously existing parameter m #18620

Closed

fchapoton mentioned this issue Nov 29, 2018

remove some deprecated lazy imports #26772

Closed

Universal Cyclotomic Field implementation using libgap #18152

Universal Cyclotomic Field implementation using libgap #18152

Comments

videlec commented Apr 9, 2015

This comment has been minimized.

videlec commented Apr 9, 2015

videlec commented Apr 9, 2015

sagetrac-git mannequin commented Apr 9, 2015

sagetrac-git mannequin commented Apr 9, 2015

videlec commented Apr 9, 2015

This comment has been minimized.

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

videlec commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

videlec commented Apr 10, 2015

videlec commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

sagetrac-git mannequin commented Apr 10, 2015

jplab commented Apr 11, 2015

videlec commented Apr 11, 2015

This comment has been minimized.

sagetrac-git mannequin commented Apr 21, 2015

videlec commented Apr 21, 2015

tscrim commented Apr 21, 2015

videlec commented Apr 21, 2015

nthiery commented Apr 22, 2015

jplab commented Apr 29, 2015

videlec commented Apr 29, 2015

jplab commented Apr 29, 2015

jplab commented Apr 29, 2015

jplab commented Apr 29, 2015

jplab commented Apr 30, 2015

videlec commented Apr 30, 2015

videlec commented Apr 30, 2015

videlec commented Apr 30, 2015

jplab commented May 6, 2015

vbraun commented May 6, 2015