Interpolation of shifted-lacunary polynomials
From MaRDI portal
Publication:626682
DOI10.1007/S00037-010-0294-0zbMATH Open1235.68327arXiv0810.5685OpenAlexW2167854544MaRDI QIDQ626682FDOQ626682
Authors: Daniel S. Roche, Mark Giesbrecht 
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Abstract: Given a "black box" function to evaluate an unknown rational polynomial f in Q[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity t, the shift s (a rational), the exponents 0 <= e1 < e2 < ... < et, and the coefficients c1,...,ct in Q{0} such that f(x) = c1(x-s)^e1+c2(x-s)^e2+...+ct(x-s)^et. The computed sparsity t is absolutely minimal over any shifted power basis. The novelty of our algorithm is that the complexity is polynomial in the (sparse) representation size, and in particular is logarithmic in deg(f). Our method combines previous celebrated results on sparse interpolation and computing sparsest shifts, and provides a way to handle polynomials with extremely high degree which are, in some sense, sparse in information.
Full work available at URL: https://arxiv.org/abs/0810.5685
Recommendations
- Sparse polynomial interpolation with finitely many values for the coefficients
- scientific article; zbMATH DE number 503193
- Sparse Polynomial Interpolation in Nonstandard Bases
- scientific article; zbMATH DE number 1263400
- An algorithm for symbolic-numeric sparse interpolation of multivariate polynomials whose degree bounds are unknown
Cited In (6)
- Interpolation of polynomials given by straight-line programs
- Sparse Polynomial Interpolation in Nonstandard Bases
- A nearly optimal algorithm to decompose binary forms
- On the codimension of the singularity at the origin for networked delay systems
- Lacunary interpolation by cosine polynomials
- Supersparse black box rational function interpolation
This page was built for publication: Interpolation of shifted-lacunary polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626682)
