Computer Science – Symbolic Computation
Scientific paper
2008-10-31
Computational Complexity, Vol. 19, No 3., pp. 333-354, 2010
Computer Science
Symbolic Computation
22 pages, to appear in Computational Complexity
Scientific paper
10.1007/s00037-010-0294-0
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.
Giesbrecht Mark
Roche Daniel S.
No associations
LandOfFree
Interpolation of Shifted-Lacunary Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interpolation of Shifted-Lacunary Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interpolation of Shifted-Lacunary Polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-457045