Revision history [back]

Hello!

I'm writing some code to solve by radicals a polynomial with solvable galois group, and an important part of doing this is the special case of a cyclic field extension.

I've implemented the algorithm (probably naively) and while it _works_, it's extremely slow to do a polynomial multiplication in the middle part of the algorithm. Granted, we end up with a polynomial of degree $n!$, but for $n=5$ I feel like it shouldn't be quite as slow as it is (though maybe I'm wrong). As an aside, if anybody knows of a more efficient algorithm, I would love to hear about it. I'm thinking of looking through the references of this paper, but I haven't had time yet.

Here's a minimal excerpt from the code which shows the part that runs slowly:

f = x^3 + x^2 - 2*x - 1 

n = f.degree(x)

# make a number field where w is a nth root of 1
K.<w> = CyclotomicField(n)

# make vars for the roots.
# a[i] = alpha_i
R = PolynomialRing(K, n, 'a')
a = R.gens()

v = sum([w^k * a[k] for k in range(n)])^3

# build the conjugates of v.
# it turns out we only need one from each conjugacy class,
# which keeps the degree down.

Sn = SymmetricGroup(n)

conjugates = []
for tau in Sn:
  if v * tau not in conjugates:
    conjugates += [v * tau]


S.<Y> = PolynomialRing(R)
psi = 1
for c in conjugates:
    psi *= (Y - c)

It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've also tried using prod(Y-c for c in conjugates) as well as product, rather than looping directly. I've tried making Y a symbolic variable rather than an element of a polynomial ring, but nothing seems to speed things up.

The first 10 multiplications or so happen without much hassle, but very quickly things start going very slowly. If anyone has any ideas, I would love to hear them!

Thanks in advance ^_^

Hello!

I'm writing some code to solve by radicals a polynomial with solvable galois group, and an important part of doing this is the special case of a cyclic field extension.

I've implemented the algorithm (probably naively) and while it _works_, it's extremely slow to do a polynomial multiplication in the middle part of the algorithm. Granted, we end up with a polynomial of degree $n!$, but for $n=5$ I feel like it shouldn't be quite as slow as it is (though maybe I'm wrong). As an aside, if anybody knows of a more efficient algorithm, I would love to hear about it. I'm thinking of looking through the references of this paper, but I haven't had time yet.

Here's a minimal excerpt from the code which shows the part that runs slowly:

f = x^3 + x^2 - 2*x - 1 

n = f.degree(x)

# make a number field where w is a nth root of 1
K.<w> = CyclotomicField(n)

# make vars for the roots.
# a[i] = alpha_i
R = PolynomialRing(K, n, 'a')
a = R.gens()

v = sum([w^k * a[k] for k in range(n)])^3

# build the conjugates of v.
# it turns out we only need one from each conjugacy class,
# which keeps the degree down.

Sn = SymmetricGroup(n)

conjugates = []
for tau in Sn:
  if v * tau not in conjugates:
    conjugates += [v * tau]


S.<Y> = PolynomialRing(R)
psi = 1
for c in conjugates:
    psi *= (Y - c)

It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've also tried using prod(Y-c for c in conjugates) as well as product, rather than looping directly. the explicit loop I have here. I've also tried making Y a symbolic variable rather than an element of a polynomial ring, but nothing seems to speed things up. has appreciably decreased the runtime.

The first 10 multiplications or so happen without much hassle, but very quickly things start going very slowly. If anyone has any ideas, I would love to hear them!

Thanks in advance ^_^