Efficiency Improvements in Maple 7

A number of efficiency improvements have been applied in order to make Maple 7 faster and use less memory.


Numeric Linear Algebra



The following enhancements to the LinearAlgebra package lead to faster computation and reduced storage requirements.

•

Optimized Routines for Basic Operations: Significant improvements to the speed of hardware floatingpoint computations in the LinearAlgebra package have been made for supported UNIX platforms. This is due to new linking of the external NAG and CLAPACK libraries with the optimized ATLAS library. These optimizations parallel the high performance present in Maple 6 for the Microsoft Windows platforms, which was obtained from linking with Intel's Math Kernel library.

•

Enhanced Support for Band and Packed Triangular Matrices: There is added support for fast matrix operations involving floatingpoint band and packed triangular matrices. This support, provided through external routines specially designed for such matrix structures, allows the operations to be done with a minimum amount of storage.

•

Enhanced Support for Sparse Matrices: There is added support for efficient floatingpoint sparse matrix arithmetic. In addition, the LinearSolve function now allows the option of choosing an iterative solver for sparse symmetric linear systems. The iterative solver usually requires significantly less storage than traditional methods when the input matrix is very large and sparse.

•

Additional Improvements: There is improved floatingpoint support for the Eigenvectors, Transpose, and HermitianTranspose functions. The Eigenvectors function now uses a "divideandconquer" scheme for nongeneralized realsymmetric and complexhermitian problems. Also, the calculation of optimized solutions in the rankdeficient case has been made more efficient in the LeastSquares function.



Numerical Ordinary Differential Equations


•

Maple's default numerical ODE solver has been replaced by a new rkf45 solver which has been adapted to perform operations in a mixture of native Maple code and external compiled C code. The new code computes solutions 25 times faster for most problems, also storing computed solution values so that requests for points in the already computed range or plots over that range can be performed in negligible time.

•

Maple's highaccuracy numerical ODE solver, dverk78, has also been substantially improved, obtaining answers in less than half the time of the dverk78 of prior releases.



Large Integer Division and FloatingPoint Division


•

Maple has a new algorithm for large integer division. The new algorithm is based on a paper in ISSAC 97, pp. 339341, "Practical Integer Division with Karatsuba Complexity" by Tudor Jebelean. The complexity of Jebelean's division algorithm is O(n^log[2](3)) (approximately n^1.585), while the complexity of classical integer division is O(n^2). In practice, Maple's implementation of Jebelean's algorithm becomes faster than the classical algorithm when the divisor is of size 50 words and becomes two times faster for a divisor of 250 words. This speed improvement increases for larger divisors.

•

In Maple, Jebelean's division algorithm is used when the divisor is greater than 50 words in size. For smaller divisors, the classical division algorithm will be used.

•

Since Maple's floatingpoint division uses routines for integer division, floatingpoint division has also become faster.



String Operations


•

The new package StringTools contains fast, optimized basic string operations.



List Operations


•

The new package ListTools contains basic list operations.



Miscellaneous


•

Polynomial factorization over Z[x] now uses an implementation of M. van Hoeij's algorithm (M. van Hoeij, "Factoring polynomials and the knapsack problem", to appear in Journal of Number Theory). This allows factor to quickly find factorizations for classes of polynomials that are hard to factor, such as resolvents or SwinnertonDyer polynomials.

>

factor( x^128x^112+x^80x^64+x^48x^16+1 ); # Takes very long in Maple 6.

$\left({{x}}^{{8}}{}{{x}}^{{7}}{+}{{x}}^{{5}}{}{{x}}^{{4}}{+}{{x}}^{{3}}{}{x}{+}{1}\right){}\left({{x}}^{{8}}{+}{{x}}^{{7}}{}{{x}}^{{5}}{}{{x}}^{{4}}{}{{x}}^{{3}}{+}{x}{+}{1}\right){}\left({{x}}^{{16}}{+}{{x}}^{{14}}{}{{x}}^{{10}}{}{{x}}^{{8}}{}{{x}}^{{6}}{+}{{x}}^{{2}}{+}{1}\right){}\left({{x}}^{{32}}{+}{{x}}^{{28}}{}{{x}}^{{20}}{}{{x}}^{{16}}{}{{x}}^{{12}}{+}{{x}}^{{4}}{+}{1}\right){}\left({{x}}^{{64}}{+}{{x}}^{{56}}{}{{x}}^{{40}}{}{{x}}^{{32}}{}{{x}}^{{24}}{+}{{x}}^{{8}}{+}{1}\right)$
 (1) 
•

The computation of factorials now uses a new algorithm. This results in approximately thirty times better performance for large factorial computations, and significantly extends the range of factorial computations that can be performed. There is no longer any practical limit on the size of an argument to a factorial.

>

st := time(): 25000!: time()  st; # about 30 seconds in Maple 6

>

st := time(): 45000!: time()  st; # not possible in Maple 6

>

system( "/usr/sbin/psrinfo v grep MHzhead 1" ):

The sparcv9 processor operates at 400 MHz,



•

The routines iroot and iperfpow are significantly faster due to new algorithms.

•

The sort procedure now takes a length option to sort a list of expressions by length.

>

expr := convert( series( tan( x ), x= 0 ), 'polynom' );

${\mathrm{expr}}{\u2254}{x}{+}\frac{{1}}{{3}}{}{{x}}^{{3}}{+}\frac{{2}}{{15}}{}{{x}}^{{5}}$
 (4) 
>

sort( convert( indets( expr, 'algebraic' ), 'list' ), 'length' );

$\left[{3}{\,}{5}{\,}{x}{\,}\frac{{1}}{{3}}{\,}{{x}}^{{3}}{\,}{{x}}^{{5}}{\,}\frac{{2}}{{15}}{\,}\frac{{{x}}^{{3}}}{{3}}{\,}\frac{{2}{}{{x}}^{{5}}}{{15}}{\,}{x}{+}\frac{{1}}{{3}}{}{{x}}^{{3}}{+}\frac{{2}}{{15}}{}{{x}}^{{5}}\right]$
 (5) 

