Opened 3 years ago

Last modified 5 weeks ago

#29064 new enhancement

is_galois() / automorphisms() can be made faster

Reported by: Ricardo Buring Owned by:
Priority: major Milestone: sage-9.8
Component: number fields Keywords: is_galois, automorphisms
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Let K.<a> = NumberField(f). The method K.is_galois() does the following:

if self.degree() < 12:
    return self.galois_group(type='pari').order() == self.degree()
else:
    return len(self.automorphisms()) == self.degree()

The method K.automorphisms() defined here runs essentially the PARI code

nfgaloisconj(nfinit(f))

to compute the automorphisms, followed by some conversions. As just discussed on pari-users, it is faster to run instead

nfgaloisconj(f)

because nfinit computes the full factorization of the discriminant of the polynomial, which is not (always) needed.

The question is whether the nfinit(f) data is really needed for the conversions in K.automorphisms(). If it is not needed, then the optimization (that is, calling nfgaloisconj(f) instead) can be implemented there. If it is needed, then the optimization can be implemented in is_galois().

Either way, this would make is_galois() work faster for extensions of high degree.

The fact that it is currently slow was reported on Ask SageMath, which led me to investigate.

Change History (7)

comment:1 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.1sage-9.2

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.

comment:2 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:3 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:4 Changed 15 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:5 Changed 10 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:6 Changed 6 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:7 Changed 5 weeks ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.