#20749: Use PARI nfeltup() for inclusion of base field into relative number
field
-------------------------------------+-------------------------------------
Reporter: pbruin | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.3
Component: number fields | Resolution:
Keywords: relative number | Merged in:
field pari | Reviewers: Stephan Ehlen
Authors: Peter Bruin | Work issues:
Report Upstream: N/A | Commit:
Branch: | 9f1d90be8d3f05b6d5de8ee75e36e6d17ad52095
u/pbruin/20749-pari_nfeltup | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ehlen):
Replying to [comment:7 pbruin]:
> See #20759; we can postpone the call to `_nf_nfzk`, but we should do it
at the latest when first mapping an element of the base field into the
relative field, since there is no way to predict how often this is going
to be done.
OK, #20759 is a good idea and I really think that your changes are great.
However, the time spend in {{{nf_nfzk}}} is really a lot of time when the
degree of the extension increases (and maybe it depends on the absolute
degree in fact?). When investigating the crashes in #20693, I found the
following example, which causes problems and makes it very hard to
initialize a relative extension which only took a few seconds in sage 7.1:
{{{
sage: K.<zeta22> = CyclotomicField(22)
sage: x = polygen(K)
sage: f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 +
4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 +
(181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5
- 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 +
13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3
+ 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 +
9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 +
17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9
+ 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 -
17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 +
(118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 +
66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 -
93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 -
234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 +
388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 -
1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 -
12672*zeta22^2 + 12672*zeta22 - 1196096
L.<a> = K.extension(f)
}}}
First of all, this takes 3.569s in sage 7.1. In your branch, I get after
quite a while (a few minutes):
{{{
PariError: the PARI stack overflows (current size: 2147483648; maximum
size: 2147483648)
You can use pari.allocatemem() to change the stack size and try again
}}}
Then I did:
{{{
sage: pari.allocatemem(2*2147483648)
}}}
and now it works but takes '''very''' long: 525.961s!
Of course, working with elements in the extension became now more
manageable:
In sage 7.1, we get
{{{
sage: %time r=L(K.gen())
CPU times: user 7.68 ms, sys: 84 µs, total: 7.77 ms
Wall time: 7.77 ms
sage: %time r=L(K.gen()^2)
CPU times: user 3.97 s, sys: 1.56 ms, total: 3.97 s
Wall time: 3.97 s
sage: %time r=L(K.gen()^3)
CPU times: user 7.96 s, sys: 8.36 ms, total: 7.96 s
Wall time: 7.97 s
}}}
and in your branch
{{{
sage: %time r=L(K.gen())
CPU times: user 19 ms, sys: 97 µs, total: 19.1 ms
Wall time: 19.1 ms
sage: %time r=L(K.gen()^2)
CPU times: user 19.1 ms, sys: 505 µs, total: 19.6 ms
Wall time: 19.6 ms
sage: %time r=L(K.gen()^3)
CPU times: user 19.1 ms, sys: 34 µs, total: 19.1 ms
Wall time: 19.1 ms
}}}
However, even if _nf_nfzk would be called later, waiting almost 9 minutes
for a degree 9 extension seems ridiculously long.
Don't we have any chance to improve this? Or is this a known issue in
pari?
Also, the stack overflow should somehow be taken care of, don't you think?
--
Ticket URL: <http://trac.sagemath.org/ticket/20749#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
