Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6192
Title: Decomposition of Algebraic Functions
Authors: Kozen, Dexter
Landau, Susan
Zippel, Richard
Keywords: computer science
technical report
Issue Date: Feb-1994
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1410
Abstract: Functional 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.
URI: http://hdl.handle.net/1813/6192
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
94-1410.pdf904.96 kBAdobe PDFView/Open
94-1410.ps220.73 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us