#9390: is_galois_relative() not always right
------------------------------+---------------------------------------------
Reporter: arminstraub | Owner: davidloeffler
Type: defect | Status: needs_work
Priority: major | Milestone: sage-4.6.1
Component: number fields | Keywords: galois extension
Author: Francis Clarke | Upstream: N/A
Reviewer: Marco Streng | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Changes (by mstreng):
* status: needs_review => needs_work
Comment:
On which Sage version is this a speedup for is_galois_absolute?
With Sage 4.6.1.alpha2 and no patches
{{{
sage: K.<a>=NumberField(x^2+1)
sage: Kt.<t> = K[]
sage: L.<b> = K.extension(t^3-3*t-1)
sage: M.<c> = L.absolute_field()
sage: time L.is_galois_absolute()
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.00 s
True
sage: time L.is_galois_relative()
CPU times: user 0.08 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
False
sage: time M.is_galois()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
True
}}}
Same version, but with your patch:
{{{
sage: K.<a>=NumberField(x^2+1)
sage: Kt.<t> = K[]
sage: L.<b> = K.extension(t^3-3*t-1)
sage: M.<c> = L.absolute_field()
sage: time L.is_galois_absolute()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.04 s
True
sage: time L.is_galois_relative()
CPU times: user 0.04 s, sys: 0.01 s, total: 0.05 s
Wall time: 0.05 s
True
sage: time M.is_galois()
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
True
}}}
So you did correct (and apparently speed up) is_galois_relative. However,
it seems to slow down is_galois and is_galois_absolute. This gets worse if
you use is_galois multiple times for the same field, as the old version
uses cached data and your version doesn't:
Without patch:
{{{
sage: K.<b> = NumberField(cyclotomic_polynomial(11))
sage: time K.is_galois()
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
True
sage: time [K.is_galois() for i in range(500)];
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
}}}
With patch:
{{{
sage: K.<b> = NumberField(cyclotomic_polynomial(11))
sage: time K.is_galois()
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
True
sage: time [K.is_galois() for i in range(500)];
CPU times: user 11.66 s, sys: 0.05 s, total: 11.71 s
Wall time: 11.72 s
}}}
I'm very sorry for not noticing this earlier and for letting you do make
the changes you did after my first review.
On the other hand, my suggestion allowed for a good test of your code, as
is_galois is ubiquitous:
{{{
sage -t -long devel/sage/sage/schemes/elliptic_curves/gal_reps.py
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***
}}}
Maybe it is better to stick with the is_galois_relative correction only.
Also, if you know about cached methods, then perhaps you could make
is_galois_relative and is_galois_absolute cached while you're at it.
You can also make a distinction in is_galois between degree <= 11 (use the
old method) and degree > 11 (old method only works if KASH is installed,
use your method).
I suppose it is good to still let is_galois_absolute() simply call
absolute_field().is_galois().
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9390#comment:6>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
