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 ...
- 236
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 ...
- 11.1k
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 ...
- 12.2k
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 ...
- 8,370
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' ...
- 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})$ ...
- 5,544
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, ...
- 561
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 ...
- 11.4k
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 ...
- 3,994
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 ...
- 2,145
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 ...
- 6,169
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 ...
- 3,273
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 $\...
- 54.2k
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 (...
- 201
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 ...
- 2,332
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$.
- 2,993
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 ...
- 2,440
4
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, ...
- 41
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}^{\...
- 6,169
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 ...
- 1,391
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 ...
- 2,229
4
votes
What does this function called LAGRANGE2 do?
From the name, the error message, and the code, it appears that this code is doing Lagrange polynomial interpolation for a function $f(x)$, given
$x_{1} < x_{2} < \ldots < x_{n}$
and function ...
- 18.5k
3
votes
Accurate evaluation of the sign of a polynomial
Compensated Horner method (http://www-pequan.lip6.fr/~jmc/polycopies/Compensation-horner.pdf) has an error bound of the form
$$ |\mathrm{comphorner}(p, x) - p(x)| \leq u|p(x)| + \gamma_{2n}^2\tilde p(...
- 11.4k
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. ...
- 450
3
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 ...
- 131
3
votes
Fast evaluation functions given by straight-line programs
Once you're at the level of a long list of expressions, there is little you can still do other than hope that the compiler finds opportunities for optimization at the assembly level. This may bring ...
- 54.2k
3
votes
Positive root of $x^q + bx - b$
You have demonstrated that the polynomial has only a single positive root (I assume here that you are only interested in positive real roots). Using Cauchy's upper bound for polynomial roots $$1+ \max\...
- 6,169
3
votes
Accepted
Fitting a monotonically increasing spline function
A smoothing spline might be good enough in your case. For example, scipy.interpolate.UnivariateSpline implements this.
You can use it in the following way:
...
- 459
2
votes
Accurate Polynomial Evaluation in Floating Point
As an alternative you may use the barycentric Lagrange basis which has the same evaluation complexity as the Newton basis. The barycentric formulation is also used in the MATLAB Chebfun implementation....
- 1,253
2
votes
Approximate function following interpolation (Matlab)
I think you want to use polyfit on the original data, not the already interpolated data.
p = polyfit(t,z,2);
Now ...
- 541
Only top scored, non community-wiki answers of a minimum length are eligible