Questions tagged [polynomials]

For questions about solving and representing polynomials computationally.

Filter by
Sorted by
Tagged with
3
votes
1answer
85 views

What does this function called LAGRANGE2 do?

While browsing a disk image from the Soviet mainframe BESM-6, I've found some bits and pieces of a computational math library for Algol-60, stored in plaintext (if the Soviet GOST 10859 encoding with ...
3
votes
0answers
39 views

Sufficient condition for real roots of a polynomial of order $n>5$ with arbitrary real coefficients

I ask for help in solving the problem. I am developing an optimization program that selects the coefficients of a polynomial of order $n> 5$ so that all its zeros are just real numbers. And I ...
6
votes
1answer
475 views

Polynomial approximation for floating-point arithmetic

I cannot remember where I picked this up, but during my time reading about polynomial approximation for floating-point arithmetic of sin(x), I vaguely remember that ...
2
votes
0answers
89 views

Solve Rational Equation for Root Music in MATLAB

I'm trying to estimate DOA in the Hybrid architecture using root music so I need to solve the attached equation to find the roots for the Root_Music equation in Matlab. Does anyone have an idea for ...
4
votes
1answer
171 views

Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?

I know that NumPy has linalg.cond(A) to find the condition number of a matrix A. But, if I want to find the condition numbers of the roots of a large polynomial ...
-1
votes
1answer
38 views

Time complexity and its formula [closed]

Is there any example support the case of $O(n^k)$ where $k$ has a fixed calculated value for every $n$ and $k$ is not a constant value for all $n$. As $k$ depends on the value of $n$ in polynomial ...
4
votes
0answers
58 views

Pade-like approximation, but force poles to be negative

Are there techniques to form a Pade approximation (or Pade-like approximation), except force the poles of the rational function to be negative? I am trying to use Pade approximations to extrapolate a ...
1
vote
1answer
67 views

Gauss Integration of $\sqrt(x)$

I want to construct a gauss integration for the weight function $w(x) = x^{1/2}$ for $$\int_{0}^{1}x^{1/2}f(x)dx = a_{1}f(x_{1})+a_{2}f(x_{2})$$ Solving \begin{align*} a_{1}+a_{2} =& \int_{0}^{...
1
vote
1answer
48 views

Algorithm to determine if a polynomial has any complex roots

Is there a simple algorithm to determine if a given polynomial (with all real coefficients) has all real roots? I do not need to know what the roots are; I just what to know if a given polynomial has ...
5
votes
0answers
272 views

Polynomial rooting - fast root finding

I need to solve a rooting problem of a polynomial (the order of which is 2(N-1), where N=48). So far I'm using Python Numpy algorithm (that relies on computing the eigenvalues of the companion matrix)...
2
votes
1answer
79 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
83 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
37 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 ...
2
votes
1answer
137 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(...
0
votes
0answers
38 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
137 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\...
6
votes
3answers
272 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) ...
1
vote
1answer
115 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,...
9
votes
2answers
424 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 ...
2
votes
0answers
2k 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
180 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 ...
2
votes
1answer
52 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
59 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
41 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 ...
1
vote
2answers
1k 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: ...
5
votes
2answers
208 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 ...
0
votes
1answer
71 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(...
0
votes
1answer
2k 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 ...
4
votes
2answers
281 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 ...
6
votes
3answers
150 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 ...
1
vote
0answers
506 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
282 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 ...
4
votes
1answer
537 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
71 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
88 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
59 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
138 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 ...
1
vote
1answer
326 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
372 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
175 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 ...
1
vote
0answers
82 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
97 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 ...
4
votes
2answers
309 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 ...
5
votes
1answer
430 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 ...
1
vote
0answers
342 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
27 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 ...
10
votes
3answers
1k 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. ...
2
votes
1answer
525 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
1answer
226 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
2answers
333 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 function ...