ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 07 Aug 2021 02:14:30 +0200polynomial multiplication is unexpectedly slowhttps://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/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](https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf), 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 tried using `prod(Y-c for c in conjugates)` as well as `product`, rather than 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 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 ^_^Sat, 17 Jul 2021 09:29:29 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/Comment by dispo for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58332#post-id-58332As an aside, I wasn't able to get this particular implementation working efficiently, but I found an algorithm to more efficiently compute the object I was trying to construct in this question. In case it helps anyone else, you can find the details on [my blog](https://grossack.site/2021/08/06/cyclic-extensions.html).Sat, 07 Aug 2021 02:14:30 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58332#post-id-58332Comment by dispo for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58078#post-id-58078@mwageringel, @nbruin, @rburingThu, 22 Jul 2021 03:46:09 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58078#post-id-58078Comment by dispo for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58077#post-id-58077Thank you all for your ideas! I've modified my code to use the `S.flattening_morphism().codomain()`, and this has helped significantly (though not enough to get the degree $5$ case to terminate). As for using a balanced multiplication technique, I think `prod` already does that. According to `prod??`: `prod = balanced_list_prod(x, 0, n, recursion_cutoff)`. I suppose I can try to implement my own balanced product, but I feel like anything I do is unlikely to be better than the official version. Do you think it would be helpful if I edited my question to show the entire script I'm trying to run, rather than just this minimal part of the example? Computing `psi` is still the slowest part of the process, but perhaps I can compute it in stages, etc. based on what I'm doing next? Thanks again!Thu, 22 Jul 2021 03:45:46 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58077#post-id-58077Comment by mwageringel for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58064#post-id-58064`S` is a nested polynomial ring, for which multiplication is very slow in Sage. It uses the Karatsuba algorithm, which I think is a particularly bad choice if the coefficients are polynomials themselves.
Instead, you can compute the product in `S.flattening_morphism().codomain()`, the flattened polynomial ring @nbruin suggested, and then convert the result back to `S` using `S.flattening_morphism().section()`. This might be considerably faster, since it uses libsingular.Tue, 20 Jul 2021 21:04:47 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58064#post-id-58064Comment by nbruin for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58053#post-id-58053It's probably a good exercise to write down the expected number of terms in the coefficients of this degree 120 polynomial. Sure, a degree 120 polynomial over QQ usually quite workable (if the height of the coefficients remains moderate), but in your case the coefficients are polynomials themselves. If you multiply such polynomials together, you can get very many terms very quickly, and with a lot of cross terms. A few things you could try:
- use a balanced multiplication technique (try to multiply low-degree polynomials with low-degree ones, so that there's only one very expensive multiplication)
- flatten your polynomial ring to hopefully optimize the polynomial multiplications a bit.
I suspect you're just using a very computationally intensive method.Mon, 19 Jul 2021 18:54:35 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58053#post-id-58053Comment by dispo for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58042#post-id-58042@rburing -- that's exactly the next step. We know that the coefficients of `f` are symmetric polynomials in the roots `a[i]`. The problem is that `v` _isn't_ symmetric. However, once we multiply by all the conjugates of the symmetric group, then the coefficients of `psi` _are_ symmetric, and we can write them in terms of the elementary symmetric polynomials (that is, the coefficients of `f`). The references I've seen have all needed this step before we can actually evaluate the coefficients of `psi` down to constants, but there might be a way to avoid it? As for working in a polynomial ring over Q, is that more efficient? I'm thinking now about evaluating each coefficient by hand and reducing them one by one, rather than doing a full polynomial multiply and reducing after.Sat, 17 Jul 2021 22:45:40 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58042#post-id-58042Comment by rburing for <p>Hello!</p>
<p>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.</p>
<p>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 <a href="https://www.ams.org/journals/mcom/1999-68-226/S0025-5718-99-01060-1/S0025-5718-99-01060-1.pdf">this paper</a>, but I haven't had time yet.</p>
<p>Here's a minimal excerpt from the code which shows the part that runs slowly:</p>
<pre><code>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)
</code></pre>
<p>It took my desktop (Ryzen 5 3600) running overnight to fully compute this polynomial. I've tried using <code>prod(Y-c for c in conjugates)</code> as well as <code>product</code>, rather than the explicit loop I have here. I've also tried making <code>Y</code> a symbolic variable rather than an element of a polynomial ring, but nothing has appreciably decreased the runtime.</p>
<p>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! </p>
<p>Thanks in advance ^_^</p>
https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58036#post-id-58036Probably you should use somewhere that the `a[i]` are roots; currently they don't satisfy any non-trivial polynomial equations. Also you can work in a polynomial ring over Q if you add an extra variable for the root of unity. In any case, I would expect to see `reduce` somewhere.Sat, 17 Jul 2021 09:59:54 +0200https://ask.sagemath.org/question/58035/polynomial-multiplication-is-unexpectedly-slow/?comment=58036#post-id-58036