Questions tagged [polynomials]
The polynomials tag has no usage guidance.
26
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
24 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
59 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
96 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
68 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
0answers
52 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
204 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
31 views
Efficient bit-level implementation of Boolean polynomials with few variables
A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form
$$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
1
vote
0answers
25 views
Finding points of local maximum error in Remez algorithm
So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the ...
1
vote
0answers
46 views
Optimize binary multivariate polynomial multiplication
You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
1
vote
0answers
51 views
Express polynomial as sum of two lower-degree polynomials, modulo another
Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that
$$p(x) \equiv r_1(x) x^...
1
vote
0answers
18 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
33 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
53 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
29 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
1answer
310 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) ...
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
58 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
1answer
38 views
Finding $Aeven(x)$ and $Aodd(x)$ for a Fast Fourier Transform (FFT) problem?
In this article about FFT the author used FFT on this polynomial.
$A(x) = 3+2x+3x^2+4x^3$
Using $ A(x)= Aeven(x^2) + xAodd(x^2)$ the author determined the following for $Aeven(x)$ and $Aodd(x)$
$ ...
0
votes
0answers
51 views
Time to evaluate a product of binomials $1 + x^i$
I am considering the asymptotic analysis required to convert a polynomial of the shape
$$P(x) = \prod_{i = 1}^{n}(1 + x^{s_i})$$
to its "full" representation, for example $$P(x) = 1+x^3+x^5+...
0
votes
0answers
191 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
24 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
115 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.
...
