Sparse shifts for univariate polynomials
type: Item
instance of: scholarly article
title: Sparse shifts for univariate polynomials
zbMATH Open document ID: 0953.12006
DOI: 10.1007/BF01293594
author: Y. N. Lakshman
author: B. David Saunders
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1997-04-15T00:00:00Z
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.
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 65H05
zbMATH DE Number: 936994
zbMATH Keywords: sparse shift
zbMATH Keywords: rational polynomial
zbMATH Keywords: uniqueness
zbMATH Keywords: rationality
zbMATH Keywords: algorithm
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: sparse decomposition
zbMATH Keywords: univariate polynomials
reviewed by: Joseph J. Liang
MaRDI profile type: Publication
cites work: On the invariance of chains of fields
cites work: On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
cites work: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
cites work: Computational Complexity of Sparse Rational Interpolation
cites work: Q3135191
cites work: The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
cites work: Q4279514
cites work: Q4234231
cites work: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
cites work: Global time evolution of an axisymmetric vortex ring at low Reynolds numbers
cites work: Polynomial decomposition algorithms
cites work: Sparse Polynomial Interpolation in Nonstandard Bases
cites work: Q4234292
cites work: Computing Rational Zeros of Integral Polynomials by p-Adic Expansion
cites work: Randomized Interpolation and Approximation of Sparse Polynomials
cites work: Interpolating polynomials from their values
Recommended article: Q4234292
Recommended article: Q4227280
Recommended article: Algorithms for computing sparse shifts for multivariate polynomials
Recommended article: Sparse generalised polynomials
Recommended article: Q5002654
Recommended article: Sparsity in sums of squares of polynomials
Recommended article: Sparse univariate polynomials with many roots over finite fields
Recommended article: Some properties of a class of sparse polynomials
Recommended article: On solving univariate sparse polynomials in logarithmic time
Recommended article: Sparse Polynomial Approximation of High-Dimensional Functions
description: scientific article; zbMATH DE number 936994