Enhancements to Computational Algorithms in Maple 15
Maple 15 includes new and enhanced computational algorithms for both symbolic and numeric computing.
Optimization
Polynomial Arithmetic
Sparse Matrices
High-Precision Algebraic Riccati Equations
Parametric Solving
Statistics
Units
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.
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.35MiB, alloc change=32.00MiB, cpu time=89.00ms, real time=91.00ms, gc time=7.54ms
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=6.00ms, real time=5.00ms, gc time=0ns
true
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=785.00ms, real time=131.00ms, gc time=0ns
CodeTools[Usage](divide(p+1,f,'q')); # fails instantly
memory used=0.61MiB, alloc change=0.61MiB, cpu time=3.00ms, real time=3.00ms, gc time=0ns
false
Unassign the names f, g, n, and p.
f:='f': g:='g': n:='n': p:='p':
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)]);
time(M1(..,V1));
# .060 vs 2.624
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]]);
A≔1.00.21.00.0.10.452.02.31.3
B := Matrix([[0, 1], [0, 0], [1, 0]]);
B≔010010
Q := Matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]]);
Q≔100010001
R := Matrix([[1.0, 0.], [0., 1.0]]);
R≔1.00.0.1.0
X := CARE(A, B, Q, R);
X≔3.413509124310401.858101705201212.418298585785921.858101705201219.763240942748584.652306723996382.418298585785924.652306723996383.72188050348369
Digits:=20:
X≔3.41350912431038920621.85810170520120917922.41829858578591711961.85810170520120917929.76324094274858363284.65230672399637525162.41829858578591711964.65230672399637525163.7218805034836886482
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=0a≠0
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≔SolveToolsParametric⁡−x⁢b+b,x,ba=0x=1,x=baa≠0
result := eval(result, a=0);
result≔SolveToolsParametric⁡−x⁢b+b,x,b
value(result);
x=xb=0x=1b≠0
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');
SolveToolsParametric⁡−x⁢b+b,x,ba=0x=1,x=baa≠0
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);
∑k=ab⁡1k
sum(1/k, k=a..b, parametric);
0a=b+1Ψ⁡b+1−Ψ⁡a1≤aand0≤bΨ⁡−b−Ψ⁡1−aa≤0andb≤−1FAILotherwise
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);
2⁢n−1n⁢2⁢n+44n+1n≤034n=12⁢n−1n⁢2⁢n+44n+1+382≤n
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
_EnvFormal := false;
_EnvFormal≔false
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⁢−1k⁢nkn
−kn
The command SumTools[Hypergeometric][DefiniteSumAsymptotic] was enhanced to handle bivariate rational functions.
DefiniteSum(1/(m^2+k^2)^2, m, k, 0..m);
∑k=0m⁡1k2+m22
DefiniteSumAsymptotic(1/(m^2+k^2)^2, m, k, 0..m);
π+28⁢m3+58⁢m4−124⁢m5+O⁡1m7
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];
F≔x2+y2−z3⁢1−z=0,1<5⁢y,z≤2
Below is a complete description of the real solutions in terms of formulas
RealTriangularize(F, R,output=record);
z4−z3+y2+x2=02−z>0256⁢x2+256⁢y2<275⁢y−1>0,4⁢z−3=0256⁢y2+256⁢x2−27=05⁢y−1>06400⁢x2<419
Now we provide witness solutions
SamplePoints(F, R,output=record);
z=67128,1732y=2691024x=0,z=2932,117128y=2691024x=0,z=34y=83256,2164x=0
A snow flake can be described by the following equation
F2 := [x^3+y^2*z^3-y*z^4 ];
F2≔y2⁢z3−y⁢z4+x3
Below is a complete description of the real solutions.
RealTriangularize(F2, R, output=record);
y⁢z4−y2⁢z3−x3=027⁢y5+256⁢x3>0y>0x≠0,y⁢z4−y2⁢z3−x3=027⁢y5+256⁢x3<0y<0x≠0,z−y=0y≠0x=0,z=0y≠0x=0,64⁢z3−16⁢y⁢z2−12⁢y2⁢z−9⁢y3=027⁢y5+256⁢x3=0x≠0,y=0x=0
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,2,2,2,3,0,4,2
unassign('m'):
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
Statistics[AutoCorrelation](<1,-1,1,-1>, 2);
1.−0.7499999999422560.499999999875000
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.
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
Download Help Document