Home Online Manual
Top
Back: curveColengthDerivations
Forward: decompopts
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.4.6 decomp_lib

Library:
decomp.lib
Purpose:
Functional Decomposition of Polynomials
Author:
Christian Gorzel, University of Muenster
email: [email protected]

Overview:
This library implements functional uni-multivariate decomposition of multivariate polynomials.

A (multivariate) polynomial f is a composite if it can be written as $g \circ h$ where g is univariate and h is multivariate, where $\deg(g), \deg(h)>1$.

Uniqueness for monic polynomials is up to linear coordinate change $g\circ h = g(x/c -d) \circ c(h(x)+d)$.

If f is a composite, then decompose(f); returns an ideal (g,h); such that $\deg(g) < \deg(f)$ is maximal, ( $\deg(h)\geq 2$). The polynomial h is, by the maximality of $\deg(g)$, not a composite.

The polynomial g is univariate in the (first) variable vvar of f, such that deg_vvar(f) is maximal.

decompose(f,1); computes a full decomposition, i.e. if f is a composite, then an ideal $(g_1,\dots ,g_m,h)$ is returned, where $g_i$ are univariate and each entry is primitive such that $f=g_1\circ \dots \circ g_m\circ h$.

If f is not a composite, for instance if $\deg(f)$ is prime, then decompose(f); returns f.

The command decompose is the inverse: compose(decompose(f,1))==f.

Recall, that Chebyshev polynomials of the first kind commute by composition.

The decomposition algorithms work in the tame case, that is if char(basering)=0 or p:=char(basering) > 0 but deg(g) is not divisible by p. Additionally, it works for monic polynomials over $Z$ and in some cases for monic polyomials over coefficient rings.
See is_composite for examples. (It also works over the reals but there it seems not be numerical stable.)

More information on the univariate resp. multivariate case.

Univariate decomposition is created, with the additional assumption $\deg(g), \deg(h)>1$.

A multivariate polynomial f is a composite, if f can be written as $g \circ h$, where $g$ is a univariate polynomial and $h$

is multivariate. Note, that unlike in the univariate case, the polynomial $h$ may be of degree $1$.
E.g. $f = (x+y)^2+ 2(x+y) +1$ is the composite of $g = x^2+2x+1$ and $h = x+y$.

If nvars(basering)>1, then, by default, a single-variable multivariate polynomial is not considered to be the same as in the one-variable polynomial ring; it will always be decomposed. That is:
> ring r1=0,x,dp;
> decompose(x3+2x+1);
x3+2x+1
but:
> ring r2=0,(x,y),dp;
> decompose(x3+2x+1);
_[1]=x3+2x+1
_[2]=x

In particular:
is_composite(x3+2x+1)==1; in ring r1 but
is_composite(x3+2x+1)==0; in ring r2.

This is justified by interpreting the polynomial decomposition as an affine Stein factorization of the mapping $f:k^n \to k, n\geq 2$.

The behaviour can changed by the some global variables.

int DECMETH; choose von zur Gathen's or Kozen-Landau's method.
int MINS; compute f = g o h, such that h(0) = 0.
int IMPROVE; simplify the coefficients of g and h if f is not monic.
int DEGONE; single-variable multivariate are considered uni-variate.

See decompopts; for more information.

Additional information is displayed if printlevel > 0.

References:
D. Kozen, S. Landau: Polynomial Decomposition Algorithms,

            J. Symb. Comp. (1989), 7, 445-456.

J. von zu Gathen: Functional Decomposition of Polynomials: the Tame Case,

            J. Symb. Comp. (1990), 9, 281-299.

J. von zur Gathen, J. Gerhard: Modern computer algebra,

            Cambridge University Press, Cambridge, 2003.

Procedures:

D.4.6.1 decompopts  displays resp. resets global options
D.4.6.2 decompose  [complete] functional decomposition of poly f
D.4.6.3 is_composite  predicate, is f a composite polynomial?
D.4.6.4 chebyshev  the nth Chebyshev polynomial of the first kind
D.4.6.5 compose  compose f1 (f2 (...(fn))), f_i polys of ideal
Auxiliary procedures:
D.4.6.6 makedistinguished  transforms f to a var-distinguished polynomial // divisors(n[,1]); intvec [increasing] of the divisors d of n // gcdv(v); the gcd of the entries in intvec v // maxdegs(f); maximal degree for each variable of the poly f // randomintvec(n,a,b[,1]); random intvec size n, [non-zero] entries in {a,b}