Overdetermined Rational Function Decomposition with Parameters.

Austin Roche, CECM, SFU

Given a rational function H in K(x) the problem of rational function 
decomposition is to determine two rational functions J and F such
that J o F = H.  Zippel in ISSAC 1991 presented a solution to this
problem which requires factorization.  We consider a related problem
with two simplifying and two complicating modifications:

(i) We have a sequence of compositions, J_i o F, where the left
   composition factors J_i vary but the right factor F does not.
   The J_i's are related in that they are obtained from each other by a
   sort of differentiation; in particular they may share common factors.

(ii) The form of the J_i are known a priori.

(iii) The J_i may depend on unknown parameters, whose rational
   values need to be determined as well as F.

(iv) F may depend on parameters.

A new algorithm will be presented whose complexity is decreased on account
of the simplifications (i,ii), and not significantly affected by the
complications (iii,iv). The essential idea is to look for common factors
constituting the functions J_i(F(x)) and use these, along with others
obtained by differentiation, to generate a progressively simpler sequence
{J_i o F}.

This problem has a direct application in the solving of Abel ordinary
differential equations.  Our examples will be taken from this context.