Over the past couple of releases, the efficiency of polynomial arithmetic in Maple has been improved dramatically:

This has been achieved through a combination of various techniques:

Together, these improvements have lead to sequential speedup factors of up to 22 compared to earlier Maple releases and up to 1800 compared to the latest release of Mathematica®.

Maple's parallel implementations provide even higher speedups and scale well with the number of cores.

Maple has two commands for polynomial factorization, i.e., the multiplicative decomposition of a multivariate polynomial into irreducible factors that cannot be decomposed any further.
The simplest case is that of a univariate polynomial with integer coefficients, using the factor command:

$\mathrm{factor}\left(x^8-1\right)$

Note that the resulting factors have integer coefficients as well. For example, $x^2\+1$ is not split any further into $\left(x-\mathrm{i}\right)\left(x\+\mathrm{i}\right)$. To obtain a more refined factorization, you can use a second argument to specify what you want to allow in the coefficients:

$\mathrm{factor}\left(x^8-1\,\mathrm{i}\right)$

In the most general case, the polynomial can have more than one variable and may already contain non-rational expressions such as $\mathrm{i}$ or $\sqrt{2}$ or $\sqrt{t-\sqrt{2}}$, which can even be nested or involve parameters (such as $t$ in the example) in the coefficients. Such cases are handled by the command evala(Factor(...)). Note, however, that this command generally requires all radicals to be expressed in RootOf form:

$r≔\mathrm{RootOf}\left({\mathrm{\_Z}}^2-t\right)$

$\mathrm{factor}\left(x^2-2 r x\+t\right)$

$\mathrm{evala}\left(\mathrm{Factor}\left(x^2-2 r x\+t\right)\right)$

In Maple 16, the computational efficiency of the evala(Factor(...)) command has been improved dramatically, in particular in the presence of multiple and nested RootOfs. The speedup is due to a new and efficient sparse modular algorithm. For example, the execution time for the following example is about 20 times faster than in Maple 15 on the same machine.

$\mathrm{restart}\:\mathrm{randomize}\left(1\right)\:$ 

$z_1≔\mathrm{convert}\left(\sqrt{2}\,\mathrm{RootOf}\right)$

$z_2≔\mathrm{convert}\left(t^{1\/3}\,\mathrm{RootOf}\right)$

$f≔\mathrm{evala}\left(\mathrm{Reduce}\left(\mathrm{randpoly}\left(\left[x\,y\,z_1\,z_2\,t\right]\right)\right)\right)$

$g≔\mathrm{evala}\left(\mathrm{Reduce}\left(\mathrm{randpoly}\left(\left[x\,y\,z_1\,z_2\,t\right]\right)\right)\right)$

$h≔\mathrm{evala}\left(\mathrm{Expand}\left(f g\right)\right)$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{evala}\left(\mathrm{Factor}\left(h\right)\right)\right)\:$

The following table shows some benchmarks in comparison to Maple 15.

A generalization of the concept of factoring a single polynomial into its multiplicatively irreducible factors is the prime decomposition of a polynomial ideal, generated by a finite set of multivariate polynomials. Maple's PolynomialIdeals package provides, in addition to many useful commands and tools for manipulating and analyzing polynomial ideals, the PrimeDecomposition command, as well as the Radical command, which computes equivalent to the squarefree part for a polynomial ideal. The computational efficiency of these two commands was improved for Maple 15, leading to dramatic speedup factors of more than 700 in some cases.

The main improvements are new algorithms and heuristics to split the systems more frequently and, in some cases, run the factoring Buchberger algorithm. These enhancements apply in particular to positive-dimensional systems, i.e., systems with an infinite number of complex solutions.

For example, the following computation is faster than in Maple 15 by a factor of about 50 on the same machine:

$\mathrm{restart}\:$

$\mathrm{with}\left(\mathrm{PolynomialIdeals}\right)\:$

$$\begin{gathered} \mathrm{wang92c} ≔ ⟨-3 c d\+b^2-2 a\+2\, \\ -3 c^{2}d\+b^{2}c-a d\+b\, \\ -3 a^{2}d-4 b c\+2 b^2-6 a c\+3 a b⟩ \end{gathered}$$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{PrimeDecomposition}\left(\mathrm{wang92c}\right)\right)\:$

The following table shows some benchmarks in comparison to Maple 15.