skip to main content
10.1145/3326229.3326261acmotherconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

Efficient Integer-Linear Decomposition of Multivariate Polynomials

Published: 08 July 2019 Publication History

Abstract

We present a new algorithm for the computation of the integer-linear decomposition of a multivariate polynomial. Such a decomposition is used in Ore-Sato theory and discrete creative telescoping, for example to detect applicability of Zeilberger's algorithm to a hypergeometric term. Our algorithm is quite straightforward, requiring only basic polynomial arithmetic along with efficient rational root finding. We present complete complexity analyses for both our and previous algorithms in the case of bivariate integer polynomials, and show that our method has a better theoretical performance. We also provide a Maple implementation which shows that our method is faster in practice than previous algorithms.

References

[1]
S. A. Abramov. 2003. When does Zeilberger's algorithm succeed? Adv. in Appl. Math. 30, 3 (2003), 424--441.
[2]
S. A. Abramov and H. Q. Le. 2002. A criterion for the applicability of Zeilberger's algorithm to rational functions. Discrete Math. 259, 1--3 (2002), 1--17.
[3]
S. A. Abramov and M. Petkovek. 2001. Proof of a conjecture of Wilf and Zeilberger. Preprints Series of the Institute of Mathematics, Physics and Mechanics 39(748)(2001), Ljubljana.
[4]
S. A. Abramov and M. Petkovek. 2002. On the structure of multivariate hypergeometric terms. Adv. in Appl. Math. 29, 3 (2002), 386--411.
[5]
S. Chen, Q.-H. Hou, G. Labahn, and R.-H. Wang. 2016. Existence problem of telescopers: beyond the bivariate case. In Proceedings of ISSAC'16. ACM, New York, 167--174.
[6]
S. Chen and C. Koutschan. 2019. Proof of the Wilf-Zeilberger conjecture for mixed hypergeometric terms. J. Symbolic Comput. 93 (2019), 133--147.
[7]
G. E. Collins and M. J. Encarnación. 1995. Efficient rational number reconstruction. J. Symbolic Comput. 20, 3 (1995), 287--297.
[8]
A. Conflitti. 2003. On computation of the greatest common divisor of several polynomials over a finite field. Finite Fields Appl. 9, 4 (2003), 423--431.
[9]
S. Gao. 2003. Factoring multivariate polynomials via partial differential equations. Math. Comp. 72, 242 (2003), 801--822.
[10]
J. von zur Gathen. 1990. Functional decomposition of polynomials: the tame case. J. Symbolic Comput. 9, 3 (1990), 281--299.
[11]
J. von zur Gathen and J. Gerhard. 2013. Modern Computer Algebra (third ed.). Cambridge University Press, Cambridge. xiv+795 pages.
[12]
J. Gerhard. 2004. Modular Algorithms in Symbolic Summation and Symbolic Integration (Lecture Notes in Computer Science). Springer-Verlag.
[13]
M. Giesbrecht, H. Huang, G. Labahn, and E. Zima. 2019. Efficient rational creative telescoping. In preparation.
[14]
E. Kaltofen. 1985. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput. 14, 2 (1985), 469-- 489.
[15]
H. Q. Le. 2003. A direct algorithm to construct the minimal Z-pairs for rational functions. Adv. in Appl. Math. 30, 1--2 (2003), 137--159.
[16]
Z. Li and Y. Zhang. 2013. An algorithm for decomposing multivariate hypergeometric terms. A contributed talk in CM2013.
[17]
R. Loos. 1983. Computing rational zeros of integral polynomials by p-adic expansion. SIAM J. Comput. 12, 2 (1983), 286--293.
[18]
O. Ore. 1930. Sur la forme des fonctions hypergéométriques de plusieurs variables. J. Math. Pures Appl. (9) 9, 4 (1930), 311--326.
[19]
G. H. Payne. 1997. Multivariate Hypergeometric Terms. Ph.D. Dissertation. Pennsylvania State University, Pennsylvania, USA. Advisor(s) Andrews, George E.
[20]
M. Sato. 1990. Theory of prehomogeneous vector spaces (algebraic part)-the English translation of Sato's lecture from Shintani's note. Nagoya Math. J. 120 (1990), 1--34. Notes by Takuro Shintani, Translated from the Japanese by Masakazu Muro.
[21]
B. M. Trager. 1976. Algebraic factoring and rational function integration. In Proceedings of SYMSAC'76. ACM, New York, 219--226.

Cited By

View all
  • (2021)Efficient rational creative telescopingJournal of Symbolic Computation10.1016/j.jsc.2021.07.005Online publication date: Jul-2021
  • (2021)Efficient q-Integer Linear Decomposition of Multivariate PolynomialsJournal of Symbolic Computation10.1016/j.jsc.2021.02.001Online publication date: Feb-2021

Index Terms

  1. Efficient Integer-Linear Decomposition of Multivariate Polynomials

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    ISSAC '19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation
    July 2019
    418 pages
    ISBN:9781450360845
    DOI:10.1145/3326229
    • General Chairs:
    • James Davenport,
    • Dongming Wang,
    • Program Chair:
    • Manuel Kauers,
    • Publications Chair:
    • Russell Bradford
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 July 2019

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. creative telescoping
    2. integer-linear polynomials
    3. ore-sato theory
    4. polynomial decomposition

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    ISSAC '19

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)11
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 10 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Efficient rational creative telescopingJournal of Symbolic Computation10.1016/j.jsc.2021.07.005Online publication date: Jul-2021
    • (2021)Efficient q-Integer Linear Decomposition of Multivariate PolynomialsJournal of Symbolic Computation10.1016/j.jsc.2021.02.001Online publication date: Feb-2021

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media