Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient q-Integer Linear Decomposition of Multivariate Polynomials
69
0
0.0
(
0
)
Added by
Hui Huang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present two new algorithms for the computation of the q-integer linear decomposition of a multivariate polynomial. Such a decomposition is essential for the treatment of q-hypergeometric symbolic summation via creative telescoping and for describing the q-counterpart of Ore-Sato theory. Both of our algorithms require only basic integer and polynomial arithmetic and work for any unique factorization domain containing the ring of integers. Complete complexity analyses are conducted for both our algorithms and two previous algorithms in the case of multivariate integer polynomials, showing that our algorithms have better theoretical performances. A Maple implementation is also included which suggests that our algorithms are also much faster in practice than previous algorithms.
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 propose a functional implementation of emph{Multivariate Tower Automatic Differentiation}. Our implementation is intended to be used in implementing $C^infty$-structure computation of an arbitrary Weil algebra, which we discussed in the previous work.
We propose a new algorithm for multiplying dense polynomials with integer coefficients in a parallel fashion, targeting multi-core processor architectures. Complexity estimates and experimental comparisons demonstrate the advantages of this new approach.
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.
The aim of the paper is to produce new families of irreducible polynomials, generalizing previous results in the area. One example of our general result is that for a near-separated polynomial, i.e., polynomials of the form $F(x,y)=f_1(x)f_2(y)-f_2(x)f_1(y)$, then $F(x,y)+r$ is always irreducible for any constant $r$ different from zero. We also provide the biggest known family of HIP polynomials in several variables. These are polynomials $p(x_1,ldots,x_n) in K[x_1,ldots,x_n]$ over a zero characteristic field $K$ such that $p(h_1(x_1),ldots,h_n(x_n))$ is irreducible over $K$ for every $n$-tuple $h_1(x_1),ldots,h_n(x_n)$ of non constant one variable polynomials over $K$. The results can also be applied to fields of positive characteristic, with some modifications.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
