Algorithms for Computing Sparse Shifts for Multivariate Polynomials

In this paper, we investigate the problem of finding t-sparse shifts for multivariate polynomials. Given a polynomial f∈ℱx ₁, x ₂, …, 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. Received: January 30, 1996; revised version: January 15, 2000