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

[lftabera]

Attachment: 13911.patch.gz

[lftabera]

comment:2

The pari algorithm is not fast enough. I have implemented a modular algorithm using ntl.

The patch needs doctest and integration in sage (it is, right now, a separate function).

It adds a new function modular_gcd

To test it, apply the patch and

from sage.rings.polynomial.polynomial_absolute_number_field import modular_gcd

Some timmings: (800 Mhz i386 linux, 1Gb ram)

sage: N.<a>=NumberField(x^3 -123)         
sage: K.<t>=N[]                           
sage: f=K.random_element(degree=2)        
sage: g1=K.random_element(degree=15)      
sage: g2=K.random_element(degree=15)      
sage: h1=f*g1                             
sage: h2=f*g2                             
sage: %time modular_gcd(h1,h2,'pari')     
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.31 s                                 
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t - 1312/663609*a^2 + 3026/221203*a + 66060/221203
sage: %time modular_gcd(h1,h2)                                                                                
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s                                                            
Wall time: 0.12 s                                                                                             
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t - 1312/663609*a^2 + 3026/221203*a + 66060/221203
sage: %time modular_gcd(h1,h2,'euclidean')                                                                    
CPU times: user 11.28 s, sys: 0.05 s, total: 11.33 s                                                          
Wall time: 12.21 s                                                                                            
t^2 + (-35396/663609*a^2 + 92498/663609*a + 1750733/663609)*t - 1312/663609*a^2 + 3026/221203*a + 66060/221203

sage: N.<a>=NumberField(x^10 - 123)
sage: K.<t>=N[]
sage: f=K.random_element(degree=2)
sage: g1=K.random_element(degree=15)
sage: g2=K.random_element(degree=15)
sage: h1=f*g1
sage: h2=f*g2
sage: %time l=modular_gcd(h1,h2,'pari')
CPU times: user 30.06 s, sys: 0.02 s, total: 30.07 s
Wall time: 32.15 s
sage: %time l=modular_gcd(h1,h2,'modular')
CPU times: user 0.43 s, sys: 0.00 s, total: 0.43 s
Wall time: 0.47 s

[lftabera]

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

[lftabera]

comment:3

Here there is a cleaner patch.

The patch adds a new class of univariate polynomials whose ground field is an absolute number field. There is a new _gcd method for this class. It actually implements several approaches to the modular gcd algorithm:

Langemyr-McCallum algorithm
Encarnacion
a mixture of the two previous (default)

moreover, a call to pari method and the old Euclidean method.

I think that there should be only one modular algorithm, but, as usual, there are cases in which any of them beats the others. So suggestions are welcome. It should probably be Encarnacion or the mixture of boths

some timmings for harder problems:

sage: N = NumberField(ZZ[x].random_element(15).monic(),'a')    
sage: K = N[x]
sage: f = K.random_element(100)
sage: g1 = K.random_element(100)
sage: g2 = K.random_element(100)
sage: g1 *= f
sage: g2 *= f
sage: %time _=gcd(g1,g2)
CPU times: user 7.32 s, sys: 0.02 s, total: 7.34 s
Wall time: 7.42 s

This example with the old implementation or even pari is unfeasible.

[lftabera]

comment:4

• Improved documentation
• Eliminated an improvement in a function that hos nothing to do with the ticket

[lftabera]

Author: Luis Felipe Tabera Alonso

[lftabera]

comment:5

Added the method also for number fields of degree 1 using Flint in this special case

[lftabera]

comment:6

Attachment: 14371.patch.gz

Now that #4000 has possitive review, I raise the priority of this one.

Updated patch to work in 4.5.3

Now, it works also for relative number fields, passing to an absolute representation and performing there the computations. This is not optimal but it is usable.

If the extension of the field is one, then the gcd of QQ[x] is used wich is faster.

[lftabera]

Attachment: trac-5885.patch.gz

[JohnCremona]

comment:7

I can confirm that the patch applies fine to 4.6.rc0 and all tests (including long) pass.

There are some minor problems with the documentation (just punctuation) -- now I am studying the code, since this looks like very useful functionality!

[lftabera]

comment:8

Some clean in the documentation, reorder of the methods (methods after the classes of the file) and a couple of small bugs (honor the method option for relative fields and duplicated code for degree 1 extensions). Rename correctly the patch.

Apply: trac-8558.patch

Try new buildbot :)

[loefflerd]

comment:9

Apply trac-8558.patch

(I think such messages have to come after the patch is uploaded)

[lftabera]

avoid next_prime, better exceptions

[lftabera]

comment:10

Attachment: trac-8558.patch.gz

[malb]

comment:11

Hi, I don't know much about fast computation in polynomial rings over number fields. However, I'm wondering why you have this bias towards functions as opposed to methods? For example, lift_pm looks like it should be a method on p instead of a function? Perhaps the same applies to the gcd functions? Or am I missing something?

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

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 8c678f6 to f16a49b