More Like this

1. Certified Hermite matrices from approximate roots

   https://doi.org/10.1016/j.jsc.2022.12.001  

   Ayyildiz Akoglu, Tulay; Szanto, Agnes (July 2023, Journal of Symbolic Computation)

   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 non-radical, 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 non-negativity 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
2. Hermite Rational Function Interpolation with Error Correction

   https://doi.org/10.1007/978-3-030-60026-6_19  

   Kaltofen, Erich L.; Pernet, Clement; Yang, Zhi-Hong (September 2020, Proc. Computer Algebra in Scientific Computing (CASC) 2020)

   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 j-th 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 soft-O(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 Welch-Berlekamp algorithm. 

   more » « less
3. Waring’s Problem for Rational Functions in One Variable

   https://doi.org/10.1093/qmathj/haz052  

   Im, Bo-Hae; Larsen, Michael (February 2020, The quarterly journal of mathematics)

   Let f∈ℚ(x) be a non-constant 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
4. Sparse Polynomial Hermite Interpolation

   https://doi.org/10.1145/3476446.3535501  

   Kaltofen, Erich L. (July 2022, ISSAC '22 Proc. 2022 ACM Internat. Symp. Symbolic Algebraic Comput.)

   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 Reed-Solomon code requires fewer values than the multiplicity code, which is based on Hermite interpolation, but the Reed-Solomon 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 Prony-based 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 2t-1 values of f'. 

   more » « less
5. Hilbert’s 17th problem in free skew fields

   https://doi.org/10.1017/fms.2021.54  

   Volčič, Jurij (January 2020, Forum of Mathematics, Sigma)

   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