add a fast gcd algorithm for univariate polynomials over absolute number fields

[lftabera]

Question arised here,

http://groups.google.com/group/sage-devel/browse_thread/thread/0f5b029970e1a4e2/fcec7d0e35474fbd#fcec7d0e35474fbd

univariate gcd is performed using euclidean algorithm, which causes explosion of coefficients and is slow but for trivial examples.

For relative number fields, pass to an absolute representation. This may be slow. But for the cases where this is slow the current implementation may be unfeasible.

Depends on #14186 Depends on #15803 Depends on #15804

CC: @slel

Component: algebra

Keywords: gcd, pari, ntl, days94

Author: Luis Felipe Tabera Alonso

Branch/Commit: u/lftabera/ticket/8558 @ f16a49b

Reviewer: Jeroen Demeyer

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

[pjbruin]

comment:42

(I'm not sure if the merge conflict was caused by this ticket or one of its dependencies; I just reported what the patchbot told me.)

I don't really have time to review any of this at the moment, but I agree with earlier reviewers that this looks like a very nice addition. I was just wondering whether it would make sense to do this via a NumberField._gcd_univariate_polynomial() method as introduced by #13442. On the one hand, this would mean you didn't have to introduce new classes (potentially many of them: we have absolute and relative number fields, quadratic fields, cyclotomic fields, sparse and dense polynomials, who knows what other distinctions we'll have in the future). On the other hand, the code of this ticket has already been written and #13442 is still at needs_work, so it probably isn't worth the effort for now.

[pjbruin]

Changed work issues from does not merge with 6.2 to none

[lftabera]

comment:43

Thanks anyway, this made me update my local branches :)

The code is ok, but the branch of patches is a little mess due to my poor "git-fu". As of now I think that it is more important to get the dependencies merged, they are much simpler and would allow to prepare cleaner patches for this ticket.

Concerning #13442, I had in mind an implementation of these rings as in ticket #10591, so it would be better to have different classes for polynomials over number fields. The long term goal would be to have nice multiple extensions without the need of computing a primitive element for basic arithmetic, IMO it would be faster than using singular (cf. #9541).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f57b651 to add0e63

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

775f2c7	Merge tag '6.3' into u/lftabera/ticket/8558
a2622a9	Merge tag '6.4' into u/lftabera/ticket/8558
9da4eab	Merge branch 'master' into u/lftabera/lift_centered
406dca9	Fix import error
e81e7a0	Merge branch 'master' into u/lftabera/lift_centered
07f725e	Merge branch 'u/lftabera/lift_centered' into u/lftabera/ticket/8558
add0e63	Fix an exception that has changed.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from add0e63 to c89c734

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2f30718	Merge tag '6.5' into u/lftabera/lift_centered
fff5565	Merge tag '6.6' into u/lftabera/lift_centered
7a5e891	Merge tag '6.7' into u/lftabera/lift_centered
3dd232b	Ticket 15804
c89c734	Merge branch 'u/lftabera/lift_centered' into u/lftabera/ticket/8558

[lftabera]

comment:48

After so much time, I want to check if the code needs refactoring.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c89c734 to 43d1c12

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f6a168e	Merge branch 'develop' into u/lftabera/ticket/8558
6c2dca3	Merge branch 'develop' into u/lftabera/ticket/8558
43d1c12	- Make the code work with 7.1.beta4

[lftabera]

comment:50

It works again with latest beta

[videlec]

comment:51

• .. NOTE: -> .. NOTE::

• In the docstring of "lift_to_poly_QQ" it is written that "it may fail with a ValueError exception.". But there is only an example which gives an "ArithmeticError". So either fix the note or add a doctest.

• you should do more typing in Cython file (with cdef). For example, cdef list lifted = []. It will help cython to speed up loops including the loops. And if I am not mistaken, this syntax for 0 <= i < r is equivalent to for i in range(r) which is more Python friendly.

• the name lift_to_poly_QQ looks strange to me. What does the QQ stands for?

• Could you provide more examples why the situation is it better with this new algorithm?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 43d1c12 to eef9fe1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a897e89	Merge tag '7.3.beta7' into u/lftabera/ticket/8558
8eaf6b8	Add more cdef variables
eef9fe1	Fixed examples docstring.

[lftabera]

comment:53

• I have added mor cdef, however, I cannot do that in polynomial_number_field since the class inherist from a python class. I was not able to cdef, rings or number field elements. The latter has at least two classes and I was not able to cdef the common parent.

• I have fixed types, more verbose method names, clean unusued variables.

• modular method can be further improved for high degree using half-gcd algorithms in ntl.

• Some more examples:

Pari seems to use either Euclid or some subresultant variation. I would expect pari to perform better when the gcd is big with respect to the degree of the inputs. Or, when the input has small degree.

The polynomials are generated with K.random_element() so small coefficients. This benefits pari.

Small extension, not impressing except for huge polynomials

sage: K=QQ[I]['x']

deg f, deg g, deg gcd, timeit pari, timeit modular
2, 2, 0, 111 µs, 176 µs
2, 2, 1, 173 µs, 360 µs
2, 2, 2, 185 µs, 466 µs

100, 100, 0, 30.6 ms, 7.06 ms
100, 100, 50, 22.5 ms, 34.7 ms
100, 100, 100, 4.82 ms, 6.58 ms

300, 300, 0, 1.8 s, 45.1 ms
300, 300, 150, 534 ms, 201 ms
300, 300, 300, 13.3 ms, 11.3 ms

1000, 1000, 100, 2min 52s, 2.07 s

A degree 3, easy extension

sage: R=NumberField(x^3-2,'a')['x']

deg f, deg g, deg gcd, timeit pari, timeit modular
2, 2, 0, 163 µs, 243 µs
2, 2, 1, 239 µs, 597 µs
2, 2, 2, 257 µs, 587 µs

100, 100, 0, 19 s, 11.2 ms (1000x faster)
100, 100, 50, 8.6 s, 47.3 ms (100x faster)
100, 100, 100, 6.57 ms, 11.9 ms (2x slower)

300, 300, 150, > 600 s, 403 ms

Tu support my claim that big coefficients benefits modular

sage: K=QQ[I]['x']
sage: f=K.random_element(2,10**10)

100, 100, 0, 282 ms, 6.92 ms
100, 100, 50, 117 ms, 15.4 ms
100, 100, 100, 4.69 ms, 5.01 ms

[lftabera]

comment:54

lift methods still need better documentation according to #18

[JohnCremona]

comment:55

If I were a pari developer reasing this, I would ask: why not implement the algorithm in pari itself, rather than in Sage?

[lftabera]

comment:56

I am not a pari developer, it would certainly benefit more people than an implementation in Sage. I thought about an implementation in ntl, but I do not touch C++ since 15 years ago. Flint would also be a good place to put a similar code.

According to the documentation:

gcd uses:

• integers: use modified right-shift binary ("plus-minus" variant).

• univariate polynomials with coefficients in the same number field (in particular rational): use modular gcd algorithm.

• general polynomials: use the subresultant algorithm if coefficient explosion is likely (non modular coefficients).

So, it may be the case that we are not translating polynomials to the correct pari setting and so I get bad timings? It may be the case, in order not to compute the discriminant of the number field we are dealing with...

[JohnCremona]

comment:57

One thing to watch when comparing timings with pari is that when Sage calls pari to compute class number s and units in a number field, unless Proof=False it assumes no hypothesis (like GRH) so is often a lot slower than the same thing done in pari, where the default is to assume everything (and you can ask for certification later). This should be as issue if you only do basic number field arithmetic, but if you do anything which requires knowing the units or class group it can be quite significant. You might want to try setting Proof=False in Sage and seeing if your timings change.

[lftabera]

comment:58

It it is not that, I only need basic arithmetic, at most, pari could be interested in the discriminant, but I am working in QQ[I] in my examples. Which should be easy.

I have tried to write polynomials in pure gp as

f= Mod(3*y,y<sup>2-1)*x</sup>2+Mod(1,y<sup>2-1)*x+Mod(y,y</sup>2-1)

or as

w=quadgen(-4)
f= 3*w*x^2+1*x+w

in both cases I get bad timing. Reading the documentation now to see how to deal with polynomials with number field coefficients in pari...

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from eef9fe1 to 5cfbce8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b89dac9	Merge tag '7.3.beta8' into u/lftabera/ticket/8558
9685a00	Minor documentation fix
5cfbce8	Be more conservative with the primes.

[lftabera]

comment:60

It looks that Pari is not really using a modular algorithm...

In any case, I have fixed the documentation, I have also fixed some heuristic assumptions about the primes. Do not use proof=False and be more conservative about the size of the primes. In principle, with proof=False we could try a composite number such that the gcd in the residue ring success but some prime factors are good and some are bad. Not sure if this is possible. Also, chinese remainder could potentially fail, in this case I think that can only happens if the gcd is already unfeasible by any method. But let's be conservative and use only failproof methods.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

41d24b4	Merge tag '8.1.beta5' into u/lftabera/ticket/8558
41f33f5	Merge tag '8.2.beta6' into u/lftabera/ticket/8558
02639b7	Merge tag '8.2.beta7' into u/lftabera/ticket/8558

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5cfbce8 to 02639b7

[lftabera]

Changed keywords from gcd, pari, ntl to gcd, pari, ntl, days94

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 02639b7 to b894a30

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e08165b	Merge branch 'develop' into u/lftabera/ticket/8558
9c94c68	One should not use a method only inteded for doctest
5584a90	Moved the bibliography to the main reference file.
b894a30	Fix doctest error in rational_reconstruction

[lftabera]

comment:64

This code uses ntl ZZ_pEX while it should use the faster lzz_pEX for word-sized primes.

[embray]

comment:66

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:67

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3c40475	Merge tag '8.6' into u/lftabera/ticket/8558
8c678f6	Merge branch 'develop' into u/lftabera/ticket/8558

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b894a30 to 8c678f6

[lftabera]

comment:69

lzz_pEX is not interfaced in Sage, so that should be a different ticket.

Still, with latest ntl library the code should be even much faster since the modular gcds are subquadratic for these types.

develop merged.

[slel]

comment:70

Replying to @lftabera:

lzz_pEX is not interfaced in Sage, so that should be a different ticket.

There is #8109 for that.

[embray]

comment:71

Ticket retargeted after milestone closed

[mkoeppe]

comment:72

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[seblabbe]

comment:73

The branch has conflict with the sage develop branch since at least 9.1.beta7 according to the patchbot reports.

[mkoeppe]

comment:75

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:76

Setting a new milestone for this ticket based on a cursory review.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cac17c2	Merge tag '8.9' into u/lftabera/ticket/8558
83d1864	Merge tag '9.0' into u/lftabera/ticket/8558
b27ae79	Merge tag '9.1' into u/lftabera/ticket/8558
58fc36c	Merge tag '9.2' into u/lftabera/ticket/8558
f16a49b	Merge branch 'develop' into u/lftabera/ticket/8558

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8c678f6 to f16a49b