✦ LIBER ✦

Decomposition of Algebraic Functions

✍ Scribed by Dexter Kozen; Susan Landau; Richard Zippel

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 554 KB
Volume: 22
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1996.0051

No coin nor oath required. For personal study only.

✦ Synopsis

Functional decomposition-whether a function f (x) can be written as a composition of functions g(h(x)) in a non-trivial 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 (1989). Dickerson (1987) and von zur Gathen (1990a) gave algorithms for certain multivariate cases. Zippel (1991) 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 characterize all decompositions of a given algebraic function up to isomorphism, and give an exponential time algorithm for finding a non-trivial one if it exists. The algorithm involves genus calculations and constructing transcendental generators of fields of genus zero.

📜 SIMILAR VOLUMES

Multiplicative Decompositions of Holomor

Multiplicative Decompositions of Holomorphic Fredholm Functions and ψ*-Algebras

✍ Bernhard Gramsch; Winfried Kaballo 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 873 KB

In this article we construct multiplicative decompoeitions of holomorphic Fkedholm operator d u d functions on Stsin manifolds with d u e s in d o u a algebras of differential and pseudo differential operahm which are submultiplicrtive 0' -algebras, a concept introduced by the first author. For Redh

Computational Complexity of Algebraic Fu

Computational Complexity of Algebraic Functions

✍ Nicholas Pippenger 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 919 KB

Algebraic values of meromorphic function

Algebraic values of meromorphic functions

✍ Serge Lang 📂 Article 📅 1965 🏛 Elsevier Science 🌐 English ⚖ 538 KB

E-Algebraic Functions over Fields of Pos

E-Algebraic Functions over Fields of Positive Characteristic—An Analogue of Differentially Algebraic Functions

✍ Habib Sharif 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 158 KB

A function or a power series f is called differentially algebraic if it satisfies a Ž X Ž n. . differential equation of the form P x, y, y , . . . , y s 0, where P is a nontrivial polynomial. This notion is usually defined only over fields of characteristic zero and is not so significant over fields

Algebraic Families of Analytic Functions

Algebraic Families of Analytic Functions, I

✍ M. Briskin; Y. Yomdin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 311 KB

The aim of this paper is to consider analytic functions, arising in connection with algebraic differential equations, from the following point of view: Taylor coefficients of such functions usually turn out to be polynomials (or rational functions) in the parameters of the problem. Following pioneer

Rings of algebraic numbers and functions

✍ Edward D. Davis 📂 Article 📅 1965 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB

## Introduction. That every integrally closed subring of the field of algebraic numbers is a ring of quotients of its subring of algebraic integers is a remark of 131. The purpose of the present note is to prove this assertion without the hypothesis of integral closure (Theorem A). The proof rests