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.Thu, 27 May 2021 21:08:55 +0200Performance of PolynomialRing evaluationhttps://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/ Hi,
I am having a performance issue with the evaluation of a PolynomialRing which I find suspicious. I would like to understand if I am doing things correctly here.
The polynomial is calculated as a function of a set of matrices, whose logic is not relevant here.
In particular, the polynomial I am benchmarking has 16 variables and is 15.000 terms long, which means it has (on average) 120.000 multiplications and 15.000 sums for a total of 135.000 operations.
On my laptop, a single evaluation takes 4 seconds, in other words a single operation every 30 us.
This seems weird, given the speed of modern computers and especially compared to the speed of calculating the polynomial - the *representativeSetPoly* in the code. Indeed I was expecting that part to be slower than the verification.
Is there a way I can evaluate the polynomial in a more efficient way (the verification part in the code)? I am attaching a code snippet to reproduce the issue
Thanks in advance!
import time
import numpy as np
from sage.all import *
from tqdm import tqdm
WORKLOAD_DIM = 16
PRIME_NUM = 109211909
workload = np.random.randint(2, size=(2, 50, WORKLOAD_DIM), dtype=np.int8)
variables = ["x" + str(counter) for counter in range(1, WORKLOAD_DIM + 1)]
P = PolynomialRing(GF(PRIME_NUM), variables, order='lex')
def calculateRowPoly(rowP):
poly = 1
for index, elem in enumerate(rowP):
rowMask = [0] * WORKLOAD_DIM
rowMask[index] = 1
poly = poly * (1 - P.monomial(*rowMask) * elem)
return poly
#=== Start finding solution (the polynomial)
representativeSetPoly = 0
t0solve = time.perf_counter()
for row in tqdm(workload[1]):
representativeSetPoly = representativeSetPoly + calculateRowPoly(row)
t1solve = time.perf_counter()
print(f"== It took {t1solve - t0solve} seconds to find a solution!")
#=== End finding solution
print(type(representativeSetPoly))
#=== Start verification
numOrthoVecVerifier = 0
t0verify = time.perf_counter()
for vec in tqdm(workload[0]):
numOrthoVecVerifier += representativeSetPoly(*vec)
t1verify = time.perf_counter()
print(f"== It took {t1verify - t0verify} seconds to verify the solution")
#=== End verification
Wed, 26 May 2021 10:12:47 +0200https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/Answer by mwageringel for <p>Hi,</p>
<p>I am having a performance issue with the evaluation of a PolynomialRing which I find suspicious. I would like to understand if I am doing things correctly here. </p>
<p>The polynomial is calculated as a function of a set of matrices, whose logic is not relevant here.</p>
<p>In particular, the polynomial I am benchmarking has 16 variables and is 15.000 terms long, which means it has (on average) 120.000 multiplications and 15.000 sums for a total of 135.000 operations.
On my laptop, a single evaluation takes 4 seconds, in other words a single operation every 30 us. </p>
<p>This seems weird, given the speed of modern computers and especially compared to the speed of calculating the polynomial - the <em>representativeSetPoly</em> in the code. Indeed I was expecting that part to be slower than the verification.</p>
<p>Is there a way I can evaluate the polynomial in a more efficient way (the verification part in the code)? I am attaching a code snippet to reproduce the issue</p>
<p>Thanks in advance!</p>
<pre><code>import time
import numpy as np
from sage.all import *
from tqdm import tqdm
WORKLOAD_DIM = 16
PRIME_NUM = 109211909
workload = np.random.randint(2, size=(2, 50, WORKLOAD_DIM), dtype=np.int8)
variables = ["x" + str(counter) for counter in range(1, WORKLOAD_DIM + 1)]
P = PolynomialRing(GF(PRIME_NUM), variables, order='lex')
def calculateRowPoly(rowP):
poly = 1
for index, elem in enumerate(rowP):
rowMask = [0] * WORKLOAD_DIM
rowMask[index] = 1
poly = poly * (1 - P.monomial(*rowMask) * elem)
return poly
#=== Start finding solution (the polynomial)
representativeSetPoly = 0
t0solve = time.perf_counter()
for row in tqdm(workload[1]):
representativeSetPoly = representativeSetPoly + calculateRowPoly(row)
t1solve = time.perf_counter()
print(f"== It took {t1solve - t0solve} seconds to find a solution!")
#=== End finding solution
print(type(representativeSetPoly))
#=== Start verification
numOrthoVecVerifier = 0
t0verify = time.perf_counter()
for vec in tqdm(workload[0]):
numOrthoVecVerifier += representativeSetPoly(*vec)
t1verify = time.perf_counter()
print(f"== It took {t1verify - t0verify} seconds to verify the solution")
#=== End verification
</code></pre>
https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?answer=57302#post-id-57302Thank you for reporting this problem. I can reproduce the issue, but am not sure what is causing it. There is a current ticket ([#27261](https://trac.sagemath.org/ticket/27261)) about memory leaks with polynomial evaluation, which might be connected to this problem.
For now, there are at least two faster workarounds.
Define the evaluation homomorphism at the point `vec` and evaluate it at a polynomial `f`:
def ev1(f, vec):
P = f.parent()
phi = P.hom(list(vec), P.base_ring())
return phi(f)
Or, compute the residue of `f` modulo the point ideal `J` corresponding to the vector. As the result is a constant polynomial, we can convert it to the base ring.
def ev2(f, vec):
P = f.parent()
J = P.ideal([x-v for x, v in zip(P.gens(), vec)])
return P.base_ring()(J.reduce(f))
###Timings:
For reproducibility, I ran
np.random.seed(0)
before executing your code snippet.
sage: vec = workload[0][0]
sage: %time representativeSetPoly(*vec)
CPU times: user 14.6 s, sys: 20.2 ms, total: 14.6 s
Wall time: 14.6 s
0
sage: %timeit ev1(representativeSetPoly, vec)
213 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit ev2(representativeSetPoly, vec)
11 ms ± 156 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
This shows that `ev2` is the fastest. Maybe this is not unexpected as homomorphisms and evaluation/substitution can be used in more general contexts than reduction modulo an ideal.Thu, 27 May 2021 19:48:55 +0200https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?answer=57302#post-id-57302Comment by mwageringel for <p>Thank you for reporting this problem. I can reproduce the issue, but am not sure what is causing it. There is a current ticket (<a href="https://trac.sagemath.org/ticket/27261">#27261</a>) about memory leaks with polynomial evaluation, which might be connected to this problem.</p>
<p>For now, there are at least two faster workarounds.</p>
<p>Define the evaluation homomorphism at the point <code>vec</code> and evaluate it at a polynomial <code>f</code>:</p>
<pre><code>def ev1(f, vec):
P = f.parent()
phi = P.hom(list(vec), P.base_ring())
return phi(f)
</code></pre>
<p>Or, compute the residue of <code>f</code> modulo the point ideal <code>J</code> corresponding to the vector. As the result is a constant polynomial, we can convert it to the base ring.</p>
<pre><code>def ev2(f, vec):
P = f.parent()
J = P.ideal([x-v for x, v in zip(P.gens(), vec)])
return P.base_ring()(J.reduce(f))
</code></pre>
<h3>Timings:</h3>
<p>For reproducibility, I ran</p>
<pre><code>np.random.seed(0)
</code></pre>
<p>before executing your code snippet.</p>
<pre><code>sage: vec = workload[0][0]
sage: %time representativeSetPoly(*vec)
CPU times: user 14.6 s, sys: 20.2 ms, total: 14.6 s
Wall time: 14.6 s
0
sage: %timeit ev1(representativeSetPoly, vec)
213 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit ev2(representativeSetPoly, vec)
11 ms ± 156 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
</code></pre>
<p>This shows that <code>ev2</code> is the fastest. Maybe this is not unexpected as homomorphisms and evaluation/substitution can be used in more general contexts than reduction modulo an ideal.</p>
https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?comment=57307#post-id-57307Thanks for confirming. It seems that the the generic evaluation is not such a bad workaround for #27261 after all.Thu, 27 May 2021 21:08:55 +0200https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?comment=57307#post-id-57307Comment by vdelecroix for <p>Thank you for reporting this problem. I can reproduce the issue, but am not sure what is causing it. There is a current ticket (<a href="https://trac.sagemath.org/ticket/27261">#27261</a>) about memory leaks with polynomial evaluation, which might be connected to this problem.</p>
<p>For now, there are at least two faster workarounds.</p>
<p>Define the evaluation homomorphism at the point <code>vec</code> and evaluate it at a polynomial <code>f</code>:</p>
<pre><code>def ev1(f, vec):
P = f.parent()
phi = P.hom(list(vec), P.base_ring())
return phi(f)
</code></pre>
<p>Or, compute the residue of <code>f</code> modulo the point ideal <code>J</code> corresponding to the vector. As the result is a constant polynomial, we can convert it to the base ring.</p>
<pre><code>def ev2(f, vec):
P = f.parent()
J = P.ideal([x-v for x, v in zip(P.gens(), vec)])
return P.base_ring()(J.reduce(f))
</code></pre>
<h3>Timings:</h3>
<p>For reproducibility, I ran</p>
<pre><code>np.random.seed(0)
</code></pre>
<p>before executing your code snippet.</p>
<pre><code>sage: vec = workload[0][0]
sage: %time representativeSetPoly(*vec)
CPU times: user 14.6 s, sys: 20.2 ms, total: 14.6 s
Wall time: 14.6 s
0
sage: %timeit ev1(representativeSetPoly, vec)
213 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit ev2(representativeSetPoly, vec)
11 ms ± 156 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
</code></pre>
<p>This shows that <code>ev2</code> is the fastest. Maybe this is not unexpected as homomorphisms and evaluation/substitution can be used in more general contexts than reduction modulo an ideal.</p>
https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?comment=57306#post-id-57306With #27261 (where __call__ goes via generic Python evaluation) I got
sage: vec = workload[0][0]
sage: %timeit representativeSetPoly(*vec)
113 ms ± 1.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit ev1(representativeSetPoly, vec)
108 ms ± 1.37 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit ev2(representativeSetPoly, vec)
7.9 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)Thu, 27 May 2021 20:41:49 +0200https://ask.sagemath.org/question/57281/performance-of-polynomialring-evaluation/?comment=57306#post-id-57306