Questions tagged [polynomials]

The tag has no usage guidance, but it has a tag wiki.

Filter by
Sorted by
Tagged with
6
votes
1answer
274 views

Problems Implementing the Remez Algorithm

So first off: *** This code is not being used in production software. It is a personal project of mine, trying to understand approximation theory and advanced curve fitting. In other words, I'm ...
-3
votes
0answers
33 views

Pseudocode of Lagrange derivatives through recursion

First of all, I do not have experience building a recursion algorithm. Unfortunately, I have to make a simple code that used to find the Lagrange weight in a different derivative order. $$l(x)=\prod_{...
6
votes
3answers
241 views

Fast evaluation functions given by straight-line programs

I have a simple but long function that takes a vector x[10], and outputs a vector y[100]. It is an automatically generated eval function for a multivariate polynomial, ie, there is only (complex) ...
2
votes
1answer
57 views

How to robustly and numerically expand a $k$-order polynomial in two variables defined on a polygon domain?

Given a $k$-order polynomial in two variable $p(x, y)$ defined on a polygon domain $K$. And I want to numerically expand it to the following form $$ p(x, y) = c_0 + c_1 x + c_2 y + c_3 x^2 + c_4 xy + ...
2
votes
0answers
26 views

Find solution to Polynomial Sequences without going through variety in Sage

I'm computing the Groebner basis of an ideal defined over the QQ ring. Once I have this Groebner basis, I would like to obtain a set of values that satisfy the equations in the Groebner basis. I know ...
1
vote
0answers
33 views

Minimizing a polynomial with millions of monomials

I need to minimize a single polynomial $P(x_1,x_2,...,x_n)$ with the constraint that for each $i$, $0\leq x_i \leq 1$. The number of variables in my practical problem is at most $50$. The degree is at ...
4
votes
1answer
259 views

Interpolating a mathematical function using a Hermite Cubic Finite Element Space

I have a Hermite Cubic Finite Element Space on a computer in the form of Matlab m-files. More specifically, I can evaluate four "shape functions" $N_1, N_2, N_3,$ and $N_4$, for which the following ...
2
votes
1answer
97 views

Differentiation Matrix In DG-FEM - Hesthaven/Warburton

In the book of Hesthaven and Warburton on discontinual Galerkin methods the authors give motivation to the differentiation matrix (page 52), referred to as $D_r(i,j)=\frac{dl_j}{dr}|_{r_i}$ where $l_i(...
1
vote
0answers
108 views

C++ Library: What is the Most Efficient Library that Factorizes a Polynomial?

I need to know what library is the fastest one that can factorize a polynomial of large degree whose coefficients are big integers. I have tried NTL library to factorize a monic polynomial but it is ...
0
votes
0answers
26 views

Finding the polynomial for the solution of an ODE

I’m stuck trying to solve part (b) and (c) of the below problem, but part (b) is the one of main concern here as I think (c) should follow easily once (b) is completed. I don’t know where to start ...
6
votes
2answers
122 views

Positive root of $x^q + bx - b$

Is there either a closed-form expression or fast/elegant algorithm for computing the positive root of the polynomial $$f(x)=x^q + \beta x - \beta,$$ where $\beta>0$ and $q\geq2$? How about the $q\...
1
vote
1answer
106 views

Find the roots of a complicated polynomial

For the polynomial $$p(x) = (x-1)(x-2) \cdots (x-20) - 2^{-23}x^{19}\, ,$$ I tried to use fzero() in MATLAB, and I set the interval to be $[0.5,1.5]\cdots [19.5,...
5
votes
2answers
153 views

Building Gaussian-type quadrature schemes with Zernike polynomials

The abscissas for Gauss quadrature are given by the zeros of the Legendre polynomials. The Legendre polynomials form an orthogonal set over $[-1, 1]$, and it is shown in (for instance) Kress that the ...
9
votes
2answers
243 views

Numerical stability of higher order Zernike polynomials

I'm trying to calculate higher order (e.g., m=0, n=46) Zernike moments for some image. However, I'm running into a problem ...
1
vote
0answers
736 views

Solve system of polynomial equations with Python

I have 5 at most 4th order polynomials in 5 variables, $$p_i(x_1,x_2,x_3,x_4,x_5) \qquad i = 1, \ldots, 5$$ where all coefficients are either rational or floating point. I'd would like to get the ...
5
votes
2answers
161 views

Polynomial approximation spaces

I often see people using products of 1-D polynomials to do interpolation or projection of smooth multivariate functions over grids or cells because it is intuitive and simple to implement. What are ...
24
votes
5answers
2k views

Why do equi-spaced points behave badly?

Experiment description: 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. Each ...
2
votes
1answer
49 views

Test on a set of high degree polynomials whose coefficients in {-1,0,1}

I'm looking for the best way of implementing the following algorithm: consider the set of all polynomials with a high degree (say, degree 30) whose coefficients ranges from a given set of values (say, ...
1
vote
0answers
55 views

Numerical analysis: Chebyshev coefficient representation error

If $x_k$ are the Chebyshev nodes, that is for $n \in \mathbb{N}^*$, we have $x_k = \cos(\pi \frac{2k + 1}{n})$. Now suppose you have approximated values of $x_k$ and $x_{k'}$ for $k,k' \leq n$. In the ...
2
votes
0answers
37 views

Can I expect reasonable results when expanding in scaled Legendre polynomials?

Imagine I want to compute the eigenvalues of an operator $\hat O$ defined on $ L^2(\mathbb{R})$, however using a properly scaled N-dimensional polynomial basis of $ L^2([-a,a]) $ which fulfills ...
2
votes
2answers
709 views

Polynomial Interpolation with Matlab polyfit

Given $N$ data points, does polyfit of degree $N-1$ produces the unique interpolating polynomial? For concreteness, here is a code example: ...
1
vote
2answers
315 views

Polynomial approximation

Is there any universal method to fill this matrix for any $n$ value: $\textbf{A} = \left[ \matrix{n & \sum x_i & \sum x_i^2 & \cdots & \sum x_i^n \cr \sum x_i & \sum ...
4
votes
2answers
127 views

Intervals where the sign of a polynomial can be computed reliably

This is a follow-up of a previous question. Let $p$ be a polynomial with floating-point coefficients. Is there a method for finding intervals where evaluating $p$ in floating-point arithmetic always ...
0
votes
1answer
342 views

Derivatives of a Chebychev polynomial

I am using Chebychev collocation nodes for approximation, and my problem requires me to calculate derivatives of the polynomial. I have been reading from a few sources, but I am not sure I understand ...
0
votes
1answer
50 views

Chebychev Polynomial derivatives at zero points and extreme points

I was looking for some help with derivatives of Chebychev polynomials at zero points. The recursive expression, $$ T_{(j+1)}(x) = 2xT_j(x) - T_{(j-1)}(x) $$ has the derivative $$ T'_{j+1}(x) = 2T_j(...
6
votes
3answers
138 views

Accurate evaluation of the sign of a polynomial

Let $p$ be a polynomial with floating-point coefficients and let $a$ be a floating-point value. Is there a method for accurately evaluating the sign of $p(a)$ in floating-point arithmetic? I don't ...
4
votes
1answer
168 views

Computing size of N-Dimensional Polynomial Basis and Efficient Representation of Basis

A problem I have had on my mind recently has been a compact way to compute the size of an $N$-Dimensional Polynomial basis of some order $p$, where a linear basis is $p=1$. I have attempted searching ...
1
vote
0answers
399 views

Polynomial approximation - Vandermonde matrix creation - precision

I am trying to fit a polynomial through 340 points in a 3D space, i.e. $$f(x,y,z) = k$$ I asked previously about the theory behind polynomial interpolation here -> Polynomial interpolation Few ...
0
votes
1answer
145 views

Underdetermined/overdetermined polynomial interpolation

I am trying to apply a polynomial interpolation to 340 points in a 4D space, i.e., $$f(x,y,z)=k\, .$$ What I would like to understand is this: if I use a 6th order polynomial I will end up with 343 ...
2
votes
1answer
69 views

Legendre expansion of $r(x) = f(x)/g(x)$ using a finite number of samples from $f(x)$ and $g(x)$

I have two finite sets of events $\{x_1, ..., x_N\}$ and $\{y_1, ..., y_N\}$ that are sampled from the PDFs $f(x)$ and $g(x)$, respectively, where $x \in [-1,+1]$. I want to estimate the Legendre ...
1
vote
0answers
73 views

Quadrature in finite element methods | How should I compute integrals involving the solution of the last time step?

Let $\Delta\subseteq\mathbb R^2$ denote the triangle spanned by $(0,0)$, $(1,0)$ and $(0,1)$ and $$\mathbb P_r(\Delta):=\left\{p:\Delta\to\mathbb R\mid p(x)=\sum_{|\alpha|\le r}\lambda_\alpha x^\alpha\...
1
vote
0answers
56 views

How to sort 13 enormous polynomials, each having terms with 5 variables ($1>h_0>h_1>h_2>h_3>h_4$)?

Both algebraically or with software (numerically/computationally, for example) is acceptable. Here is a how one of the polynomials looks like ($L<1$ is a constant). I have attached a text file ...
3
votes
0answers
103 views

Closed form PDF/CDF using Orthogonal Polynomial Expansion (gPC)

Consider a random variable which is given by an orthogonal polynomial expansion in one parameter (or polynomial chaos expansion PCE), i.e. , $$ f(\alpha) = \sum\limits_{n=0}^{\infty} \hat{f} (n) \psi ...
10
votes
3answers
3k 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 ...
1
vote
1answer
257 views

Matlab symbolic differentiation of Legendre polynomials

Consider $f(x)= \sum\limits_{n=0}^N a_n p_n (x)$, where $p_n$ are the Legendre polynomials. If one wants to differentiate $f'$ symbolically, i.e. to compute $$f'(x) = \sum\limits_{n=0}^{N-1} b_n p_n (...
7
votes
1answer
294 views

Numerically stable computation of the Characteristic Polynomial of a matrix for Cayley-Hamilton Theorem

I was wondering if there is any known way to compute the Charactaristic Polynomial P of a matrix A numerically stable in the sense of realizing the Cayley-Hamilton Theorem, i.e. that P(A)=0. I've ...
5
votes
0answers
151 views

How to optimally choose points for multivariable Hermite interpolation?

I have a multi-variate, continuous function $f$ from $R^n$ to $R$, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ...
2
votes
1answer
284 views

How to compute the Jacobi matrix (tridiagonal matrix) of a polynomial with a recurrence relationship?

I am looking at Trefethen and Bau Exercise 37.1: I have two normalizations of the Legendre polynomials with corresponding recurrence relations: $$P_n(1)=1$$ which follows $$P_n(x) = \frac{2n-1}{n} x ...
1
vote
0answers
73 views

A linear polynomial that is the minimax (best) approximation to $f(x)$ on the interval $[-1,1]$

Suppose you have the following analytical information about a function $f(x)$ on $[-1,1]$: \begin{align*} f(x) &= \frac{1}{x+3}\\ f'(x) & = -\frac{1}{(x+3)^2}\\ f^{''}(x) &= \frac{2}{(x+3)...
2
votes
0answers
96 views

Is the numerical resolution of this huge sparse polynomial system tractable?

I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution ...
5
votes
1answer
357 views

Polynomial order of an approximation of a section of sine and numerical accuracy

I was playing with the idea that a sine function is periodic. But even within one period there are symmetries, namely the second fourth of a period is the mirror image of the first fourth and the ...
10
votes
3answers
772 views

Benchmarks for Gröbner bases and polynomial system solution

In the recent question Solving system of 7 nonlinear algebraic equations symbolically, Brian Borchers experimentally confirmed that Maple can solve a polynomial system that Matlab/Mupad cannot handle. ...
1
vote
0answers
215 views

Calculating lagrange polynomial for 100 points?

I need to calculate the lagrange polynomial which approximates $e^x$ at $101$ points, the points $\frac{k}{101^2}$ for $k\in\{0,1,2\dots 100\}$. I tried the following code: ...
2
votes
0answers
26 views

Choosing suitable polynomial degree based on information in advection stencil

I'm working on a finite volume advection scheme for unstructured meshes which uses a multidimensional polynomial weighted least squares fit for interpolating from cell centres onto faces. In 2D, the ...
1
vote
1answer
196 views

Approximate function following interpolation (Matlab)

How do you approximate a function for interpolated points? I use the natural cubic spline to interpolate points as follows for n = 500 points: ...
4
votes
1answer
240 views

Chebyshev and Legendre expansions

I am looking at approximating my function $f(x)$ using a Chebyshev and Legendre series and I ran into this question. Is interpolation using $n+1$ Chebyshev nodes the same as representing the ...
1
vote
0answers
54 views

Comparison between of higher order interpolations

A while ago I came up with an algorithm which can be used to numerically solve optimal control problems, which basically came down to discretizing the control input $u(t)$ and interpolating this to ...
3
votes
2answers
2k views

C++ Library: What is the common libraries that do polynomial arithmetic?

I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of ...
2
votes
0answers
95 views

C++: How to find the roots of polynomial modulus N [duplicate]

I need to know what library, given a vector of coefficients and modulus N return the roots of polynomial modulus N. The library should support big integer. I'm coding in C++.
19
votes
1answer
605 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 ...