Polynomial ring automorphisms, rational (w,sigma)-canonical forms, and the assignment problem (Prof. Marko Petkovsek)
Sprache des Titels:
We investigate representations of a rational function R in k(x) in the
form R = K * sigma S / S where K, S are again in k(x) and sigma is an
automorphism of k(x) such that sigma(k[x]) = k[x] and sigma(k) = k.
There are infinitely many such representations, so we begin by showing
how to minimize the degrees of the numerator and denominator of K
simultaneously. Then we present an algorithm for minimizing w(deg num S,
deg den S) among all representations with minimal K, where w is any
appropriate weight function. This algorithm is based on reduction to the
so-called assignment problem of combinatorial optimization. Finally we
show how to use these representations to obtain succinct representations
of sigma-hypergeometric terms.
This is joint work with Sergei A. Abramov and Ha Q. Le.