Questions tagged [polynomials]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
128 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
51 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
68 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
35 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
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
198 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
47 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
1answer
234 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
52 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
104 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
102 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
111 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. ...