Show simple item record

dc.contributor.authorKozen, Dexteren_US
dc.contributor.authorLandau, Susanen_US
dc.contributor.authorZippel, Richarden_US
dc.description.abstractFunctional decomposition--whether a function $f(x)$ can be written as a composition of functions $g(h(x))$ in a nontrivial way--is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau [8]. Dickerson [5] and von zur Gathen [11] gave algorithms for certain multivariate cases. Zippel [13] showed how to decompose rational functions. In this paper, we address the issue of decomposition of algebraic functions. We show that the problem is related to univariate resultants in algebraic function fields, and in fact can be reformulated as a problem of resultant decomposition. We give an algorithm for finding a nontrivial decomposition of a given algebraic function if it exists. The algorithm involves genus calculations and constructing transcendental generators of fields of genus zero.en_US
dc.format.extent926682 bytes
dc.format.extent226027 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleDecomposition of Algebraic Functionsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record