Sparse shifts for univariate polynomials

DOI10.1007/BF01293594MaRDI QIDQ1924546zbMATH OpenFDO

Authors Y. N. Lakshman, B. David Saunders

Publication date 15 April 1997

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01293594

zbMATH Keywords

algorithmpolynomial time algorithmrational polynomialrationalitysparse decompositionsparse shiftuniquenessunivariate polynomials

Mathematics Subject Classification ID

Numerical computation of solutions to single equations (65H05) Symbolic computation and algebraic computation (68W30)

Review text

A \(t\)-sparse shift for a polynomial \(f(x)\) over the rationals with degree greater than or equal to \(t\) is an algebraic number \(\alpha\) such that \(f(x)= \sum a_i (x- \alpha)^i\) with at most \(t\) of the coefficients \(a_i\) nonzero. The authors develop some condition on the uniqueness and rationality of the \(t\)-sparse shift and an algorithm for computing a sparse shift for a given polynomial. In addition, a criterion is given for distinguishing two polynomials which are sparse with respect to bounded shifts together with a description of a polynomial time algorithm for computing sparse decomposition of univariate polynomials.

Recommendations

• scientific article; zbMATH DE number 1263400
• scientific article; zbMATH DE number 1254239
• Algorithms for computing sparse shifts for multivariate polynomials
• Sparse generalised polynomials
• On some computations on sparse polynomials
• Sparsity in sums of squares of polynomials
• Sparse univariate polynomials with many roots over finite fields
• Some properties of a class of sparse polynomials
• On solving univariate sparse polynomials in logarithmic time
• Sparse Polynomial Approximation of High-Dimensional Functions

Cites work

• Computational Complexity of Sparse Rational Interpolation
• Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Global time evolution of an axisymmetric vortex ring at low Reynolds numbers
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• scientific article; zbMATH DE number 1263351 (Why is no real title available?)
• scientific article; zbMATH DE number 1263400 (Why is no real title available?)
• scientific article; zbMATH DE number 503193 (Why is no real title available?)
• Interpolating polynomials from their values
• On the invariance of chains of fields
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Polynomial decomposition algorithms
• Randomized Interpolation and Approximation of Sparse Polynomials
• Sparse Polynomial Interpolation in Nonstandard Bases
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators

Cited in

(7)

• Algorithms for computing sparse shifts for multivariate polynomials
• On the linear independence of shifted powers
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Computing the multilinear factors of lacunary polynomials without heights
• Sparse polynomial interpolation by variable shift in the presence of noise and outliers in the evaluations
• scientific article; zbMATH DE number 1254239 (Why is no real title available?)
• scientific article; zbMATH DE number 1263400 (Why is no real title available?)

This page was built for publication: Sparse shifts for univariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924546)