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 |
|
