
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. 