Let I = f1,..., fm β Q[x1,..., xn] be a zero dimensional radical
ideal defined by polynomials given with exact rational coefficients.
Assume that we are given approximations {z1,..., zk} β Cn for
the common roots {ΞΎ1,..., ΞΎk} = V (I) β Cn. In this paper we
show how to construct and certify the rational entries of Hermite
matrices for I from the approximate roots {z1,..., zk}. When I
is nonradical, we give methods to construct and certify Hermite
matrices for β
I from the approximate roots. Furthermore, we use
signatures of these Hermite matrices to give rational certificates
of nonnegativity of a given polynomial over a (possibly positive
dimensional) real variety, as well as certificates that there is a real
root within an Ξ΅ distance from a given point z β Qn.
more »
« less
Certified Hermite Matrices from Approximate Roots  Univariate Case
Let π1,β¦,ππ be univariate polynomials with rational coefficients and I:=β¨π1,β¦,ππβ©ββ[π₯] be the ideal they generate. Assume that we are given approximations {π§1,β¦,π§π}ββ[π] for the common roots {π1,β¦,ππ}=π(I)ββ . In this study, we describe a symbolicnumeric algorithm to construct a rational matrix, called Hermite matrix, from the approximate roots {π§1,β¦,π§π} and certify that this matrix is the true Hermite matrix corresponding to the roots V(I) . Applications of Hermite matrices include counting and locating real roots of the polynomials and certifying their existence.
more »
« less
 Award ID(s):
 1813340
 NSFPAR ID:
 10195815
 Date Published:
 Journal Name:
 Part of the Lecture Notes in Computer Science book series (LNCS, volume 11989)
 Volume:
 11989
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the jth derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely softO(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 WelchBerlekamp algorithm.more » « less

Let fββ(x) be a nonconstant rational function. We consider βWaringβs problem for f(x), i.e., whether every element of β can be written as a bounded sum of elements of {f(a)β£aββ}. For rational functions of degree 2, we give necessary and sufficient conditions. For higher degrees, we prove that every polynomial of odd degree and every odd Laurent polynomial satisfies Waringβs problem. We also consider the 'easier Waringβs problem': whether every element of β can be represented as a bounded sum of elements of {Β±f(a)β£aββ}. β .more » « less

Amir Hashemi (Ed.)We present Hermite polynomial interpolation algorithms that for a sparse univariate polynomial f with coefficients from a field compute the polynomial from fewer points than the classical algorithms. If the interpolating polynomial f has t terms, our algorithms, require argument/value triples (w^i, f(w^i), f'(w^i)) for i=0,...,t + ceiling( (t+1)/2 )  1, where w is randomly sampled and the probability of a correct output is determined from a degree bound for f. With f' we denote the derivative of f. Our algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases. We have algorithms that can correct errors in the points by oversampling at a limited number of good values. If an upper bound B >= t for the number of terms is given, our algorithms use a randomly selected w and, with high probability, ceiling( t/2 ) + B triples, but then never return an incorrect output. The algorithms are based on Prony's sparse interpolation algorithm. While Prony's algorithm and its variants use fewer values, namely, 2t+1 and t+B values f(w^i), respectively, they need more arguments w^i. The situation mirrors that in algebraic error correcting codes, where the ReedSolomon code requires fewer values than the multiplicity code, which is based on Hermite interpolation, but the ReedSolomon code requires more distinct arguments. Our sparse Hermite interpolation algorithms can interpolate polynomials over finite fields and over the complex numbers, and from floating point data. Our Pronybased approach does not encounter the Birkhoff phenomenon of Hermite interpolation, when a gap in the derivative values causes multiple interpolants. We can interpolate from t+1 values of f and 2t1 values of f'.more » « less

Abstract This paper solves the rational noncommutative analogue of Hilbertβs 17th problem: if a noncommutative rational function is positive semidefinite on all tuples of Hermitian matrices in its domain, then it is a sum of Hermitian squares of noncommutative rational functions. This result is a generalisation and culmination of earlier positivity certificates for noncommutative polynomials or rational functions without Hermitian singularities. More generally, a rational Positivstellensatz for free spectrahedra is given: a noncommutative rational function is positive semidefinite or undefined at every matricial solution of a linear matrix inequality $L\succeq 0$ if and only if it belongs to the rational quadratic module generated by L . The essential intermediate step toward this Positivstellensatz for functions with singularities is an extension theorem for invertible evaluations of linear matrix pencils.more » « less