 Improvements for Polynomials - Maple Programming Help Improvements for Polynomials

Maple 18 builds upon the efficiency improvements of earlier releases for multivariate polynomial operations. More polynomials now take advantage of the high performance data structure introduced in Maple 17, further improvements has been made to Maple’s performance for large computations, and polynomial computations modulo p are now significantly faster. As a result of these changes, computations that explicitly rely on polynomials, as well as the many Maple library routines that rely on underlying polynomial computations, are now faster.

Expanded Degree Range

In Maple 18, the maximum degree range of polynomials that can be stored in the new data structure has been expanded. In Maple 17, a polynomial in n variables used $\frac{64}{n+1}$ bits to store the total degree and each of the n exponents. Thus, the maximum total degree was equal to the maximum partial degree in Maple 17.  For most values of n, this is needlessly restrictive. For example, for $n=11$ variables there are five bits per exponent and five bits for the total degree, leaving four bits unused. In Maple 18, the extra bits are given to the total degree, which allows a much greater range of polynomials to be stored in the new data structure. The practical limits for a 64-bit machine are shown below, and we have highlighted cases where we are limited by the bits available for the total degree. In most cases, we can store the sum of maximum partial degrees.

 Number of variables 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Maximum partial degree 2097151 65535 4095 1023 511 255 127 63 31 31 15 15 15 15 Maximum total degree 4194302 65535 16380 5115 1023 255 255 567 310 341 180 195 210 15

 Number of variables 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Maximum partial degree 7 7 7 7 7 3 3 3 3 3 3 3 3 3 3 3 Maximum total degree 112 119 126 127 15 63 66 69 72 75 78 81 84 63 15 3

Determinant Benchmark

We compute determinants of $n$ by $n$ Vandermonde matrices in the variables {${x}_{1}$, ${x}_{2}$, ..., ${x}_{n}$}.  The determinant has $n!$ terms and total degree $\frac{n\left(n-1\right)}{2}$.  For $n=4,$ the matrix and determinant are:

$A:=\mathrm{LinearAlgebra}:-\mathrm{VandermondeMatrix}\left(\left[{x}_{1},{x}_{2},{x}_{3},{x}_{4}\right]\right)$

 $\left[\begin{array}{cccc}{1}& {{x}}_{{1}}& {{x}}_{{1}}^{{2}}& {{x}}_{{1}}^{{3}}\\ {1}& {{x}}_{{2}}& {{x}}_{{2}}^{{2}}& {{x}}_{{2}}^{{3}}\\ {1}& {{x}}_{{3}}& {{x}}_{{3}}^{{2}}& {{x}}_{{3}}^{{3}}\\ {1}& {{x}}_{{4}}& {{x}}_{{4}}^{{2}}& {{x}}_{{4}}^{{3}}\end{array}\right]$ (2.1)

 ${{x}}_{{1}}^{{3}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{3}}{-}{{x}}_{{1}}^{{3}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{4}}{-}{{x}}_{{1}}^{{3}}{}{{x}}_{{2}}{}{{x}}_{{3}}^{{2}}{+}{{x}}_{{1}}^{{3}}{}{{x}}_{{2}}{}{{x}}_{{4}}^{{2}}{+}{{x}}_{{1}}^{{3}}{}{{x}}_{{3}}^{{2}}{}{{x}}_{{4}}{-}{{x}}_{{1}}^{{3}}{}{{x}}_{{3}}{}{{x}}_{{4}}^{{2}}{-}{{x}}_{{1}}^{{2}}{}{{x}}_{{2}}^{{3}}{}{{x}}_{{3}}{+}{{x}}_{{1}}^{{2}}{}{{x}}_{{2}}^{{3}}{}{{x}}_{{4}}{+}{{x}}_{{1}}^{{2}}{}{{x}}_{{2}}{}{{x}}_{{3}}^{{3}}{-}{{x}}_{{1}}^{{2}}{}{{x}}_{{2}}{}{{x}}_{{4}}^{{3}}{-}{{x}}_{{1}}^{{2}}{}{{x}}_{{3}}^{{3}}{}{{x}}_{{4}}{+}{{x}}_{{1}}^{{2}}{}{{x}}_{{3}}{}{{x}}_{{4}}^{{3}}{+}{{x}}_{{1}}{}{{x}}_{{2}}^{{3}}{}{{x}}_{{3}}^{{2}}{-}{{x}}_{{1}}{}{{x}}_{{2}}^{{3}}{}{{x}}_{{4}}^{{2}}{-}{{x}}_{{1}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{3}}^{{3}}{+}{{x}}_{{1}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{4}}^{{3}}{+}{{x}}_{{1}}{}{{x}}_{{3}}^{{3}}{}{{x}}_{{4}}^{{2}}{-}{{x}}_{{1}}{}{{x}}_{{3}}^{{2}}{}{{x}}_{{4}}^{{3}}{-}{{x}}_{{2}}^{{3}}{}{{x}}_{{3}}^{{2}}{}{{x}}_{{4}}{+}{{x}}_{{2}}^{{3}}{}{{x}}_{{3}}{}{{x}}_{{4}}^{{2}}{+}{{x}}_{{2}}^{{2}}{}{{x}}_{{3}}^{{3}}{}{{x}}_{{4}}{-}{{x}}_{{2}}^{{2}}{}{{x}}_{{3}}{}{{x}}_{{4}}^{{3}}{-}{{x}}_{{2}}{}{{x}}_{{3}}^{{3}}{}{{x}}_{{4}}^{{2}}{+}{{x}}_{{2}}{}{{x}}_{{3}}^{{2}}{}{{x}}_{{4}}^{{3}}$ (2.2)

The benchmark was performed on an Intel Core i7 3930K 3.2 GHz with 64 GB RAM running 64-bit Linux. Maple 16 uses the traditional "sum of products" data structure for all polynomials. Maple 17 uses the new polynomial data structure for determinants up to $n=9$, but for $n=10$ the total degree field overflows and performance degrades. The extra degree bits in Maple 18 allow the computation to reach $n=12,$which produces 479 million terms. Faster Dense Algorithms

Maple 18 uses Kronecker substitution to multiply and divide dense polynomials in subquadratic time. Performance has been improved with an upgrade to GMP 5.1.1 and tweaks to Maple's garbage collector. Below, we multiply and divide dense polynomials in n variables with degree d in each variable and b bit coefficients. The benchmark was performed on an Intel Core i5 4670 3.4 GHz with 16 GB RAM running 64-bit Linux.

$c≔\mathrm{rand}\left(1..\mathrm{ceil}\left({2}^{\mathrm{evalf}\left(\frac{b}{n}\right)}\right)\right):$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{divide}\left(\mathrm{expand}\left(f\cdot g\right),f,'q'\right)\right):$ Polynomial Powers

Maple 18 uses a new algorithm to expand powers of short polynomials. This complements square and multiply (used for dense polynomials) and repeated multiplication (used for sparse polynomials).  An improved heuristic selects among these algorithms. The timings below are on an Intel Core i5 4670 3.4 GHz with 16 GB RAM running 64-bit Linux. Computations Modulo p

Prior to Maple 18, polynomial computations over Zp called interpreted Maple library routines. This incurred significant overhead for small operations. For this release, we implemented Eval, Expand, and Divide in the kernel in C for the non-algebraic number case. Their performance is comparable to eval, expand, and divide, except that numbers are reduced to modulo p to prevent expression swell. The benchmark below times these operations for small polynomials on an Intel Core i5 4670 3.4 GHz with 16 GB RAM running 64-bit Linux.

$p≔32003:$$\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}k≔10000:$

$v≔\left[\mathrm{seq}\left(\mathrm{cat}\left(x,i\right),i=1..n\right)\right]:$

$e≔\left[\mathrm{seq}\left(i=\mathrm{rand}\left(\right),i=v\right)\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}p:$

$f≔\mathrm{randpoly}\left(v,\mathrm{degree}=2,\mathrm{dense}\right):$

$g≔\mathrm{randpoly}\left(v,\mathrm{degree}=2,\mathrm{dense}\right):$

$r≔\mathrm{CodeTools}:-\mathrm{Usage}\left(\left[\mathrm{seq}\left(\mathrm{Expand}\left(\left(f+i\right)g\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}p,i=1..k\right)\right]\right):$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\left[\mathrm{seq}\left(\mathrm{Divide}\left(i,g,'q'\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}p,i=r\right)\right]\right):$

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\left[\mathrm{seq}\left(\left(\mathrm{Eval}\left(i,e\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}p,i=r\right)\right]\right):$

The bar chart below shows the overall times for each n, with the times for Eval on top of the times for Divide and the times for Expand on the bottom. 