Questions tagged [polynomials]
For questions about solving and representing polynomials computationally.
100 questions
2
votes
2
answers
119
views
Gradient descent for solving polynomial equations while encouraging variables to be nonzero
I would like to use gradient descent to "randomly sample" solutions to a set of homogeneous polynomial equations. Because the equations are homogeneous, setting all variables to 0 is a valid ...
- 123
0
votes
1
answer
187
views
Solving a polynomial with NumPy
I'm trying to do something that I thought would be very straightforward but somehow I'm struggling.
I have a time series and I want to extrapolate it, assuming a linear trend, to forecast when will it ...
user782
2
votes
0
answers
98
views
What is the point in non-intrusive Polynomial Chaos output moments?
So I recently learned about Polynomial Chaos Expansion (aka PCE), and it seemed to me that its purpose was to propagate uncertainty from the inputs to the outputs more efficiently (via closed-form ...
- 149
0
votes
1
answer
76
views
Solve bivariate polynomial system
Given a bivariate polynomial system with variables $(x, y, z)$ like
(1) $ f_1 = x * a_1 + y * a_2 + z * a_3 = 0 $
(2) $ f_2 = x * a_4 + y * a_5 + z * a_6 = 0$
(3) $ f_3 = x^2 + y^2 - 1 = 0$
how do I ...
- 11
1
vote
0
answers
74
views
Strategies to solve an equation with a polynomial and a numeric function
I have to solve numerically an equation of the following form:
$$
\sum_{n=0}^m c_n x^n = f(x) x^k
$$
Where the $c_n$ are real values, $k$ is an integer and $f$ can only be evaluated numerically.
The ...
- 153
1
vote
1
answer
133
views
Explicit polynomial for quadratic elements? (FEM)
In this resource the linear (barycentric) elements are explicitly given:
The geometry placement of higher order elements is also given but not expression for the polynomial of $P_2$ is given. I am ...
- 379
1
vote
0
answers
99
views
Integration problem
I want to numerically solve integrals of the form,
$$
I = \int_a^b x^k f(x) dx
$$
where $k$ is a given integer, and $f(x)$ is a cubic polynomial, expressed as,
$$
f(x) = c_0 + c_1 (x - a) + \frac{c_2}{...
- 1,078
2
votes
0
answers
54
views
Software for Smith form or Hermite form of a sparse polynomial matrix
In a current research project, I have a number of matrices with coefficients in ℚ[𝑥] for which I want to understand how their rank depends on the value of the parameter 𝑥.
These matrices are:
...
0
votes
0
answers
48
views
Quadrature rules for products of 2D regions
I am interested in computing integrals of the form $\iint_{P\times P} Q(x_1,x_2,y_2,y_2) dxdy$ where $P$ is a polygon and $Q$ is a polynomial. The coordinates $(x_1,x_2)$ are in the plane of $P$. Of ...
- 1,077
0
votes
0
answers
711
views
Curve fitting using a piecewise polynomial
I am trying to fit a piecewise polynomial function
Code:
...
- 433
0
votes
1
answer
2k
views
Fitting a monotonically increasing spline function
I want to fit a monotonically increasing smooth spline function for a dataset
Code:
...
- 433
0
votes
0
answers
125
views
Recursion relations for integrating Gaussian functions
I'm trying to implement a numerical method used in quantum chemistry from scratch. I'm using this paper as a reference. It's also available on Sci-Hub. So, the method requires calculating integrals of ...
2
votes
1
answer
209
views
Quadrature of rational functions
I have a class of integrals I need to solve numerically which have the form:
$$
I_k = \int_a^b \frac{p_k(x)}{x^k} dx, \quad k = 0, 1, \dots, K
$$
where $p_k(x)$ is a cubic polynomial on the interval $[...
- 1,078
1
vote
0
answers
78
views
Generate polynomial basis through a sequence of SVD
I need help to understand how to use the result given by an algorithm for constructing an orthonormal polynomial basis over $L^{2}(X)$, where $X\subset\mathbb{R}^2$, with respect to the inner product $...
- 219
3
votes
1
answer
101
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 ...
- 215
3
votes
0
answers
92
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 ...
- 130
6
votes
1
answer
568
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 ...
- 475
2
votes
0
answers
110
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 ...
- 31
4
votes
1
answer
356
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 ...
- 41
-1
votes
1
answer
40
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
0
answers
118
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 ...
- 3,225
1
vote
1
answer
73
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}^{...
user37062
1
vote
1
answer
81
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
0
answers
389
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)...
- 61
2
votes
1
answer
91
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 + ...
- 143
2
votes
0
answers
128
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 ...
- 121
1
vote
0
answers
46
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 ...
- 121
2
votes
1
answer
191
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(...
- 295
0
votes
0
answers
46
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 ...
- 101
6
votes
2
answers
144
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,433
6
votes
3
answers
301
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) ...
- 129
1
vote
1
answer
122
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,...
- 29
9
votes
2
answers
604
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 ...
- 273
2
votes
0
answers
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 ...
- 121
5
votes
2
answers
201
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 ...
- 1,031
2
votes
1
answer
62
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, ...
- 21
1
vote
0
answers
63
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 ...
- 111
2
votes
0
answers
46
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 ...
- 121
1
vote
2
answers
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:
...
- 245
5
votes
2
answers
279
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 ...
- 2,165
0
votes
1
answer
154
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
1
answer
4k
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
2
answers
447
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 ...
- 1,006
6
votes
3
answers
191
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,006
1
vote
0
answers
547
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 ...
- 13
0
votes
1
answer
402
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 ...
- 13
4
votes
1
answer
966
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 ...
- 399
2
votes
1
answer
103
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 ...
- 23
1
vote
0
answers
102
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\...
- 283
1
vote
0
answers
63
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 ...
- 11