of polynomials g and h, where g and h have degree greater than 1; it is an algebraic functional decomposition.
The degree of a composite polynomial is always a composite number, the product of the degrees of the composed polynomials.
The rest of this article discusses only univariate polynomials; algorithms also exist for multivariate polynomials of arbitrary degree.
[2] In the simplest case, one of the polynomials is a monomial.
For example, decomposes into since using the ring operator symbol ∘ to denote function composition.
The restriction in the definition to polynomials of degree greater than one excludes the infinitely many decompositions possible with linear polynomials.
, and the degrees of the components are the same up to linear transformations, but possibly in different order; this is Ritt's polynomial decomposition theorem.
For example, can be calculated with 3 multiplications and 3 additions using the decomposition, while Horner's method would require 7 multiplications and 8 additions.
This technique is used in many computer algebra systems.
[4] For example, using the decomposition the roots of this irreducible polynomial can be calculated as[5] Even in the case of quartic polynomials, where there is an explicit formula for the roots, solving using the decomposition often gives a simpler form.
For example, the decomposition gives the roots[5] but straightforward application of the quartic formula gives equivalent results but in a form that is difficult to simplify and difficult to understand; one of the four roots is: The first algorithm for polynomial decomposition was published in 1985,[6] though it had been discovered in 1976,[7] and implemented in the Macsyma/Maxima computer algebra system.
[8] That algorithm takes exponential time in worst case, but works independently of the characteristic of the underlying field.
A 1989 algorithm runs in polynomial time but with restrictions on the characteristic.
[9] A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.