Questions tagged [polynomials]
The polynomials tag has no usage guidance.
20
questions with no upvoted or accepted answers
5
votes
0answers
130 views
minimizing computations for evaluating two polynomial simultaneously
I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700.
I ...
3
votes
0answers
23 views
Bit complexity of computing the sign of an expression evaluated at an algebraic number
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
3
votes
0answers
54 views
Computational complexity of numerically estimating the roots of a polynomial
The Wikipedia article on finding the roots of polynomials mentions all sorts of methods to do so. But it doesn't give, nor can one easily figure out by following the links, known lower and upper ...
2
votes
0answers
87 views
Decide whether a polynomial has a root
Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
2
votes
0answers
44 views
Understanding CRC Computation with PCLMULQDQ
I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet.
Starting with this one for the definition of ...
2
votes
1answer
269 views
CRC computation speed vs polynomials features
I tried to find information about how features of a CRC polynomials influence computation speed of implementations.
It is obvious that (depending from the CPU architecture the algorithm runs on) ...
2
votes
0answers
50 views
An efficient algorithm to find a linear transformation between two ternary quadratic forms
Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms
$$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\
Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$
over the field $\mathbb{F}...
2
votes
0answers
199 views
Algorithm for finding roots of a polynomial modulo prime powers
Given a polynomial $f$ with integer coefficients and a prime power $p^i$, I wish to find a root of $f$ modulo $p^i$, provided one exists, in polynomial or randomized polynomial time in the size of the ...
1
vote
0answers
15 views
Binomial basis and the usual basis of polynomial algebra $\mathbb C(X)$
Consider the polynomial algebra $\mathbb C[X]$. Then the set $\{1, X, X^2,\dots,\}$ forms a vector space basis for this algebra. In general, we know that the set $\{P_n(X) \in \mathbb C[X]: n \ge 0 \...
1
vote
0answers
32 views
How do I decode a received polynomial code with an error?
As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
1
vote
0answers
48 views
How to compute the first n coefficients using number theoretic transform (NTT)?
I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(...
1
vote
0answers
25 views
Generating a set of divergence-free basis
I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis ...
1
vote
0answers
42 views
Update model parameter with new data, discarding old data
I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve,...
1
vote
0answers
32 views
Complexity of computing symmetries of a polynomial
Given a polynomial $f\in\mathbb{F}[x_1,\ldots,x_n]$ what is the computational complexity of computing a generating set of the automorphism group of $f$? On first look this seems like a hard problem (...
1
vote
0answers
53 views
How to find (real-valued) roots of matrix polynomial
Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial
$$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$
Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
1
vote
0answers
107 views
Connection between formula size and time complexity
Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree.
Is there a connection between ...
1
vote
0answers
41 views
Degrees of polynomials representing Boolean functions
Let $$B_1=\vee_{i_1=1}^d\wedge_{i_2=1}^d\dots\vee_{i_{2r-1}=1}^d\wedge_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$
$$B_2=\wedge_{i_1=1}^d\vee_{i_2=1}^d\dots\wedge_{i_{2r-1}=1}^d\vee_{i_{2r}=1}^dX_{...
0
votes
0answers
117 views
Multiplying bivariate polynomials using FFT
Consider two bivariate polynomials of degree at most $n-1$ in each variable:
$$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$
...
0
votes
0answers
18 views
custom cc 16 bits with Polynomial and Initial Value , algorithm
I generate crc 16 bits with hex Workshop.
Polynomial :1234(hex) Initial Value :5678 (hex) . making it on 010 (ascii) and get 3744.
I looking for this algorithm , I prefer it on c#. but I not find it....
-1
votes
1answer
113 views
I would like to know if there is a closed form expression from taking the reciprocal of a polynomial
I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading.
...
