Computer Science

Questions tagged [polynomials]

Ask Question

The tag has no usage guidance.

80 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
1
vote
1answer
26 views

Fitting a polynomial to a set of points or to a skeleton

Available data Available to me is a set of points which can be represented as shown in image 1: Also available to me is a non-continuous path derived from this data. It is not important how this non-...
1
vote
0answers
13 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 ...
2
votes
1answer
68 views

Polynomials - using Newton's method, or not?

I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed. I can use general Newton's ...
3
votes
1answer
44 views

Polynomial size Boolean circuit for counting number of bits

Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x_1, y_1, \dots, x_n, y_n)$, such that the output is true if and only if the assignment that makes ...
2
votes
1answer
20 views

Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''

I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my ...
1
vote
1answer
26 views

Search for numerical solutions of underdetermined systems of quadratic equations

I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a ...
1
vote
0answers
117 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
1answer
92 views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
3
votes
1answer
81 views

Last digit of polynomial value

There is a simple-looking problem. Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and ...
0
votes
1answer
167 views

Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
2
votes
1answer
44 views

Polylogarithm growth rate proof using Polynomial growth equation

In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function ...
0
votes
0answers
11 views

Convert polynomial generator to binary form for crc [duplicate]

i have the polynomial generator x^3 + x To convert to binary and i am unsure of the steps to complete. Help on how to convert various polynomials to binary would be greatly appreciated and i do not ...
2
votes
0answers
44 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}...
3
votes
1answer
63 views

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following: Let $F(x)$ be given as a product $F(x) = \prod_{...
4
votes
1answer
66 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
1
vote
1answer
46 views

How to find sets of polynomially bounded numbers whose subset sums are different?

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
2
votes
1answer
269 views

Calculating a polynomial's coefficients from its roots

Let $P$ be a monic polynomial polynomial given by its roots: $$P(X) = (X-x_1)\times...\times(X-x_n)$$ What is the minimum asymptotic complexity to compute its expansion of the form: $$a_nX^n+...+a_0$$...
2
votes
1answer
86 views

Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
2
votes
1answer
42 views

No common terms between polynomials: an efficient check?

The "common term" would be in standard form, but the two input multivariate polynomials needn't be, e.g $x(1+y)+y$ and $y(x+a+b)$ have one common term, $xy$. A brute force solution would be to ...
2
votes
2answers
69 views

How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it? Perhaps: SZ shows natural polynomials are equal iff it shows those ...
0
votes
0answers
17 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 ...
1
vote
1answer
83 views

How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$. In ...
0
votes
1answer
84 views

How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics

I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a,...
2
votes
2answers
63 views

Necessity of convolution operations for product of two polynomials via brute force method

Reference: Page 4 of this document Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$. ...
2
votes
1answer
265 views

Randomized vs deterministic approach for multiset equality

Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$? Algo 1: Sort $S_1$ and $S_2$ and then check $S_1 = S_2$ Running time : $O(n \log {n})$, where $n$ is the size of the multi ...
1
vote
0answers
65 views

Global Minimum of Multivariate Polynomial is coNP-complete? [closed]

Is the following problem coNP-complete? Inputs: $p=$ a possibly non-convex multivariate polynomial over $\mathbb Z$ $k\in \mathbb Z$, an integer Question: Is $\forall x\in\mathbb Z: p(x)\geq k$?
16
votes
1answer
1k views

Find a polynomial in two or three queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point. Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$. Output: The $d$ coefficients of polynomial ...
1
vote
1answer
203 views

How does one generate all the terms of a multivariate polynomial algorithmically?

I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a ...
1
vote
0answers
37 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,...
3
votes
0answers
47 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 ...
3
votes
1answer
77 views

Approximate a smooth f(x,y) function with a polynomial function

I have a discrete function of two real variables defined as a set of point in a rectangular domain. The function is smooth. I need to approximate it with a polynomial function of the 2nd degree with ...
4
votes
1answer
87 views

Efficient algorithm to translate/shift polynomials

I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the ...
5
votes
1answer
89 views

Lower bound of degree of polynomial approximating parity

Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$ It is known [See e.g. Lemma 5 of this lecture note] that any ...
1
vote
1answer
58 views

Isomorphism of finite dimensional polynomial algebras over finite fields

For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between: $$\frac{\mathbb{F}_q[x]}{\...
4
votes
3answers
4k views

Converting Polynomials into Binary form

How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$
-1
votes
1answer
106 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. ...
2
votes
0answers
180 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
1answer
2k views

Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

I was reading about CRC coding from two books: Data Communication and Networking by Forouzan Page 294 Computer Network by Tanenbaum Page 188 They use following notations: $d(x)$: dataword to be ...
4
votes
2answers
52 views

Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?

I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 ...
0
votes
0answers
39 views

Polynomial Multiplication and Modulo Operation complexity [duplicate]

Given two polynomials of degree $n$ and $m$ over $\Bbb F_q[x]$ it takes about $O((n+m)\log ((n+m)))$ operations ring operations over $\Bbb F_q[x]$ to multiply them. What is the corresponding bit ...
0
votes
1answer
92 views

CRC error detection

I know that to find an error in signal we have to divide given signal with given polynomial and if 0 remains there is no error. But if I have received signal: 0000 0101 0101 0000 1010 0101 and ...
0
votes
2answers
647 views

Find all rational roots of a polynomial equation

I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest ...
3
votes
1answer
276 views

How to find the symmetry group of a polynomial

Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. ...
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 (...
2
votes
1answer
107 views

Check if a given polynomial is primitive

I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C ...
-1
votes
1answer
624 views

Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?

Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need ...
5
votes
1answer
3k views

Multi-point evaluations of a polynomial mod p

Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this? I tried using Berlekamp's ...
0
votes
1answer
136 views

Computing a subproduct tree

Consider the following description of a subproduct tree. We define a tree T for some points x[0] to x[n-1], and define m = log_2(n). Tree T is represented as a matrix where each row-column entry i, ...
1
vote
1answer
93 views

Boolean function and real degree

Let $f$ be a boolean function with minimum degree real polynomial representing it be of degree $d$. Is there a relation between number of zeros $f$ or $1-f$ and degree $d$?
5
votes
0answers
124 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 ...

1 2