Rational canonical forms and efficient representations of hypergeometric terms

ABSTRACT

We propose four multiplicative canonical forms that exhibit the shift structure of a given rational function. These forms in particular allow one to represent a hypergeometric term efficiently. Each of these representations is optimal in some sense.

REFERENCES

• 1: Sergei A. Abramov , Manuel Bronstein, Hypergeometric dispersion and the orbit problem, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.8-13, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345561]
• 2: S. A. Abramov , M. Petkovsek, Rational normal forms and minimal decompositions of hypergeometric terms, Journal of Symbolic Computation, v.33 n.5, p.521-543, May 2002 [doi>10.1006/jsco.2002.0529]
• 3: R. M. Karp, S.-Y. R. Li, Two special cases of the assignment problem. Discrete Math. 13 (1975) 129--142.
• 4: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 5: M. Petkovšek, H. S. Wilf, D. Zeilberger. A=B. A K Peters, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Design

Keywords:
canonical forms, efficient representations, hypergeometric terms, rational functions