Efficiency Improvements in Maple 16 - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 16 : updates/Maple16/Efficiency

Efficiency Improvements in Maple 16

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

• 

Polynomial arithmetic

• 

Polynomial factorization

• 

Polynomial ideal decomposition

• 

Numerical PDE solutions with compile

 

Polynomial arithmetic

Polynomial factorization

Polynomial ideal decomposition

Numerical PDE solutions with compile

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, degree 60/degree 30

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,degree 30/linear

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:

factorx81

x1x+1x2+1x4+1

(2.1)

Note that the resulting factors have integer coefficients as well. For example, x2+1 is not split any further into xx+. To obtain a more refined factorization, you can use a second argument to specify what you want to allow in the coefficients:

factorx81,

x2+Ix2+Ix+Ix+Ix1x+1

(2.2)

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 t2, 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:

rRootOf_Z2t

RootOf_Z2t

(2.3)

factorx22 r x+t

x22RootOf_Z2tx+t

(2.4)

evalaFactorx22 r x+t

xRootOf_Z2t2

(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.

restart:randomize1: 

z1convert2,RootOf

RootOf_Z22,index=1

(2.6)

z2convertt1/3,RootOf

RootOf_Z3t,index=1

(2.7)

(2.8)

fevalaReducerandpolyx,y,z1,z2,t

34y2RootOf_Z22,index=120xy2RootOf_Z22,index=1+93x3RootOf_Z22,index=1t+45x3t2+30y3RootOf_Z3t,index=1256RootOf_Z22,index=1RootOf_Z3t,index=1t

(2.9)

gevalaReducerandpolyx,y,z1,z2,t

47t2+40x2t+114yRootOf_Z22,index=1+58x3yt+43xyRootOf_Z3t,index=12t98t

(2.10)

hevalaExpandf g

21204x3yt+1360y2RootOf_Z22,index=1x2t+1972y3RootOf_Z22,index=1x3t940xy2RootOf_Z22,index=1t2800x3y2RootOf_Z22,index=1t1160x4y3RootOf_Z22,index=1t+1960xy2RootOf_Z22,index=1t+5394x6RootOf_Z22,index=1t2y+5130x3t2yRootOf_Z22,index=1+1935x4t3yRootOf_Z3t,index=12+1200y3RootOf_Z3t,index=12x2t+1740y4RootOf_Z3t,index=12x3t2240RootOf_Z22,index=1RootOf_Z3t,index=1t2x2+1290t2y4RootOf_Z3t,index=1x2408t3RootOf_Z22,index=1xy+1462y3RootOf_Z22,index=1xRootOf_Z3t,index=12t860x2y3RootOf_Z22,index=1RootOf_Z3t,index=12t+3999x4RootOf_Z22,index=1t2yRootOf_Z3t,index=123248RootOf_Z22,index=1RootOf_Z3t,index=1t2x3y+2115x3t4+1800x5t34410x3t34560xy3+2610x6t3y+1598y2RootOf_Z22,index=1t23332y2RootOf_Z22,index=1t+4371x3RootOf_Z22,index=1t3+3720x5RootOf_Z22,index=1t29114x3RootOf_Z22,index=1t2+1410y3RootOf_Z3t,index=12t2+3420y4RootOf_Z3t,index=12RootOf_Z22,index=12940y3RootOf_Z3t,index=12t2632RootOf_Z22,index=1RootOf_Z3t,index=1t3+5488RootOf_Z22,index=1RootOf_Z3t,index=1t212768RootOf_Z3t,index=1ty+7752y3

(2.11)

CodeTools:-UsageevalaFactorh:

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

RootOf_Z22, RootOf_Z33

5

10

36

5.0 s

0.21 s

24

x,y

RootOf_Z22, RootOf_Z3t

t

5

10

36

6.1 s

0.34 s

18

x,y

RootOf_Z22, RootOf_Z3t

t

5

10

134

18 s

0.36 s

50

x,y

RootOf_Z22, RootOf_Z3t

t

5

10

276

29 s

0.68 s

43

x,y

RootOf_Z22, RootOf_Z3t

t

5

20

36

24 s

0.42 s

57

x,y

RootOf_Z22, RootOf_Z3t

t

5

30

36

220 s

0.40 s

550

x,y

RootOf_Z22, RoofOf_Z3tRootOf_Z22

t

5

10

36

7.6 s

0.68 s

11

x,y

RootOf_Z22, RootOf_Z23, RootOf_Z2t

t

6

10

36

16 s

0.60 s

27

x,y

RootOf_Z2s, RootOf_Z3t

s,t

6

10

36

16 s

0.33 s

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:

restart:

withPolynomialIdeals:

wang92c  3 c d+b22 a+2,                      3 c2d+b2ca d+b,                      3 a2d4 b c+2 b26 a c+3 a b

3cd+b22a+2,3c2d+b2cad+b,3a2d4bc+2b26ac+3ab

(3.1)

CodeTools:-UsagePrimeDecompositionwang92c:

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

6.8 s

0.82 s

8.3

prime decomposition

vermeer

5

1

5

6.4 s

0.60 s

11

prime decomposition

wang92c

4

1

3

45 s

0.84 s

54

prime decomposition

ctoa

10

4

2

> 5 min

0.54 s

>550

prime decomposition

butcher

7

3

4

> 5 min

0.42 s

>710

radical

butcher

7

3

4

> 5 min

0.57 s

>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.

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam