Interpolation of Shifted-Lacunary Polynomials |
| |
Authors: | Mark Giesbrecht Daniel S Roche |
| |
Affiliation: | 1. School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
|
| |
Abstract: | Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQx]f \in {\mathbb{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 \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|
|