Algorithms for Computing Sparse Shifts for Multivariate Polynomials |
| |
Authors: | Dima Yu. Grigoriev Y. N. Lakshman |
| |
Affiliation: | (1) IRMAR Université Rennes-1 Campus Beaulieu, 35042 Rennes, France (e-mail: dima@maths.univ-rennes1.fr), FR;(2) Computing Science Research, Bell Labs., 600 Mountain Hill, Murray Hill, NJ, 07974, USA (e-mail: ynl@research.bell-labs.com), US |
| |
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. Received: January 30, 1996; revised version: January 15, 2000 |
| |
Keywords: | : Shifted sparse polynomial, Gr?bner bases, Complexity. " > |
本文献已被 SpringerLink 等数据库收录! |
|