Revision history [back]

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