12 votes
Accepted

Benchmarks for Gröbner bases and polynomial system solution

I posted some benchmarks here: http://www.cecm.sfu.ca/~rpearcea/mgb.html (archived copy) These are for total degree orders. To solve systems you typically need to do more work. Timings are for a ...
user avatar
10 votes

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

According to Wolfram Alpha, $x^5+3(x-1)=0$ has no closed-form solution, so you can forget about a nice closed-form expression. :) I see nothing wrong with Newton's method; it should be quick and ...
user avatar
9 votes
Accepted

Interpolating a mathematical function using a Hermite Cubic Finite Element Space

Short answer You are missing the Jacobian of the transformation for the derivatives. Long answer The conditions that you propose for your interpolator translate into the following system of ...
user avatar
  • 7,902
9 votes

Benchmarks for Gröbner bases and polynomial system solution

Googling benchmark polynomial systems leads to a few hits, including the University of Mannheim's Computer Algebra Benchmark Initiative. Sadly, most of these are ...
user avatar
9 votes
Accepted

Accurate Polynomial Evaluation in Floating Point

Horner is indeed the most stable way to evaluate a polynomial (and you get the bonus of evaluating its derivatives with not too much extra cost). Higham presents a nice error analysis of the algorithm ...
user avatar
  • 6,046
8 votes

Polynomial approximation

$\mathbf{A}$ is an $(n+1) \times (n+1)$ matrix. It can be obtained as follows: $\textbf{A} = \left[ \matrix{1 & 1 & 1 & \cdots & 1 \cr x_0 & x_1 & x_2 & \...
user avatar
  • 2,139
8 votes

Numerical stability of higher order Zernike polynomials

A possible solution (suggested by @gammatester) is to use Jacobi polynomials. This circumvents the problem of catastrophic cancellation in adding the large polynomial coefficients by 'naive' ...
user avatar
  • 273
8 votes
Accepted

Polynomial approximation for floating-point arithmetic

The sine is an odd function, so you want that also in an approximation. A polynomial with $p(0)=0$ can be factored as $p(x)=xq(x)$, so $q(x)\approx \frac{\sin(x)}{x}$. Each interval $[2^n,2^{n+1})$ ...
user avatar
  • 3,501
7 votes
Accepted

roots of polynomials with small coefficients

Note that, if $D$ is invertible, the eigenvalues of $A$ and $DAD^{-1}$ are the same. You can avoid floating-point underflow when forming the matrix by scaling the companion matrix by a diagonal ...
user avatar
  • 372
7 votes
Accepted

Numerical stability of higher order Zernike polynomials

In this paper, Honarvar and Paramesran derive an interesting method to compute the radial Zernike polynomials in a very nice recursive way. The recursion formula is surprisingly straightforward, ...
user avatar
  • 551
6 votes

Benchmarks for Gröbner bases and polynomial system solution

Always keep in mind that the results of any benchmark will depend, in addition to the problem's size, on the base field over which the polynomial ring is defined (rational numbers or integers modulo ...
user avatar
6 votes
Accepted

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

Generally speaking, $P(A)$ would not be close to the zero matrix: if you compute the polynomial $P$ to a relative accuracy of $\epsilon$ (which is $10^{-16}$ in double-precision), then $P(A)$ would be ...
user avatar
  • 11.4k
6 votes

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

The condition number of a root $r$ of a polynomial $p$ is $$ \kappa := \frac{\left\| p \right\|}{|rp'(r)|} $$ There is some arbitrariness in the choice of norm which affects the definition of the ...
user avatar
  • 2,001
5 votes

What are the numerical methods for huge polynomial systems?

Certified homotopy continuation methods are used both for finding roots and for proving that they indeed exist (inside a certain interval). A quick web search turned out this paper: Reliable ...
user avatar
5 votes

Chebyshev and Legendre expansions

What you are doing here is projecting a function onto a basis of a finite dimensional space of polynomials. All you use in the formulas you show is that the basis $T_k$ is orthogonal, i.e., that $\...
user avatar
5 votes

Building Gaussian-type quadrature schemes with Zernike polynomials

Unfortunately the 1D reasoning will not directly carry into 2D and beyond. Depending on the domain for your integral, you will have considerable latitude in the node choice - but of course the ...
user avatar
5 votes

Building Gaussian-type quadrature schemes with Zernike polynomials

Yes, one can extend the Gaussian quadrature (in one dimension) to multiple dimensions. Often this is called cubature. Much work on this has been done by Ronald Cools and collaborators (see his ...
user avatar
  • 6,046
5 votes

Fast evaluation functions given by straight-line programs

OK, you have a very nice problem, I tried to run some benchmarks. First, I don't have your parameters so I used your small example. Second, since you do not specify the language, I used C + GSL (...
user avatar
  • 101
5 votes
Accepted

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

The problem that you are seeing is a well known problem of these basis functions: $$\phi_{m,n}(x,y) = x^{m}y^{n}$$ I quote from here: The reason why the coefficient matrix is nearly singular and ...
user avatar
5 votes

Gauss Integration of $\sqrt(x)$

Quadrature points $x_1,x_2$ are also unknown. You need two more equations corresponding to $x^2$ and $x^3$. Then you solve for $a_1, a_2, x_1, x_2$.
user avatar
  • 2,983
5 votes
Accepted

Quadrature of rational functions

Choose four collocation points in the interval $[a,b]$, e.g., $ x_0=a\\ x_1=a + (1/3)(b-a)\\ x_2=a + (2/3)(b-a)\\ x_3=b $ and form a matrix $M$ \begin{bmatrix} 1 & x_0 & x_0^2 & x_0^3 \\ 1 ...
user avatar
4 votes

Problems Implementing the Remez Algorithm

Let's use the example (approximate the square root function on $[0.25,1.0]$ with a quartic polynomial) to step through your calculations. I suspect that the code is going to work with only modest ...
user avatar
  • 3,189
4 votes
Accepted

Polynomial approximation

You can easily do this with for loops. Just use n to define your loop limits. Here's a fully functional solution for MATLAB (just define n and x first): ...
user avatar
4 votes

What are the numerical methods for huge polynomial systems?

For this kind of large scale problem, using method like Gröbner basis, or other generally used to solve polynomial system, require lots of calculation time and many times your "solution" is so big you ...
user avatar
  • 171
4 votes

Matlab symbolic differentiation of Legendre polynomials

Philips in 1988 proved the following relationship: If $f(x)$ is an infinitely differentiable function defined on the interval $[-1,+1]$ and its Legendre expansion is given by $f(x) = \sum_{n=0}^{\...
user avatar
  • 6,046
4 votes

Intervals where the sign of a polynomial can be computed reliably

Yes. You can compute a running error bound, i.e, a number $\mu$ such that the difference between the exact value of $y = p(x)$ and the computed value satisfies $\hat{y}$ satisfies $$|y - \hat{y}| \leq ...
user avatar
4 votes

Find the roots of a complicated polynomial

One technique is to use a library with arbitrary large integers and use fixed point arithmetic. Just scale up x by some integer factor, then compute your polynomial in fixed-point, keeping only the ...
user avatar
  • 141
4 votes
Accepted

Differentiation Matrix In DG-FEM - Hesthaven/Warburton

Taking your questions in order, the definition of $D_r$ as the operator converting the nodal values of $u_h$ into derivatives follows immediately from the definition, although the notation is a little ...
user avatar
  • 2,189
3 votes
Accepted

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

By using orthonormal polynomial basis functions, then you do not need to solve a linear set of equations in order to get the polynomial coefficients, similar to the Fourier series coefficients. ...
user avatar
  • 430
3 votes

Accurate Polynomial Evaluation in Floating Point

The stability of Horner can be improved by subtracting a constant from each $x$ in the Horner form. This is described in "Stable Evaluation of Polynomials" by C. Mesztenyi and C. Witzgall, ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible