Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitlePolynomial ring automorphisms, rational -canonical forms, and the assignment problem
Author(s) S.A. Abramov, M. Petkovšek
TypeArticle in Journal
AbstractWe investigate the representations of a rational function R ∈ k ( x ) where k is a field of characteristic zero, in the form R = K ⋅ σ S / S . Here K , S ∈ k ( x ) , and σ is an automorphism of k ( x ) which maps k [ x ] onto k [ x ] . We show that the degrees of the numerator and denominator of K are simultaneously minimized iff K = r / s where r , s ∈ k [ x ] and r is coprime with σ n s for all n ∈ Z . Assuming existence of algorithms for computing orbital decompositions of R ∈ k ( x ) and semi-periods of irreducible p ∈ k [ x ] ∖ k , we present an algorithm for minimizing w ( deg num ( S ) , deg den ( S ) ) among representations with minimal K , where w is any appropriate weight function. This algorithm is based on a reduction to the well-known assignment problem of combinatorial optimization. We show how to use these representations of rational functions to obtain succinct representations of σ -hypergeometric terms.
KeywordsPolynomial ring automorphisms, Rational normal forms, Rational canonical forms, Product representation of hypergeometric terms
URL http://www.sciencedirect.com/science/article/pii/S0747717110000313
JournalJournal of Symbolic Computation
Pages684 - 708
Translation No
Refereed No