0
votes
0answers
43 views

Real roots of a quintic polynomial with constraints

This is a question on the edge of math and programming. I pondered about the best way to state the problem: should I provide context, or get straight to the point of the question? Given various ...
0
votes
0answers
35 views

Question about Horners rule algorithm

I am studying Horner's rule I have a question about an algorithm I found here . I understand that the rule allows you to break down polynomials in to monomials to solve them more easily, so that for ...
0
votes
1answer
30 views

Fast Fourier Transformation: inverse transform of the product of polynomials

I have managed to implement and understand most of the Fast Fourier Transformation. However, I have one last question. If one has two polynomials, say $A(x)$ and $B(x)$, and one computes DFT of ...
0
votes
2answers
54 views

Solving polynomial to get all coefficients

Given an array of N integers where N can go upto 10^4 and each element can be upto 10^5. Now i need to find the coefficients of polynomial p that is given as : ...
1
vote
2answers
88 views

Most Efficient Method to Find Roots of Polynomial [duplicate]

I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
2
votes
1answer
40 views

Efficient Extended GCD Algorithm for Polynomials

For computing the GCD of two multivariate polynomials we have the Euclidian algorithm. However, it's well known that the Euclidian algorithm is not very efficient (because of intermediate expression ...
3
votes
1answer
61 views

Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$

Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$. Given $n+1$ values ...
1
vote
1answer
36 views

find the polynomial if we know its output

$f$ is a polynomial of integral coefficient.Now suppose we have a computer program to find out its output taken in $\mathbb{Z}$.Is it possible for us to find out this polynomial in finitely many ...
1
vote
0answers
22 views

Factorisation algorithm for polynomials in several variables over $\mathbb{Z}$.

What algorithm is used by a CAS to decide how to factor a polynomial in several variables over $\mathbb Z$?
1
vote
0answers
54 views

Algorithm for finding irreducible polynomials in finite field extension

Let $K(\alpha_1,\ldots,\alpha_n)/K$ be a finite field extension and suppose we know ${\rm irr}(\alpha_1,K),\ldots,{\rm irr}(\alpha_n,K)\in K[x]$. My question is: given an arbitrary element $\lambda\in ...
1
vote
0answers
35 views

GCD of this polynomial

So here is the exact question that i am having trouble on: "Extend the Euclidean algorithm to polynomials and find the greatest common divisor of: $3x^5-10x^4-4x^3-14x^2-7x-4$ and ...
1
vote
1answer
29 views

Find a polynomial mod $n$ injective on a given set

This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice ...
2
votes
1answer
107 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
1answer
62 views

Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
0
votes
1answer
26 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
0
votes
1answer
31 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
0
votes
0answers
14 views

Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
0
votes
1answer
58 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
0
votes
0answers
23 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
1
vote
3answers
110 views

How to choose the starting point in Newton's method?

How to choose the starting point in Newton's method ? If $p(x)=x^3-11x^2+32x-22$ We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some ...
5
votes
2answers
188 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
4
votes
2answers
56 views

Finding out the coeffcient next to $x^2$ in $(\cdots(x-2)^2-2)^2\cdots-2)^2$.

In need to find out the coefficient next to $x^2$ in polynomial $(\cdots(x-2)^2-2)^2\cdots-2)^2$, where we nest the expression $(x-2)^2$ n times. Meaning that for $n=1$ we get $(x-2)^2$, for $n=2$ we ...
1
vote
1answer
73 views

Find coefficients of polynomial that has zeros at certain points

Given a list of values z0, z1, ..., zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z0, z1, ..., zn-1 (possibly ...
0
votes
0answers
39 views

algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
1
vote
2answers
83 views

Polynomial composition

I have a polynomial of degree at least 4. How can I test if it is the composition of two other polynomials of degree at least 2? (Any polynomial is the composition of two polynomials if you allow one ...
0
votes
1answer
77 views

Efficient polynomial evaluation using idea of fast fourier transform

Please would anyone suggest an efficient algorithm ($O(n \log n)$) to evaluate a polynomial at all the $n$th roots of unity, where $n$ is not a power of $2$?
0
votes
1answer
92 views

Algorithm for a n x n grid of squares

Say we have a puzzle where by there are $n^2$ squares and each of the 4 sides of each square has a colour. The aim of the puzzle is to see if the squares can be arranged in such a way that when 2 ...
2
votes
0answers
41 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
3
votes
0answers
197 views

Convert CRC to result of reversed polynomial?

Looking at the Wikipedia page for CRCs I see that they list a bunch of standard CRC polynomials along with the Reversed Polynomials of each. If I have a value that was calculated with a certain ...
0
votes
1answer
26 views

Compute all the directional derivatives of a trivariate polynomial function quickly

Given a trivariate polynomial $A\in\mathbb{R}[x,y,z]$, a direction $\vec v\in\mathbb{R}^3$ and a point $p\in \mathbb{R}^3$, what is the fastest way to compute the directional deriviatives ...
1
vote
2answers
58 views

Polynomial Question

Find polynomials $A(x)$ and $B(x)$ such that $A(x)P(x) + B(x)Q(x) = x + 1$ for all $x$ where $P(x) = x^4 - 1$ and $Q(x) = x^3 + x^2$. I'm stumped on this question. I know that I'm supposed to apply ...
2
votes
1answer
257 views
2
votes
3answers
114 views

If I know that a polynomial (of order $k \gt 2$) has at most $1$ positive real root - can I find that easily?

[update 2] Urgghh - the time-consumption really stems only from the construction of the h-order polynomial. The time for finding the roots (only 10 to 20 times Newton-iteration because of my nice ...
0
votes
1answer
94 views

Bounding a bicubic polynomial

My actual situation is working with bicubic polynomials, (that is, polynomials of the form $\sum_{i=0}^3 \sum_{j=0}^3 a_{i,j} x^iy^j$) defined on the unit square $[0,1]^2$ (actually these are ...
2
votes
3answers
75 views

How to solve the polynomial equation $\sum_{i=1}^{i=m} \frac{l_i}{l_i - x} = n$?

Let m and n be strictly positive integers, and a set of m real positive numbers $$l_{i, i \in \{ 1, m \}}.$$ I want to solve numerically: $$\sum_{i=1}^{i=m} \frac{l_i}{l_i - x} = n$$ finding the m ...
0
votes
1answer
52 views

algorithm for Bezier curve with eleven control points

I would like to know the algorithm/ polynomial equation for a Bezier curve with eleven control points. Thanks in advance.
1
vote
2answers
180 views

Solve a set of non linear Equations on Galois Field

I have the following set of equations: $$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$ $$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$ $M_1, M_2, x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m).$ I want to ...
9
votes
2answers
680 views

Quickest way to determine a polynomial with positive integer coefficients

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. ...
1
vote
2answers
96 views

Factoring any single-variable polynomial in $\mathbb C$

The fundamental theorem of algebra says $$ \forall p(x):\mathbb C \to \mathbb C,\ p(x) = a\prod_{n=0}^m\big(b_nx+c_n\big) $$ where $p(x)$ is a single-variable polynomial, and $\{a;m\}\cup\{\forall ...
3
votes
1answer
54 views

Computational Complexity of Algorithms

I want to know if the following proposition is correct or not? For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is ...
1
vote
1answer
88 views

what if geometric sequence + geometric sequence

I wrote a program that basicly can find the formula of the sequence that created with any-degree equation. For example if you give my program that sequence: [1926, 2811, 833240, 28778265, 398155842, ...
2
votes
2answers
143 views

Prove that consecutive Legendre Polynomials do not have a common root.

I am using the following definition of Legendre Polynomials: $P_0(x)=1$ $P_1(x)=x$ $\displaystyle P_{k+1}(x)=\frac{2k+1}{k+1}x P_k(x)-\frac{k}{k+1} P_{k-1}(x)$ Q: Prove that for no $k\in ...
0
votes
1answer
32 views

Distinct-degree factorization

I'm trying to understand distinct-degree factorization from Wikipedia. I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$. We start with $i=1$. I calculate $g = ...
1
vote
0answers
61 views

Positive Semidefiniteness of a polynomial.

I have a multivariate polynomial $p(x_1,\ldots,x_n)$ and I wish to check if it is positive semidefinite over $R^n$. I can always choose any direction $\vec{v}$ and check that the univariate polynomial ...
3
votes
1answer
349 views

Recursive FFT java implementation

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
0
votes
1answer
107 views

Multiplying Polynomials with fewer coefficient multiplications

Not sure how this works! Apparently it can be done in 5-6 multiplications Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.
5
votes
1answer
490 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
3
votes
1answer
294 views

Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
1
vote
1answer
66 views

minimizing multiplications in computing a polynomial expression

I am looking for an algorithm which presents a given polynomial in many variables (given as a sum of monomials) in a form with the smallest number of multiplications of variables. For example ...
1
vote
1answer
178 views

Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)…(z-n)$ into a vector

So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ ...