Details:
Title  Polynomial ring automorphisms, rational canonical forms, and the assignment problem  Author(s)  S.A. Abramov, M. Petkovšek  Type  Article in Journal  Abstract  We 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 semiperiods 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 wellknown assignment problem of combinatorial optimization. We show how to use these representations of rational functions to obtain succinct representations of σ hypergeometric terms.  Keywords  Polynomial ring automorphisms, Rational normal forms, Rational canonical forms, Product representation of hypergeometric terms  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717110000313 
Language  English  Journal  Journal of Symbolic Computation  Volume  45  Number  6  Pages  684  708  Year  2010  Edition  0  Translation 
No  Refereed 
No 
