Performance - Maple Help

Performance

Maple 2018 improves the performance of many routines.

Gröbner Bases

Gröbner bases lie at the heart of many fundamental operations, including solving systems of equations and integration, so performance improvements in Gröbner bases results in faster calculations in other areas as well. Maple 2018 includes new optimizations to the F4 algorithm to increase parallel speedup when computing large total degree Gröbner bases.  On a quad core Core i7 with hyperthreading, the new implementation runs 33 percent faster and parallel speedup increases from 1.94x to 2.84x.

$\mathrm{cyclic9}≔\left[\mathrm{x0}+\mathrm{x1}+\mathrm{x2}+\mathrm{x3}+\mathrm{x4}+\mathrm{x5}+\mathrm{x6}+\mathrm{x7}+\mathrm{x8},\mathrm{x0}\mathrm{x1}+\mathrm{x0}\mathrm{x8}+\mathrm{x1}\mathrm{x2}+\mathrm{x2}\mathrm{x3}+\mathrm{x3}\mathrm{x4}+\mathrm{x4}\mathrm{x5}+\mathrm{x5}\mathrm{x6}+\mathrm{x6}\mathrm{x7}+\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}+\mathrm{x0}\mathrm{x1}\mathrm{x8}+\mathrm{x0}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}+\mathrm{x2}\mathrm{x3}\mathrm{x4}+\mathrm{x3}\mathrm{x4}\mathrm{x5}+\mathrm{x4}\mathrm{x5}\mathrm{x6}+\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}+\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}+\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}+\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}+\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}+\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}+\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x1}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x0}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}+\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8},\mathrm{x0}\mathrm{x1}\mathrm{x2}\mathrm{x3}\mathrm{x4}\mathrm{x5}\mathrm{x6}\mathrm{x7}\mathrm{x8}-1\right]:$

$G≔\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{Groebner}:-\mathrm{Basis}\left(\mathrm{cyclic9},\mathrm{tdeg}\left(\mathrm{x0},\mathrm{x1},\mathrm{x2},\mathrm{x3},\mathrm{x4},\mathrm{x5},\mathrm{x6},\mathrm{x7},\mathrm{x8}\right),\mathrm{characteristic}={2}^{31}-1\right)\right):$

 memory used=24.08MiB, alloc change=18.98MiB, cpu time=2.73m, real time=25.73s, gc time=0ns

Maple 2018 also includes a new implementation of the FGLM algorithm for converting total degree Gröbner bases to lexicographical order, with improved performance and lower memory requirements.  On this example, the FGLM algorithm runs about 3.5x faster.

$\mathrm{katsura12}≔\left[2\mathrm{x0}\mathrm{x11}+2\mathrm{x1}\mathrm{x10}+2\mathrm{x1}\mathrm{x12}+2\mathrm{x2}\mathrm{x9}+2\mathrm{x3}\mathrm{x8}+2\mathrm{x4}\mathrm{x7}+2\mathrm{x5}\mathrm{x6}-\mathrm{x11},2\mathrm{x0}\mathrm{x10}+2\mathrm{x1}\mathrm{x11}+2\mathrm{x1}\mathrm{x9}+2\mathrm{x12}\mathrm{x2}+2\mathrm{x2}\mathrm{x8}+2\mathrm{x3}\mathrm{x7}+2\mathrm{x4}\mathrm{x6}+{\mathrm{x5}}^{2}-\mathrm{x10},2\mathrm{x0}\mathrm{x9}+2\mathrm{x1}\mathrm{x10}+2\mathrm{x1}\mathrm{x8}+2\mathrm{x11}\mathrm{x2}+2\mathrm{x12}\mathrm{x3}+2\mathrm{x2}\mathrm{x7}+2\mathrm{x3}\mathrm{x6}+2\mathrm{x4}\mathrm{x5}-\mathrm{x9},2\mathrm{x0}\mathrm{x8}+2\mathrm{x1}\mathrm{x7}+2\mathrm{x1}\mathrm{x9}+2\mathrm{x10}\mathrm{x2}+2\mathrm{x11}\mathrm{x3}+2\mathrm{x12}\mathrm{x4}+2\mathrm{x2}\mathrm{x6}+2\mathrm{x3}\mathrm{x5}+{\mathrm{x4}}^{2}-\mathrm{x8},2\mathrm{x0}\mathrm{x7}+2\mathrm{x1}\mathrm{x6}+2\mathrm{x1}\mathrm{x8}+2\mathrm{x10}\mathrm{x3}+2\mathrm{x11}\mathrm{x4}+2\mathrm{x12}\mathrm{x5}+2\mathrm{x2}\mathrm{x5}+2\mathrm{x2}\mathrm{x9}+2\mathrm{x3}\mathrm{x4}-\mathrm{x7},2\mathrm{x0}\mathrm{x6}+2\mathrm{x1}\mathrm{x5}+2\mathrm{x1}\mathrm{x7}+2\mathrm{x10}\mathrm{x4}+2\mathrm{x11}\mathrm{x5}+2\mathrm{x12}\mathrm{x6}+2\mathrm{x2}\mathrm{x4}+2\mathrm{x2}\mathrm{x8}+{\mathrm{x3}}^{2}+2\mathrm{x3}\mathrm{x9}-\mathrm{x6},2\mathrm{x0}\mathrm{x5}+2\mathrm{x1}\mathrm{x4}+2\mathrm{x1}\mathrm{x6}+2\mathrm{x10}\mathrm{x5}+2\mathrm{x11}\mathrm{x6}+2\mathrm{x12}\mathrm{x7}+2\mathrm{x2}\mathrm{x3}+2\mathrm{x2}\mathrm{x7}+2\mathrm{x3}\mathrm{x8}+2\mathrm{x4}\mathrm{x9}-\mathrm{x5},2\mathrm{x0}\mathrm{x4}+2\mathrm{x1}\mathrm{x3}+2\mathrm{x1}\mathrm{x5}+2\mathrm{x10}\mathrm{x6}+2\mathrm{x11}\mathrm{x7}+2\mathrm{x12}\mathrm{x8}+{\mathrm{x2}}^{2}+2\mathrm{x2}\mathrm{x6}+2\mathrm{x3}\mathrm{x7}+2\mathrm{x4}\mathrm{x8}+2\mathrm{x5}\mathrm{x9}-\mathrm{x4},2\mathrm{x0}\mathrm{x3}+2\mathrm{x1}\mathrm{x2}+2\mathrm{x1}\mathrm{x4}+2\mathrm{x10}\mathrm{x7}+2\mathrm{x11}\mathrm{x8}+2\mathrm{x12}\mathrm{x9}+2\mathrm{x2}\mathrm{x5}+2\mathrm{x3}\mathrm{x6}+2\mathrm{x4}\mathrm{x7}+2\mathrm{x5}\mathrm{x8}+2\mathrm{x6}\mathrm{x9}-\mathrm{x3},2\mathrm{x0}\mathrm{x2}+{\mathrm{x1}}^{2}+2\mathrm{x1}\mathrm{x3}+2\mathrm{x10}\mathrm{x12}+2\mathrm{x10}\mathrm{x8}+2\mathrm{x11}\mathrm{x9}+2\mathrm{x2}\mathrm{x4}+2\mathrm{x3}\mathrm{x5}+2\mathrm{x4}\mathrm{x6}+2\mathrm{x5}\mathrm{x7}+2\mathrm{x6}\mathrm{x8}+2\mathrm{x7}\mathrm{x9}-\mathrm{x2},2\mathrm{x0}\mathrm{x1}+2\mathrm{x1}\mathrm{x2}+2\mathrm{x10}\mathrm{x11}+2\mathrm{x10}\mathrm{x9}+2\mathrm{x11}\mathrm{x12}+2\mathrm{x2}\mathrm{x3}+2\mathrm{x3}\mathrm{x4}+2\mathrm{x4}\mathrm{x5}+2\mathrm{x5}\mathrm{x6}+2\mathrm{x6}\mathrm{x7}+2\mathrm{x7}\mathrm{x8}+2\mathrm{x8}\mathrm{x9}-\mathrm{x1},{\mathrm{x0}}^{2}+2{\mathrm{x1}}^{2}+2{\mathrm{x10}}^{2}+2{\mathrm{x11}}^{2}+2{\mathrm{x12}}^{2}+2{\mathrm{x2}}^{2}+2{\mathrm{x3}}^{2}+2{\mathrm{x4}}^{2}+2{\mathrm{x5}}^{2}+2{\mathrm{x6}}^{2}+2{\mathrm{x7}}^{2}+2{\mathrm{x8}}^{2}+2{\mathrm{x9}}^{2}-\mathrm{x0},2\mathrm{x12}+2\mathrm{x1}+2\mathrm{x11}+\mathrm{x0}+2\mathrm{x10}+2\mathrm{x9}+2\mathrm{x2}+2\mathrm{x8}+2\mathrm{x3}+2\mathrm{x7}+2\mathrm{x4}+2\mathrm{x6}+2\mathrm{x5}-1\right]:$

 memory used=186.80MiB, alloc change=256.00MiB, cpu time=82.03s, real time=26.78s, gc time=93.75ms

Kernel Improvements

Fast code has been added to the subs command for the case of replacing variables in polynomials with products.  The following types of substitutions run significantly faster on large polynomials.

 ${{x}}^{{4}}{+}{3}$ (2.1)

Kernel code has been added to speed up tests for polynomials and rational functions using Maple library types.  The examples below run about 6x faster.

 ${\mathrm{true}}$ (2.2)

Logic

The SAT solver used by the Satisfy and Satisfiable commands is now MapleSAT, a SAT solver based on MiniSat but with improvements to the variable branching heuristic.  The following example runs about 4x faster in Maple 2018 than Maple 2017.  It encodes an instance of the pigeonhole principle, the fact that $n$ pigeons cannot fit in $n-1$ holes if each hole can contain at most one pigeon.

 ${561}$ (3.1)

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{Logic}:-\mathrm{Satisfiable}\left(\mathrm{PHP}\right)\right)$

 ${\mathrm{false}}$ (3.2)

Graph Theory

The ChromaticNumber command which computes the chromatic number of a graph now uses a hybrid algorithm by default.  This algorithm runs two separate implementations in parallel and returns the result of whichever method finishes first.  Consequently, some examples which could not be solved in Maple 2017 in a reasonable amount of time can be quickly solved in Maple 2018.  In the following example Maple 2017 is unable to determine the chromatic number after an hour of CPU time while Maple 2018 does so in seconds.  The example is a random graph which appears in the paper "Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning" by D. Johnson, C. Aragon, L. McGeoch, and C. Schevon.

 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 125 vertices and 736 edge\left(s\right)}}$ (4.1)

$\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{GraphTheory}:-\mathrm{ChromaticNumber}\left(G\right)\right)$

memory used=266.60KiB, alloc change=10.94MiB, cpu time=48.00ms, real time=1.14s, gc time=0ns

 ${5}$ (4.2)

Sparse Linear Equations mod p

The msolve command has been updated with a new solver for sparse linear equations for primes up to ${2}^{31}-1$.  It pivots for structure and sparsity and quickly detects redundant equations in overdetermined systems.  The example below runs over 100x faster.

 memory used=1.03MiB, alloc change=0 bytes, cpu time=125.00ms, real time=19.00ms, gc time=0ns

Matrix Inverse with Trig Functions

The inverse of a matrix with trigonometric functions is faster.

 ${0.078}$ (6.1)



timelimit

The timelimit command is useful for putting a time bound on a computation, preventing it from running longer than you expect. The timelimit command now has virtually no overhead.

 > f := proc(x)     description "Number of Primes less than x";     global i,j;     i:=0:     for j to x do         if isprime(j) then             i := i + 1;         end if;     end do:     return i; end proc:
 > timelimit(0.5,f(1000000));
 > printf("The number of primes less than %a is %a. This was computed in %.2f s.", j, i, 0.5);
 The number of primes less than 150743 is 13909. This was computed in 0.50 s.