Enhancements to Computational Algorithms in Maple 15 - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : System : Information : Updates : Maple 15 : updates/Maple15/computation

Enhancements to Computational Algorithms in Maple 15

 

Introduction

Optimization

Polynomial Arithmetic

Sparse Matrices

High-Precision Algebraic Riccati Equations

Parametric Solving

Statistics

Units

Introduction

Maple 15 includes new and enhanced computational algorithms for both symbolic and numeric computing.

  

Optimization package

  

Polynomial arithmetic

  

Sparse Matrices

  

High-precision algebraic Riccati equations

  

Parametric solving

  

Statistics package

  

Units package

Optimization

• 

A new sparse iterative interior point method has been added to Optimization[LPSolve]. The method is based on an algorithm developed by Dr. H. Wolkowicz at the University of Waterloo and colleagues. It provides a significant improvement in efficiency over the previously available active-set method when solving large sparse linear programs.

Polynomial Arithmetic

• 

Multiplication, division and powering of high-degree dense polynomials are at least 4 times faster because of an improved implementation.  This implementation consumes at least 3/4 less memory than the ones in Maple 14.

• 

The following examples shows efficient polynomial multiplication, powering, division and modulus operations:

f,g := seq(randpoly(x,degree=10^4,dense),i=1..2):

p := CodeTools[Usage](expand(f*g)):

memory used=314.77KiB, alloc change=0 bytes, cpu time=4.00ms, real time=4.00ms, gc time=0ns

p := CodeTools[Usage](expand((5*x-3*y)^10000)):

memory used=32.34MiB, alloc change=32.00MiB, cpu time=111.00ms, real time=111.00ms, gc time=9.26ms

n := prevprime(2^512):

f := Expand((1+x+y+z+t)^30) mod n:

CodeTools[Usage](Divide(f,1+x+y+z+t,'q') mod n);

memory used=0.65MiB, alloc change=0 bytes, cpu time=4.00ms, real time=5.00ms, gc time=0ns

true

(1)
• 

divide determines if the polynomial is not divisible immediately as shown in the second call to the command:

f,g := seq(randpoly([x,y,z],degree=30,terms=3000),i=1..2):

p := expand(f*g):

CodeTools[Usage](divide(p,f,'q'));    # computes quotient

memory used=49.09KiB, alloc change=0 bytes, cpu time=259.00ms, real time=66.00ms, gc time=0ns

true

(2)

CodeTools[Usage](divide(p+1,f,'q'));  # fails instantly

memory used=0.61MiB, alloc change=0.61MiB, cpu time=1000.00us, real time=2.00ms, gc time=0ns

false

(3)
• 

Unassign the names f, g, n, and p.

f:='f': g:='g': n:='n': p:='p':

Sparse Matrices

• 

Support for various operations involving sparse matrices has been greatly improved.  Native support for hardware float multiplication, transpose, block copy, concatenation, and submatrix selection take almost no time to execute now.

M := LinearAlgebra[RandomMatrix](1000,storage=rectangular,density=.003,datatype=float):

time(Matrix(M,storage=sparse));

  

# now .012s vs .200s in Maple 14

M1 := LinearAlgebra[RandomMatrix](1000,storage=sparse,density=.003,datatype=float):

M2 := LinearAlgebra[RandomMatrix](1000,storage=sparse,density=.003,datatype=float):

time(M1.M2);

  

# now .004s vs .032s in Maple 14

time(Matrix(M1,transpose=true));

  

# .000  vs 5.104

time(Matrix(M1,storage=rectangular));

  

#  .008 vs 0.052

time(<M1|M2>);

  

#  .000 vs 10.096

time(<M1,M2>);

  

#  .000 vs 10.148

MD := LinearAlgebra[RandomMatrix](1000,shape=diagonal,datatype=float):

time(MD.M1);

  

#  .000 vs .204

time(M1[..,1..500]);

  

#  .000 vs 2.528

V1 := Vector([seq(2*i,i=1..500)]);

(4)

time(M1(..,V1));

  

#  .060 vs 2.624

High-Precision Algebraic Riccati Equations

• 

High precision Algebraic Riccati Equation solving in the LinearAlgebra package

• 

The commands CARE and DARE for solving the linear systems which represent continuous and discrete Algebraic Riccati Equations have been enhanced to work at higher than hardware double precision.

with(LinearAlgebra):

A := Matrix([[1.0, .2, 1.0], [0., .1, .45], [2.0, 2.3, 1.3]]);

A1.00.21.00.0.10.452.02.31.3

(5)

B := Matrix([[0, 1], [0, 0], [1, 0]]);

B010010

(6)

Q := Matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]]);

Q100010001

(7)

R := Matrix([[1.0, 0.], [0., 1.0]]);

R1.00.0.1.0

(8)

X := CARE(A, B, Q, R);

X3.413509124310391.858101705201212.418298585785921.858101705201219.763240942748594.652306723996382.418298585785924.652306723996383.72188050348369

(9)

Digits:=20:

X := CARE(A, B, Q, R);

X3.41350912431038920621.85810170520120917922.41829858578591711961.85810170520120917929.76324094274858363284.65230672399637525162.41829858578591711964.65230672399637525163.7218805034836886482

(10)

Parametric Solving

Solving Polynomial Equations with Case Discussion

• 

New user-level functionality for building case discussions of the solutions of polynomial equations are now available as the new SolveTools[Parametric] command, and the new parametric option for the solve command.

SolveTools[Parametric]({a*x}, {x}, {a});

x=xa=0x=0a0

(11)
• 

By default these new commands return piecewise answers containing answers for the most general cases and the other branches containing inert function calls.

result := SolveTools[Parametric]({a*x^2-(b+a)*x+b}, {x});

result?Parametricxb+b&comma;x&comma;ba=0x=1&comma;x=baa0

(12)

result := eval(result, a=0);

result?Parametricxb+b&comma;x&comma;b

(13)

value(result);

x=xb=0x=1b0

(14)
• 

The new solve option does some additional processing of the input, but uses the same backend as SolveTools[Parametric] and produces the same answers.  See the solve/parametric help page for more details.

solve( a*x^2-(b+a)*x+b, x, 'parametric');

?Parametricxb+b&comma;x&comma;ba=0x=1&comma;x=baa0

(15)

Definite Summation

• 

The sum command has been enhanced for the case of definite sums with parametric bounds. The behavior can be can be controlled via the optional keyword parametric.

sum(1/k, k=a..b);

Warning, unable to determine if the summand is singular in the interval of summation; try to use assumptions or use the parametric option

k=ab1k

(16)

sum(1/k, k=a..b, parametric);

0a=b+1Ψb+1Ψa1aand0bΨbΨ1aa0andb−1FAILotherwise

(17)
• 

In addition to the sum command itself, the definite summation command SumTools[DefiniteSum][Definite] has been extended by a new option parametric.

with(SumTools):

DefiniteSum[Definite](binomial(2*k-3, k)/4^k, k=0..n, parametric);

2n1n2n+44n+1n034n=12n1n2n+44n+1+382n

(18)
• 

For the case of non-parametric definite sums, handling of removable singularities has been improved. By default, they will be removed, but this can be disabled by setting _EnvFormal to false.

sum(1/GAMMA(k), k=-1..5);

6524

(19)

_EnvFormal := false;

_EnvFormalfalse

(20)

sum(1/GAMMA(k), k=-1..5);

Error, (in SumTools:-DefiniteSum:-ClosedForm) summand is singular in the interval of summation

Additional Improvements to SumTools

• 

Two new commands have been added to the SumTools package and its subpackages: BottomSequence and SummableSpace.

• 

The indefinite summation commands SumTools[IndefiniteSum][Indefinite], SumTools[IndefiniteSum][Hypergeometric], and SumTools[IndefiniteSum][Rational] were extended by a new option failpoints.

• 

A new optional argument was added to the command SumTools[Hypergeometric][Gosper] to return the rational certificate in Gosper's algorithm.

with(SumTools[Hypergeometric]):

Gosper((-1)^k*binomial(n,k), k, 'r');
r;

k−1knkn

kn

(21)
• 

The command SumTools[Hypergeometric][DefiniteSumAsymptotic] was enhanced to handle bivariate rational functions.

DefiniteSum(1/(m^2+k^2)^2, m, k, 0..m);

k=0m1k2+m22

(22)

DefiniteSumAsymptotic(1/(m^2+k^2)^2, m, k, 0..m);

π+28m3+58m4124m5+O1m7

(23)
• 

The possible minimizations via the keyword option minimize in the command SumTools[Hypergeometric][SumDecomposition] were extended.

RegularChains

• 

In Maple 15, the RegularChains library offers a variety of tools to compute the real solutions of polynomial systems. The three new commands RealTriangularize, LazyRealTriangularize, and SamplePoints deal with arbitrary semi-algebraic systems. That is, given any system S of polynomial equations, polynomial inequations and polynomial inequalities (strict or large) these commands produce information about the real solutions of this system.

• 

RegularChains[RealTriangularize] returns a full description of the real solutions of S: it computes a family of simpler systems such that a point is a solution of S if and only if it is a solution of one of the simpler systems.  Each simpler system has a triangular shape and remarkable properties: for this reason it is called a regular semi-algebraic system and the set of the simpler systems is called a full triangular decomposition of S.

• 

RegularChains[LazyRealTriangularize] allows the user to compute a triangular decomposition of S in an interactive manner. This feature is particularly well adapted for systems that are hard to solve.  For such systems, LazyRealTriangularize returns the components of S of maximum dimension together with unevaluated recursive calls, such that, when fully evaluated, these calls produce the other components of S (which are generally harder to compute).

• 

RegularChains[SamplePoints] is even a lazier (and thus much cheaper) way of solving: it produces at least one sample point per connected component of the solution set of S. This way of solving is often sufficient in practical problems.

• 

RegularChains[Display] is a new pretty-printing command that handles any object types in used in the RegularChains library.

• 

RegularChains[ChainTools][Extend] is a new command that decomposes a triangular set into regular chains.

• 

RegularChains[ParametricSystemTools][RealRootClassification] has two new output options, namely formula and samples.  These options allow you to obtain either a formal description or simply sample points of the computed set.

with(RegularChains):

R := PolynomialRing([z,y,x]):

• 

The Zeck algebraic surface is defined by the following equation to which we added inequality constraints in order to select part of this surface

F := [x^2+y^2-z^3*(1-z) = 0, 5*y> 1, z<=2];

Fx2+y2z31z=0&comma;1<5y&comma;z2

(24)
• 

Below is a complete description of the real solutions in terms of formulas  

RealTriangularize(F, R,output=record);

z4z3+y2+x2=02z>0256x2+256y2<275y1>0,4z3=0256y2+256x227=05y1>06400x2<419

(25)
• 

Now we provide witness solutions

SamplePoints(F, R,output=record);

z=5371024&comma;269512y=2816999491073741824x=0,z=74398192&comma;119027131072y=2816999491073741824x=0,z=34y=6652048&comma;13334096x=0

(26)
• 

A snow flake can be described by the following equation

F2 := [x^3+y^2*z^3-y*z^4 ];

F2y2z3yz4+x3

(27)
• 

Below is a complete description of the real solutions.

RealTriangularize(F2, R, output=record);

yz4y2z3x3=027y5+256x3>0y>0x0,yz4y2z3x3=027y5+256x3<0y<0x0,zy=0y0x=0,z=0y0x=0,64z316yz212y2z9y3=027y5+256x3=0x0,y=0x=0

(28)

RootFinding[Parametric]

• 

The RegularChains library can be used in RootFinding[Parametric][CellDecomposition] through this command's new option, method.

with(RootFinding[Parametric]):

m := CellDecomposition([x^2+a*x+b = 0], [x], 'method' = 'RC'):

CellPlot(m, 'samplepoints');

NumberOfSolutions(m);

1&comma;2&comma;2&comma;2&comma;3&comma;0&comma;4&comma;2

(29)

unassign('m'):

Statistics

• 

New commands AutoCorrelation and CrossCorrelation have been added to the Statistics package.  The commands efficiently compute approximations of the autocorrelations of a discrete time series or the cross-correlations of a pair of discrete time series.

Statistics[CrossCorrelation](<1,2,1,2>, <2,1,2,1>, 2);

0.4999999999665181.125000000005631.0.7499999999829220.500000000010712

(30)

Statistics[AutoCorrelation](<1,-1,1,-1>, 2);

1.−0.7499999999422560.499999999875000

(31)
• 

The Statistics[Sample] command can now use a preexisting rtable to store its results in, instead of always creating a new one. This can be used for more efficient memory usage.

Units

• 

The UseUnit command has been added to the Units package. It can be used to select a unit that is to be used for computation in this package. The command is a simpler alternative to the AddSystem and UseSystem commands.

See Also

Index of New Maple 15 Features

Updates to Differential Equation (DE) Solvers in Maple 15

Updates to the Differential Equation Package in Maple 15