Efficient q-integer linear decomposition of multivariate polynomials

DOI10.1016/J.JSC.2021.02.001MaRDI QIDQ2029008zbMATH OpenOpenAlexFDO

Authors Hui Huang, Mark Giesbrecht, G. Labahn, Eugene Zima

Publication date 3 June 2021

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.00124

zbMATH Keywords

\(q\)-analoguecreative telescopinginteger-linear polynomialsNewton polytopeOre-Sato theorypolynomial decomposition

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Difference algebra (12H10) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Symbolic computation and algebraic computation (68W30)

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.

Recommendations

• Efficient integer-linear decomposition of multivariate polynomials
• A q-analogue of the modified Abramov-Petkovšek reduction
• Algorithms for \(q\)-hypergeometric summation in computer algebra
• scientific article; zbMATH DE number 1023404
• Efficient rational creative telescoping

Cites work

• A criterion for the applicability of Zeilberger's algorithm to rational functions
• An algorithmic proof theory for hypergeometric (ordinary and ``\(q\)) multisum/integral identities
• Applicability of the \(q\)-analogue of Zeilberger's algorithm
• Bounds for resultants of univariate and bivariate polynomials
• Efficient integer-linear decomposition of multivariate polynomials
• Factoring multivariate polynomials via partial differential equations
• scientific article; zbMATH DE number 3147675 (Why is no real title available?)
• scientific article; zbMATH DE number 3955412 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 1023404 (Why is no real title available?)
• scientific article; zbMATH DE number 2008526 (Why is no real title available?)
• Lectures on Polytopes
• Modern computer algebra
• On computation of the greatest common divisor of several polynomials over a finite field.
• On multiplication and factorization of polynomials. I: Lexicographic orderings and extreme aggregates of terms
• On the \(q\)-analogue of Zeilberger's algorithm to rational functions
• On the structure of multivariate hypergeometric terms.
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Proof of the Wilf-Zeilberger conjecture for mixed hypergeometric terms
• The Ore-Sato theorem and shift exponents in the \(q\)-difference case

Cited in

(4)

• A q-analogue of the modified Abramov-Petkovšek reduction
• A Fast Schur–Euclid-Type Algorithm for Quasiseparable Polynomials
• Efficient integer-linear decomposition of multivariate polynomials
• A unified reduction for hypergeometric and q-hypergeometric creative telescoping

Describes a project that uses

Uses Software

• qZeil
• Maple

This page was built for publication: Efficient \(q\)-integer linear decomposition of multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029008)