Efficiency Improvements in Maple 16
Maple 16 includes a number of efficiency improvements for polynomial computations.
Polynomial ideal decomposition
Numerical PDE solutions with compile
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.
Multiplication, dense, 3 variables, degree 30
Mathematica 8: 110s
Speedup M16/M14: 1.3
Speedup M16/Mathematica8: 210
Division, dense, 3 variables,
(degree 60 / degree 30)
Mathematica 8: 84s
Speedup M16/M14: 1.6
Speedup M16/Mathematica8: 160
Univariate multiplication, sparse, degree 100000, 1000 terms
Mathematica 8: 3.0s
Speedup M16/Mathematica8: 14
Univariate division, sparse,
(degree 200000) / (degree 100000),
(180000 terms) / (1000 terms)
Mathematica 8: 78s
Speedup M16/M14: 1.4
Speedup M16/Mathematica8: 390
Non-divisibility test, dense, 3 variables, degree 60/degree 30
Mathematica 8: 84s
Speedup M16/M14: 22
Speedup M16/Mathematica8: 1800
Modular division, dense, 4 variables,
512 bit prime,degree 30/linear
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
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
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:
Note that the resulting factors have integer coefficients as well. For example, x2+1 is not split any further into x−ⅈx+ⅈ. To obtain a more refined factorization, you can use a second argument to specify what you want to allow in the coefficients:
In the most general case, the polynomial can have more than one variable and may already contain non-rational expressions such as ⅈ or 2 or t−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:
factorx2−2 r x+t
evalaFactorx2−2 r x+t
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.
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.
RootOf_Z2−2, RootOf_Z2−3, RootOf_Z2−t
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:
wang92c ≔ −3 c d+b2−2 a+2, −3 c2d+b2c−a d+b, −3 a2d−4 b c+2 b2−6 a c+3 a b
memory used=36.06MiB, alloc change=23.01MiB, cpu time=1.20s, real time=4.08s
> 5 min
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.
Download Help Document