The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
2answers
102 views

What are the numerical methods for huge polynomial systems?

Let a system of $n$ polynomial equations of degree $d$ with $m$ variables. I'm interested in a sparse system with $d = 3$, $n \sim 2000000$, $m \sim 50000$ and integer coefficients. What techniques ...
0
votes
0answers
32 views

Poly-Time Factorization of Multivariate Polynomials

Is there a polynomial-time algorithm that factors multivariate polynomials over GF(2)? Or over $\mathbb Z$? By polynomial-time I mean in the degree of the polynomial, not in the number of variables - ...
5
votes
1answer
69 views

Accurate Polynomial Evaluation in Floating Point

What are the most accurate algorithms for evaluating a polynomial using floating point arithmetic? The internet seems to suggest that Horner's method is commonly used. In particular I have a cubic ...
0
votes
0answers
25 views

create local dem with polynomyals in matlab

i wrote a program about dem(digital elevation model)..and i have some data in my input...i made a meshgrid for my data....and now how can i know how many point of my data is there in my mesh ...
2
votes
1answer
110 views

rational functions in Python

I would like use Python to verify the following identities: $ \frac{1}{1-z} = 1 + z + z^2 + z^3 + \dots $ $ \frac{1}{1-z - z^2} = 1 + z + 2z^2 + 3z^3 + \dots $ $ q \prod_{n \geq 1} (1 - q^n)^{24} ...
1
vote
0answers
64 views

Prove $T_n(x)$ of Chebyshev Polynomial given the recurrence relation [closed]

Using the recursion formula for Chebyshev polynomials, show that $T_n(x)$ can be written as $$T_n(x)=2^{n-1}(x-x_1)(x-x_2)...(x-x_n)$$ where $x_i$ are the $n$ roots of $T_n$ The recurrence ...
1
vote
1answer
53 views

Transfrom a Legendre polynomial from $\int_{-1}^{1}\phi_j(x)\phi_k(x)dx $ into $\int_{a}^{b}\phi_j(t)\phi_k(t)dt$ given $t=\dfrac{1}{2}[(b-a)x+(a+b)]$

The Legendre polynomials satisfy $$\int_{-1}^{1}\phi_j(x)\phi_k(x)dx = \begin{cases} 0 &j\neq k\\\\ \dfrac{2}{2j+1} &j=k \end{cases}$$ Suppose that the best fit problem is given on the ...
1
vote
1answer
161 views

Multivariate Orthogonal Polynomial Generation

I'm trying to apply the stochastic galerkin method to partial differential equation with multiple uniform random coefficients. I'm puzzled as to how to extend the corresponding orthogonal (legendre) ...
1
vote
1answer
60 views

Determine low-order polynomial lower bound

I have a function $f$ I'd like to determine numerically and I have a bunch of $(x, y)$ pairs which approximate the function in the following sense: all of the points satisfy $f(x) \leq y$, most of the ...
3
votes
1answer
110 views

What is the most efficient way to represent a 1D function using $hp$-finite element basis functions

Given a one-dimensional function (let's say infinitely differentiable) and a prescribed accuracy of an L2 (or H1) norm, what is the optimal mesh and (in general arbitrary) polynomial orders on each ...
3
votes
3answers
130 views

Evaluating large determinants with multivariate polynomial entries

I have some large (n~100) square matrices with entries two variable polynomials of bounded degree (roughly <20, but many entries are smaller) and integer coefficients, and I'd like to be able to ...
5
votes
0answers
224 views

Stochastic Galerkin Projection Approach for using Generalized Polynomial Chaos Expansion (GPCE) in solving PDE

I am not sure if this is very general question but I want to know Is there any way that I can define the Test and trial function in the way that I want and dont use the default functions. so if I want ...
3
votes
2answers
146 views

Trajectory Planning: Polynomials as universal, integrable approximation functions?

I'd like to program a trajectory planner, let's say for a robot, and I can pass acceleration commands to the robot, the robot can move in one dimension. The outcome of the planner is now a vector with ...
3
votes
2answers
169 views

How to properly use polynomial projection to get values at visualization nodes?

I am trying to implementing a nodal discontinuous Galerkin spectral element method for linear and non-linear systems of equations. The solution at each time step is given at ...
4
votes
1answer
61 views

Fastest method for evaluating the limit of the sign of a polynomial

Consider a multivariate polynomial $f(x) = f(x_1, \ldots, x_n)$ with maximum degree $d$. Following the linear symbolic perturbation scheme described in Seidel 1998, I want to evaluate the limit ...
2
votes
2answers
125 views

Stable formula for a specific root of a depressed cubic

I have a cubic of the form $$x^3 - a x - b = 0$$ where $a, b > 0$. Thus, I know there is exactly one positive root. Is there a nice stable formula for this unique positive root?
5
votes
4answers
2k views

How to find more than one root of a polynomial?

This program finds the first root of the function f, defined in the code. There are 5 roots of this function. (x=1,2,3,4,5) I wish to find all of the roots in this program and print them to the ...
17
votes
2answers
379 views

Why do equi-spaced points behave badly?

Description of experiment: In Lagrange interpolation, the exact equation is sampled at $N$ points (polynomial order $N - 1$) and it is interpolated at 101 points. Here $N$ is varied from 2 to 64. ...
5
votes
4answers
542 views

Fastest polynomial root finder for a given accuracy

I am looking for a very fast polynomial root finder, hopefully with a matlab code. I don't need very accurate results, 2-3 decimal places would be fine. Also the method should be able to optionally ...
1
vote
1answer
317 views

How to apply a Galerkin finite element method to a linear, one-dimensional boundary value problem

I have the following boundary value problem: $$-(\alpha u')' + \gamma u = f $$ in $\Omega = (a,b)$ with b.c. $u(a) = u(b) = 0$ and $\alpha > 0, \gamma ≥ 0$ and $f:(a,b) \to \Re $ The weak ...
7
votes
1answer
298 views

Polynomial Fitting from Chebyshev Coefficients

I have been reading Numerical recipes about how to create a power series approximation to a function once you have a Chebyshev approximation to the function. However it is still very unclear to me how ...
6
votes
2answers
912 views

Solution of quartic equation

Is there a open C-implementation for the solution of quartic equations: $$ax⁴+bx³+cx²+dx+e=0$$ I am thinking of an implementation of Ferrari's solution. On Wikipedia I read that the solution is ...
19
votes
0answers
414 views

Difficulty with Spectral Method using Chebyshev Polynomials

I am having a bit of difficulty in trying to understand a paper. The paper uses spectral method to solve for an eigenvalue that comes from a system of coupled ODEs. I will write out only one equation ...
5
votes
2answers
153 views

Is there a backward stable $\tilde{O}(n \log(1/\epsilon))$ algorithm to factor a complex polynomial?

Finding the roots of a complex polynomial is in general extremely numerically unstable, as discussed in (1). According to Pan ((2), (3)), this produces a cubic complexity lower bound, and he presents ...
3
votes
2answers
555 views

Evaluation of multivariate polynomials

I am seeking for an efficient algorithm to compute a multivariate polynomial of a fixed structure, but different coefficients and evaluation points. The question is the same as this one, which ...
3
votes
1answer
89 views

Numerically stable real solution(s) to a system of bivariate quadratics

I have a a system of bivariate polynomials as follows: $ E(u,v): e_2(u) v^2 + e_1(u) v + e_0(v) = 0 \\ F(u,v): f_2(u) v^2 + f_1(u) v + f_0(v) = 0$ where $e_n(u) = e_{n_2}u^2 + e_{n_1} u + e_{n_0}$ ...
9
votes
1answer
83 views

Numerically stable algorithms for computing remainder of polynomials

Let $f, g \in \mathbb{R}[x]$ and $\deg f > \deg g$. I am looking for asymptotically fast and numerically stable algorithms for computing $f \bmod g$. In the applications intended, both $f, g$ are ...
14
votes
3answers
231 views

Uses of power series maps

I'm from the field of accelerator physics, specifically related to circular storage rings for synchrotron light sources. High energy electrons circulate around the ring, guided by magnetic fields. ...