Efficiency - Maple Help

Efficiency Improvements in Maple 16

Maple 16 includes a number of efficiency improvements for polynomial computations.

Polynomial arithmetic

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

 • Multiplication and powering (expand, Expand mod n, Power mod n, Powmod)
 • Exact division (divide, Divide mod n)
 • Univariate and multivariate polynomials with integer coefficients
 • Dense and sparse polynomials

This has been achieved through a combination of various techniques:

 • New fast heap-based and memory efficient algorithms implemented in C
 • New compact internal polynomial data structure
 • Multithreading and exploiting cache locality

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.

Computation times

Multiplication, dense, 3 variables, degree 30

M14: 0.65s

M15: 0.73s

M16: 0.52s

Mathematica 8: 110s

Speedup M16/M14: 1.3

Speedup M16/Mathematica8: 210



Division, dense, 3 variables,
(degree 60 / degree 30)

M14: 0.88s

M15: 0.75s
M16: 0.54s
Mathematica 8: 84s

Speedup M16/M14: 1.6

Speedup M16/Mathematica8: 160

Univariate multiplication, sparse, degree 100000, 1000 terms

M14: 0.27s
M15: 0.28s
M16: 0.21s
Mathematica 8: 3.0s

Speedup M16/M14: 1.3

Speedup M16/Mathematica8: 14

Univariate division, sparse,
(degree 200000) / (degree 100000),
(180000 terms) / (1000 terms)

M14: 0.27s
M15: 0.25s
M16: 0.20s
Mathematica 8: 78s

Speedup M16/M14: 1.4

Speedup M16/Mathematica8: 390

Non-divisibility test, dense, 3 variables,

M14: 0.99s
M15: 0.090s
M16: 0.046s
Mathematica 8: 84s

Speedup M16/M14: 22

Speedup M16/Mathematica8: 1800

Modular division, dense, 4 variables,
512 bit prime,

M14: 2.0s

M15: 0.16s

M16: 0.11s

Mathematica 8: 2.5s

Speedup M16/M14: 18

Speedup M16/Mathematica8: 23



Univariate powering modulo a polynomial and a 31 bit prime, dense, degree 1024

M14: 0.7s

M15: 0.26s

M16: 0.11s

Mathematica 8: freezes computer

Speedup M16/M14: 6.4



Computation times on multiple cores

Multiplication, dense, 4 variables, degree 20

M16, 1 core: 13s

M16, 2 cores: 7.5s

M16, 4 cores: 4.8s

Speedup 4 cores: 2.7

Division, dense, 4 variables, (degree 20) / (degree 10)

M16, 1 core: 14s

M16, 2 cores: 7.7s

M16, 4 cores: 4.4s

Speedup 4 cores: 3.2

Polynomial factorization

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)$

 $\left({x}{-}{1}\right){}\left({x}{+}{1}\right){}\left({{x}}^{{2}}{+}{1}\right){}\left({{x}}^{{4}}{+}{1}\right)$ (2.1)

Note that the resulting factors have integer coefficients as well. For example, ${x}^{2}+1$ is not split any further into $\left(x-i\right)\left(x+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,i\right)$

 $\left({{x}}^{{2}}{+}{I}\right){}\left({-}{{x}}^{{2}}{+}{I}\right){}\left({-}{x}{+}{I}\right){}\left({x}{+}{I}\right){}\left({x}{-}{1}\right){}\left({x}{+}{1}\right)$ (2.2)

In the most general case, the polynomial can have more than one variable and may already contain non-rational expressions such as $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{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{t}\right)$ (2.3)

 ${{x}}^{{2}}{-}{2}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{t}\right){}{x}{+}{t}$ (2.4)

 ${\left({x}{-}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{t}\right)\right)}^{{2}}$ (2.5)

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)$

 ${\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (2.6)

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

 ${\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)$ (2.7)
 ${}$ (2.8)

$f≔\mathrm{evala}\left(\mathrm{Reduce}\left(\mathrm{randpoly}\left(\left[x,y,{z}_{1},{z}_{2},t\right]\right)\right)\right)$

 ${34}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){-}{20}{}{x}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){+}{93}{}{{x}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{t}{+}{45}{}{{x}}^{{3}}{}{{t}}^{{2}}{+}{30}{}{{y}}^{{3}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{-}{56}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{t}$ (2.9)

$g≔\mathrm{evala}\left(\mathrm{Reduce}\left(\mathrm{randpoly}\left(\left[x,y,{z}_{1},{z}_{2},t\right]\right)\right)\right)$

 ${47}{}{{t}}^{{2}}{+}{40}{}{{x}}^{{2}}{}{t}{+}{114}{}{y}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){+}{58}{}{{x}}^{{3}}{}{y}{}{t}{+}{43}{}{x}{}{y}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{t}{-}{98}{}{t}$ (2.10)

 ${21204}{}{{x}}^{{3}}{}{y}{}{t}{+}{1360}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{x}}^{{2}}{}{t}{+}{1972}{}{{y}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{x}}^{{3}}{}{t}{-}{940}{}{x}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{-}{800}{}{{x}}^{{3}}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{t}{-}{1160}{}{{x}}^{{4}}{}{{y}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{t}{+}{1960}{}{x}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{t}{+}{5394}{}{{x}}^{{6}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{}{y}{+}{5130}{}{{x}}^{{3}}{}{{t}}^{{2}}{}{y}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){+}{1935}{}{{x}}^{{4}}{}{{t}}^{{3}}{}{y}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{+}{1200}{}{{y}}^{{3}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{{x}}^{{2}}{}{t}{+}{1740}{}{{y}}^{{4}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{{x}}^{{3}}{}{t}{-}{2240}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{}{{x}}^{{2}}{+}{1290}{}{{t}}^{{2}}{}{{y}}^{{4}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{x}{-}{2408}{}{{t}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{x}{}{y}{+}{1462}{}{{y}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{x}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{t}{-}{860}{}{{x}}^{{2}}{}{{y}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{t}{+}{3999}{}{{x}}^{{4}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{}{y}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{-}{3248}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{}{{x}}^{{3}}{}{y}{+}{2115}{}{{x}}^{{3}}{}{{t}}^{{4}}{+}{1800}{}{{x}}^{{5}}{}{{t}}^{{3}}{-}{4410}{}{{x}}^{{3}}{}{{t}}^{{3}}{-}{4560}{}{x}{}{{y}}^{{3}}{+}{2610}{}{{x}}^{{6}}{}{{t}}^{{3}}{}{y}{+}{1598}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{-}{3332}{}{{y}}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{t}{+}{4371}{}{{x}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{3}}{+}{3720}{}{{x}}^{{5}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{-}{9114}{}{{x}}^{{3}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{+}{1410}{}{{y}}^{{3}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{{t}}^{{2}}{+}{3420}{}{{y}}^{{4}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){-}{2940}{}{{y}}^{{3}}{}{{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}{}{t}{-}{2632}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{3}}{+}{5488}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{{t}}^{{2}}{-}{12768}{}{\mathrm{RootOf}}\left({{\mathrm{_Z}}}^{{3}}{-}{t}{,}{\mathrm{index}}{=}{1}\right){}{t}{}{y}{+}{7752}{}{{y}}^{{3}}$ (2.11)

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

 memory used=15.91MiB, alloc change=19.21MiB, cpu time=516.00ms, real time=4.50s

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

 Variables RootOfs Parameters Total #indets Degree Terms Maple 15 Maple 16 Speedup $x,y,z$ − 5 10 36 $24$ $x,y$ $t$ 5 10 36 $18$ $x,y$ $t$ 5 10 134 $50$ $x,y$ $t$ 5 10 276 $43$ $x,y$ $t$ 5 20 36 $57$ $x,y$ $t$ 5 30 36 $550$ $x,y$ $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)$, $\mathrm{RoofOf}\left({\mathrm{_Z}}^{3}-t\cdot \mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)\right)$ $t$ 5 10 36 $11$ $x,y$ $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)$, $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-3\right)$, $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-t\right)$ $t$ 6 10 36 $27$ $x,y$ $s,t$ 6 10 36 $48$

Polynomial ideal decomposition

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):$

 $⟨{-}{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}⟩$ (3.1)

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

 memory used=36.06MiB, alloc change=23.01MiB, cpu time=1.20s, real time=4.08s

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

 Task Problem #Variables Dimension Max degree Maple 15 Maple 16 Speedup prime decomposition circles $5$ $1$ $2$ $8.3$ prime decomposition vermeer $5$ $1$ $5$ $11$ prime decomposition wang92c $4$ $1$ $3$ $54$ prime decomposition ctoa $10$ $4$ $2$ $>550$ prime decomposition butcher $7$ $3$ $4$ $>710$ radical butcher $7$ $3$ $4$ $>530$

Numerical PDE solutions with compile

 • The compile option has been added to the numeric pdsolve command, to allow more efficient computation of PDE numerical solutions. See pdsolve[numeric] for more information.