Details:
Title | Polynomial ring automorphisms, rational -canonical forms, and the assignment problem | Author(s) | S.A. Abramov, M. | 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 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. | Keywords | Polynomial ring automorphisms, Rational normal forms, Rational canonical forms, Product representation of hypergeometric terms | ISSN | 0747-7171 |
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 |
|