The Functional Decomposition of Polynomials

Other Titles
Abstract
Let $f(\vec{x}), h_{1}(\vec{x}),...,h_{d}(\vec{x})$ and $g(\vec{x})$ be elements of the polynomial ring $K [\vec{x}]$ (or "polynomials over $K$"). If $f(\vec{x}) = g(h_{1}(\vec({x}),..., h_{d}(\vec{x})),$ then we call $g, h_{1},..., h{d}$ a functional decomposition of $f$. Polynomial decomposition is an important and interesting problem with a number of applications in computer scinece and computational algebra. Problems related to the decomposition of polynomials have received much attention in the past five years [AT85, BZ85, KL86, Dic87, vzGKL87, vzG87, vzG88, Dic88, KL89] as well as in the less recent past [Rit22, Eng41, Lev41, FM69, DW74]. In fact, the decomposition of polynomials is considered important enough that most major computational algebra systems (SCRATCHPAD II, MAPLE, MATHEMATICA) support polynomial decomposition for univariate polynomials. In this thesis, we examine various problems related to the functional decomposition of polynomials. We will give a brief history of polynomial decomposition, and then give a number of new results, including the first polynomial time algorithms for two important decomposition problems and a proof of the NP-completeness of another interesting polynomial decomposition problem. We will also discuss some ot the applications of polynomial decomposition to problems such as polynomial factorization and computing the inverse of an automorphism over a multivariate polynomial ring. For the latter, we will give the first known polyomial time algorithm.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1989-07
Publisher
Cornell University
Keywords
computer science; technical report
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1023
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
technical report
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record