On 5 January 2017 at 18:15, Nils Bruin <[email protected]> wrote: > On Thursday, January 5, 2017 at 2:27:06 AM UTC-8, John Cremona wrote: >> >> I have a degree 5 polynomial whose Galois group is large (S_5): >> >> sage: x = polygen(QQ) >> sage: f = x^5 - 6*x^3 - x^2 + 6*x - 1 >> >> I can compute its splitting field easily, thanks to code written by >> Jeroen Demeyer I believe: >> >> sage: %time L = f.splitting_field(names='b') >> CPU times: user 1min 1s, sys: 272 ms, total: 1min 2s >> Wall time: 1min 2s >> >> Note that the result is a number field of degree 120. However, if I >> form the degree 5 field by adjoining one root of f first, and then ask >> for its Galois closure, it takes very much longer: >> >> sage: K.<a> = NumberField(f) >> sage: %time L = K.galois_closure(names='b') >> CPU times: user 15min 24s, sys: 36 ms, total: 15min 24s >> Wall time: 15min 25s >> >> Any idea why? Essentailly the only difference I can see is that in >> the second case the polynomial f is first base-changed to K and then >> the method splitting_field is applied to that, but it is not clear to >> me why that should be slower since I think the first step of computing >> f.splitting_field() would do just that anyway? > > > I haven't looked at the code but that's certainly not the only way to arrive > at the galois closure. Some smart resolvent manipulations could give you (a > multiple of) the minimal polynomial of a generator of the galois closure. > You would never be factoring polynomials that are explicitly given over a > proper extension. I don't know if that would be faster, but polynomial > aritmetic over ZZ and QQ is so much more optimized than over number fields, > it wouldn't surprise me if there is a good range where it is.
I was basing my remarks on what I remembered from having reviewed Jeroen Demeyer's code for splitting fields. And hoping he might have something to say! > >> >> It would be very convenient for me to gain this speedup, by changing >> the method galois_closure() if necessary. I already plan to make the >> latter a @cached_method. > > > I'm tempted to say: beware of memory leaks. Caching an extension on the base > field would probably imply that both fields are now participating in a > reference cycle, anchored in the global UniqueRepresentation cache, so they > would be uncollectable by the GC. I see. But in a situation where I was processing 500 elliptic curves each defined over a quintic field whose galois closure took 15 minutes to compute, I think you can understand why I added the cache decorator in my local development branch! It is not so bad now I am using splitting field. By the way, this is at line 885 of https://github.com/sagemath/sage/blob/develop/src/sage/schemes/elliptic_curves/gal_reps_number_field.py, where replacing Kgal = K.galois_closure('b') by Kgal = K.defining_polynomial().splitting_field('b') had a rather dranmatic effect! > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" 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-support. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-support" 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-support. For more options, visit https://groups.google.com/d/optout.
