In Maple 8, the Spline function in the CurveFitting package uses a more efficient algorithm for the degree 2 and the default degree 3 cases when floating-point data is provided.  For best results, specify the input data points in the form of Vectors.

The built-in procedures add and mul have been rewritten using a new algorithm for the case of adding or multiplying over a range. In some cases, the performance of these routines is an order of magnitude faster.

time(mul(i,i=1..10000)); # about 12s in Maple 7

$0.001$

There is a new algorithm in the partial fraction conversion routine convert(...,parfrac,...). It is significantly more efficient for problems with multiplicities in the denominator. In addition, the new routine often provides more compact output.

The new algorithm decomposes the partial fraction decomposition into separate problems at each multiplicity, which can significantly reduce the run-time and memory consumption for problems having multiplicities (due to the O(n^3) cost of linear system solution).

The following example has a squared degree 44 polynomial in the denominator.

ratpol:=1/(hypergeom([-44, 51],[3],1-x)^2*(-1+x)^3*x^5);

$\mathrm{ratpol}≔\frac{1}{{\mathrm{hypergeom}\left(\left[\mathrm{-44}\,51\right]\,\left[3\right]\,1-x\right)}^2{\left(-1+x\right)}^3{x}^5}$

ratpol:=convert(ratpol,StandardFunctions):

length(ratpol),degree(denom(ratpol),x);

$1860,96$

pfratpol := convert(ratpol,parfrac,x):

The computation time is reduced by a factor of 250, and memory usage by a factor of 80.

It is often necessary to transform a polynomial into a list or Vector of coefficients.  Using the natural [seq(coeff(p,x,i),i=0..degree(p,x))] command for a polynomial p in x leads to O(n^2) behavior (where n=degree(p,x)).  There are now two routines, PolynomialTools[CoefficientVector] and PolynomialTools[CoefficientList], that perform this operation in O(n) time.  In fact, if the polynomial is sparse, it is performed in O(#terms), as the examples below show.

with(PolynomialTools):

p := 1-13*x+x^5;

$p≔x^5-13x+1$

time(CoefficientVector(p,x));

$0.014$

time(CoefficientVector(1+x+x^1000000000,x,storage=sparse));

$0.$

In Maple 8, the orthopoly package uses a more efficient algorithm to compute orthogonal polynomials for algebraic and complex rational values of the variable x.

time( orthopoly[L](400,x) );  # about 1000 seconds in Maple 7

$0.003$

time( orthopoly[P](600,1/3) );  # about 800 seconds in Maple 7

$0.005$

The LeastSquares routine in the LinearAlgebra package in Maple 8 contains a highly efficient indirect sparse real solver for floating-point problems.  In particular, it is very efficient for sparse problems with densities less than 15 percent.

In Maple 8, the fsolve routine efficiently solves univariate polynomials for all roots at higher than default settings of the Digits environment variable.

The following fsolve computation requires only approximately 30 percent of the time required in Maple 7.

Digits := 20:

p := randpoly(x,degree=100,dense):

fsolve(p,x,complex):

Evaluation of symbolic boolean expressions has been significantly optimized, so that the complexity is no longer exponential in time and space.

time(a1 and a2 and a3 and a4 and a5 and a6 and a7 and a8 and a9 and a10 and a11 and a12 and a13 and a14 and a15 and a16 and a17 and a18 and a19 and a20 and a21 and a22 and a23 and a24 and a25 and a26 and a27 and a28 and a29 and a30); # about 100 seconds in Maple 7

$0.$

Generation of sparse random Matrices is much faster in Maple 8.  A new algorithm is used when density < 1.

time( LinearAlgebra:-RandomMatrix(1000,1000,
         density=.1,outputoptions=[datatype=float[8],storage=sparse]) );

$0.028$

Faster algorithms have been incorporated for some integer matrix problems.  These include HermiteForm, SmithForm, Rank, and Determinant in the LinearAlgebra package.

A := LinearAlgebra[RandomMatrix](50,50,density=.1):

time(LinearAlgebra[SmithForm](A));

$0.209$

The routine CharacteristicPolynomial in the LinearAlgebra package has been replaced with a more efficient algorithm.

The resultant routine for Z[x] has been changed to use a probabilistic method because the coefficient bounds on the resultant, based on the determinant of Sylvester's matrix, were too large and led to inefficiency. For example, the resultant of the two cyclotomic polynomials below is 1 but the coefficient bound used was an integer of length 315 digits.  The new code is about 500 times faster in this worst case example for the coefficient bound.

Phi := numtheory[cyclotomic]:

f := Phi(1001,z): degree(f,z);

$720$

g := Phi(30,z): degree(g,z);

$8$

resultant(f,g,z);

$1$

The ratrecon routine reconstructs from u(x) and m(x) a rational function n(x)/d(x) satisfying n(x)/d(x) == u(x) mod m(x). It can be used for Pade approximation and to interpolate a rational function from sufficiently many values of the function. We have modified the implementation to use the monic Euclidean algorithm for improved efficiency.

f := 1/(1-x-x^2);

$f≔\frac{1}{-x^2-x+1}$

T := convert(taylor(f,x),polynom);

$T≔8x^5+5x^4+3x^3+2x^2+x+1$

ratrecon(T,x^6,x);

$-\frac{1}{x^2+x-1}$

X := [seq(i,i=0..4)]; Y := [seq(eval(f,x=i),i=0..4)];

$X≔\left[0\&comma;1\&comma;2\&comma;3\&comma;4\right]$

$Y≔\left[1\&comma;\mathrm{-1}\&comma;-\frac{1}{5}\&comma;-\frac{1}{11}\&comma;-\frac{1}{19}\right]$

ratrecon( interp(X,Y,x), mul( x-xval, xval=X ), x );

$-\frac{1}{x^2+x-1}$

We have improved the efficiency of the computation of the greatest common divisors of polynomials in Z[x,y] and Q(alpha)[x], that is, bivariate polynomials over the integers and univariate polynomials over an algebraic number field with one field extension. The main improvement for Z[x,y] is in the treatment of the content of the polynomials in the modular algorithm.  The new algorithm is always fast when the GCD is small.  For Q(alpha)[x], it is improved by (i) using rational reconstruction, (ii) avoiding the inversion of the leading coefficients of the input, and (iii) performing the trial divisions using integer arithmetic.

Maple 8 has improved management facilities for large expressions with many common subexpressions.

F := proc(n) option remember; if n<2 then n else x*F(n-1)+F(n-2) fi end:

f := proc()
    local    e1, e2, e3, e4, L;
    e1 := F(30); e2 := F(31);
    e3 := F(32); e4 := F(33);
    L := [[e1,e2],[e3,e4]];
    map(nops,L);
end:

time(f());

$0.$

A third-order iterative scheme is used in Maple 8 to compute the square root of a floating-point number. In addition to speed improvements, the new algorithm implements IEEE-style exact rounding (for all rounding modes). This means that a Maple float is evaluated to the current setting of Digits, and then treated as exact for the purposes of computation (this is part of the standard Maple floating-point model). The result is rounded is such a way that it would be correct, even if the square root were first computed to infinite precision. For example, since sqrt(0.9999999999) = .9999999999499999999987..., the correct (default) rounding of this result to 10 digits is 0.9999999999, which is the result Maple returns.

The ImportMatrix routine has been optimized.

Top-level access to rtable elements has been optimized.

In Maple 8, there are great efficiency improvements for evaluating large, highly recursive expressions at a point using eval(expr, x=a). In previous releases, eval() visits every node in the expression tree. In Maple 8, it visits every unique subexpression once, even if it occurs many times in the expression.