univariate polynomial gcd is slow forn number fields

[luisfe]

I have been recently working with univariate polynomials over number
fields and find the gcd very slow. At least for absolute number fields
Sage should behave better.

for QQ[x], gcd is also slow right now, but this is being addressed in
#4000

The issue is that for univariates polynomials over absolute number
fields, the implementation is just the generic one using Euclidean
algorithm. I tried passing to pari but I am afraid that the pari
coertion for these polynomials is incorrect. Is this a bug or a
feature?

I have implemented a correct pari coertion for this particular case
that allows to compute more cases of gcd. This could also be used for
gereal number fields by passing to an absolute number field.

I have also tried with Singular. For small extensions (degree <6) and
high degree polynomials singular seems to beat pari, for larger
extensions and smaller polynomial degrees pari seems better. I am not
sure if it is worthy to implement this, maybe with an option for the
user to choose the algorithm.

Any thoughts/feelings about this?

[daveloeffler]

On Mar 16, 8:29 pm, luisfe <lftab...@yahoo.es> wrote:
> The issue is that for univariates polynomials over absolute number
> fields, the implementation is just the generic one using Euclidean
> algorithm. I tried passing to pari but I am afraid that the pari
> coertion for these polynomials is incorrect. Is this a bug or a
> feature?

Can you give an example where polynomials are being passed incorrectly
to Pari? There are some known bugs in Pari's own factorisation
routines (fixed in Pari 2.3.5, which should hopefully be in the next
Sage release), but if there are problems translating between Pari and
Sage polynomials that's worrying.

David

[luisfe]

On 16 mar, 23:27, daveloeffler <dave.loeff...@gmail.com> wrote:
> Can you give an example where polynomials are being passed incorrectly
> to Pari? There are some known bugs in Pari's own factorisation
> routines (fixed in Pari 2.3.5, which should hopefully be in the next
> Sage release), but if there are problems translating between Pari and
> Sage polynomials that's worrying.

My error, there is no coercion for this class

sage: N=NumberField(x^2-2,'a')
sage: K=N['t']
sage: f=K.random_element()
sage: pari(f)
---------------------------------------------------------------------------
PariError Traceback (most recent call
last)

/home/luisfe/<ipython console> in <module>()

/opt/SAGE/sage/local/lib/python2.6/site-packages/sage/libs/pari/gen.so
in sage.libs.pari.gen.PariInstance.__call__ (sage/libs/pari/gen.c:
38930)()

/opt/SAGE/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/
polynomial_element.so in
sage.rings.polynomial.polynomial_element.Polynomial._pari_ (sage/rings/
polynomial/polynomial_element.c:26227)()

/opt/SAGE/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/
polynomial_element.so in
sage.rings.polynomial.polynomial_element.Polynomial._pari_with_name
(sage/rings/polynomial/polynomial_element.c:26353)()

/opt/SAGE/sage/local/lib/python2.6/site-packages/sage/libs/pari/gen.so
in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:44387)()

PariError: (8)

I think that I was first trying some naive transformation like
L = [pari(i) for i in f.list()]
add([L[i]*pari('t')^i for i in range(f.degree())])

And confused this with the actual coercion model.

[John Cremona]

For an example of how polynomials over number fields are converted
into pari polynomials, see
sage/rings/polynomial/polynomial_element.pyx, in the factor function.
This is the code already used to factor polynomials over number fields
by converting to pari. It is more complicated than one would like for
a couple of reasons: getting round bugs in pari's factorization of
non-monic polynomials, and variable names.

One has to be rather careful because of the variable names, here both
the name of the number field generator and the name of the polynomial
generator, since pari will only work if these are suitable.

John

> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org

[luisfe]

On 17 mar, 10:13, John Cremona <john.crem...@gmail.com> wrote:
> For an example of how polynomials over number fields are converted
> into pari polynomials, see
> sage/rings/polynomial/polynomial_element.pyx, in the factor function.
> This is the code already used to factor polynomials over number fields
> by converting to pari.  It is more complicated than one would like for
> a couple of reasons: getting round bugs in pari's factorization of
> non-monic polynomials, and variable names.
>
> One has to be rather careful because of the variable names, here both
> the name of the number field generator and the name of the polynomial
> generator, since pari will only work if these are suitable.
>
> John

This is now #8558, for the gcd, it seems that a simple:

sage: f = SomeField.random_element()
sage: f1 = pari([i._pari_('y') for i in f.list()]).Pol()

is a valid pari representation of f.

This, or something similar, should be implemented for absolute number
fields. I will look form problems this weekend and submit a patch.

[luisfe]

> sage: f1 = pari([i._pari_('y') for i in f.list()]).Pol()

well, this is use Polrev()