Keywords: Shifted sparse polynomial, Gröbner bases, Complexity. "〉
Springer Online Journal Archives 1860-2000
Abstract. In this paper, we investigate the problem of finding t-sparse shifts for multivariate polynomials. Given a polynomial f∈ℱ[x 1, x 2, …, x n ] of degree d, and a positive integer t, we consider the problem of representing f(x) as a ?-linear combination of the power products of u i where u i = x i −b i for some b i ∈?, an extension of ℱ, for i = 1, …, n, i.e., f = ∑ j F j u αj , in which at most t of the F j are non-zero. We provide sufficient conditions for uniqueness of sparse shifts for multivariate polynomials, prove tight bounds on the degree of the polynomial being interpolated in terms of the sparsity bound t and a bound on the size of the coefficients of the polynomial in the standard representation, and describe two new efficient algorithms for computing sparse shifts for a multivariate polynomial.
Type of Medium: