Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterpolation of Shifted-Lacunary Polynomials
253
0
0.0
(
0
)
Added by
Daniel Roche
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d. Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable.
We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in $ell^n$ where $ell$ is the lacunary size of the input polynomial and $n$ its number of variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in $ell$ and $n$. Over other fields of characteristic zero and finite fields of large characteristic, our algorithms compute the multilinear factors having at least three monomials of multivariate polynomials. Lower bounds are provided to explain the limitations of our algorithm. As a by-product, we also design polynomial-time deterministic polynomial identity tests for families of polynomials which were not known to admit any. Our results are based on so-called Gap Theorem which reduce high-degree factorization to repeated low-degree factorizations. While previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, our Gap Theorems only depend on the exponents of the polynomials. This makes our algorithms more elementary and general, and faster in most cases.
We present a new algorithm for the computation of the irreducible factors of degree at most $d$, with multiplicity, of multivariate lacunary polynomials over fields of characteristic zero. The algorithm reduces this computation to the computation of irreducible factors of degree at most $d$ of univariate lacunary polynomials and to the factorization of low-degree multivariate polynomials. The reduction runs in time polynomial in the size of the input polynomial and in $d$. As a result, we obtain a new polynomial-time algorithm for the computation of low-degree factors, with multiplicity, of multivariate lacunary polynomials over number fields, but our method also gives partial results for other fields, such as the fields of $p$-adic numbers or for absolute or approximate factorization for instance. The core of our reduction uses the Newton polygon of the input polynomial, and its validity is based on the Newton-Puiseux expansion of roots of bivariate polynomials. In particular, we bound the valuation of $f(X,phi)$ where $f$ is a lacunary polynomial and $phi$ a Puiseux series whose vanishing polynomial has low degree.
This paper is concerned with exact real solving of well-constrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, and to determine their intersection multiplicities. We present three algorithms and analyze their asymptotic bit complexity, obtaining a bound of $sOB(N^{14})$ for the purely projection-based method, and $sOB(N^{12})$ for two subresultant-based methods: this notation ignores polylogarithmic factors, where $N$ bounds the degree and the bitsize of the polynomials. The previous record bound was $sOB(N^{14})$. Our main tool is signed subresultant sequences. We exploit recent advances on the complexity of univariate root isolation, and extend them to sign evaluation of bivariate polynomials over two algebraic numbers, and real root counting for polynomials over an extension field. Our algorithms apply to the problem of simultaneous inequalities; they also compute the topology of real plane algebraic curves in $sOB(N^{12})$, whereas the previous bound was $sOB(N^{14})$. All algorithms have been implemented in MAPLE, in conjunction with numeric filtering. We compare them against FGB/RS, system solvers from SYNAPS, and MAPLE libraries INSULATE and TOP, which compute curve topology. Our software is among the most robust, and its runtimes are comparable, or within a small constant factor, with respect to the C/C++ libraries. Key words: real solving, polynomial systems, complexity, MAPLE software
Given a straight-line program whose output is a polynomial function of the inputs, we present a new algorithm to compute a concise representation of that unknown function. Our algorithm can handle any case where the unknown function is a multivariate polynomial, with coefficients in an arbitrary finite field, and with a reasonable number of nonzero terms but possibly very large degree. It is competitive with previously known sparse interpolation algorithms that work over an arbitrary finite field, and provides an improvement when there are a large number of variables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
