Sparse Distributed Multivariate Polynomials for Maple Roman Pearce, Michael Monagan Simon Fraser University June 2009 This library provides a data structure and fast arithmetic for sparse distributed multivariate polynomials. It is under development at Simon Fraser University in Vancouver, Canada.

Download the correct version of SDMP for your computer's architecture from http://www.cecm.sfu.ca/~rpearcea and decompress the files. Modify one of the paths below to point to the directory where the files are stored and execute the commands in that section.

If you decompressed the files to a folder called sdmp on the desktop. Change rpearcea to your username. restart; currentdir("C:/Documents and Settings/rpearce/Desktop/sdmp"): read "sdmp.mpl":

If you decompressed the files to a directory named sdmp in your home directory. Change rpearcea to your username. restart; currentdir("/Users/rpearce/sdmp"): read "sdmp.mpl":

If you decompressed the files to a directory named sdmp in your home directory. Change rpearcea to your username. restart; currentdir("/home/rpearce/sdmp"): read "sdmp.mpl":

Execute the following statement to test whether the package is working: f := sdmp(x^3+x+1,plex(x));

The easiest way to try the SDMP package is to use the commands in the AutoPack submodule. They will automatically convert Maple polynomials to the SDMP datatype, perform a computation, and convert the result back to a Maple polynomial. Not all of the functionality of SDMP is available through the AutoPack module, but you can multiply and divide polynomials. The AutoPack:-Multiply command is n-ary, and AutoPack:-Divide behaves exactly like Maple's divide command. f := randpoly([x,y,z],degree=30,terms=100): g := randpoly([x,y,z],degree=30,terms=100): h := randpoly([x,y,z],degree=30,terms=100): p := sdmp:-AutoPack:-Multiply(f,g,h): nops(p); sdmp:-AutoPack:-Divide(p,f,'q'); nops(q); You can also do computations with coefficients in Zp for p < kernelopts(maximmediate), which is 30 bits on a 32-bit machine or 62 bits on a 64 bit machine. char := characteristic=prevprime(kernelopts(maximmediate)): char; p1 := sdmp:-AutoPack:-Multiply(f,g,h,char): sdmp:-AutoPack:-Divide(p1, f, 'q', char);

To use all of the features of SDMP you will need to convert polynomials to its native data structure. The commands sdmp:-Import and sdmp:-Export will import and export Maple polynomials. As a shorthand, you can also call the sdmp module itself as if it were a function and it will determine whether to import or export. To import polynomials you must order the variables with a monomial order. The following monomial orders are supported: plex - pure lexicographic order grlex - graded lexicographic order tdeg - graded reverse lexicographic order F := randpoly([x,y,z]); f := sdmp:-Import(F, plex(x,y,z)); sdmp:-Export(f); You can also use the sdmp function for both importing and exporting. G := randpoly([x,y,z]); g := sdmp(G, plex(x,y,z)); sdmp(g); There is very limited error checking at the moment, so please be careful about what polynomials you import :)

SDMP supports the following operations (including optional arguments): # addition (n-ary) sdmp:-Add(f, g, ..., characteristic=p); # multiplication (n-ary) sdmp:-Multiply(f, g, ..., characteristic=p); # exact division sdmp:-Divide(f, g, G, 's', 'q', characteristic=p); # quotient and remainder (presently disabled) # sdmp:-Quo(f, g, G, 's', 'r', characteristic=p); # sdmp:-Rem(f, g, G, 's', 'q', characteristic=p); f, g - sdmp polynomials G - list of sdmp polynomials (optional) 's' - assigned a common denominator (optional) 'r', 'q' - assigned remainder or quotient (optional) characteristic=p (optional)

Given three univariate polynomials {f,g,h} we will perform some computations using Maple's builtin commands and SDMP: f := randpoly(x,degree=1000,terms=500): F := sdmp(f,plex(x)); g := randpoly(x,degree=1000,terms=500): G := sdmp(g,plex(x)); h := randpoly(x,degree=100,terms=50): H := sdmp(h,plex(x)); Multiply out f*g and assign it to p. p := expand(f*g): P := sdmp:-Multiply(F,G); Test whether g divides p exactly and if so, assign the quotient to q. For SDMP polynomials (which can only have integer coefficients) the quotient is Q/s. divide(p,g,'q'); sdmp:-Divide(P,G,'s','Q'); Q; evalb(q = sdmp(Q)/s); Note: quotient and remainder commands not available in this release. Compute the remainder of p divided by h and assign the quotient to q. For SDMP polynomials the remainder is R/s and the quotient is Q/s. # r := rem(p,h,x,'q'): # R := sdmp:-Rem(P,H,'s','Q'); # evalb(r = sdmp(R)/s); # evalb(q = sdmp(Q)/s); The common denominator s can be very large. # length(s);

For large computations it is useful to pack multiple exponents into each machine word. This speeds up the computation and reduces the memory required to store the result. For example, specifying pack=3 on a 32-bit machine will use 10 bits per exponent. All of the polynomials in a computation must be packed in the same way. Below we show a multiplication with packed and unpacked exponents. The size of the result is cut in half. f := sdmp(randpoly([x,y,z],degree=100,terms=3000), plex(x,y,z)); p := sdmp:-Multiply(f,f,characteristic=32003); length(p)*kernelopts(wordsize)/8/1024.^2; # size in MB f := sdmp(f, plex(x,y,z), pack=3); p := sdmp:-Multiply(f,f,characteristic=32003); length(p)*kernelopts(wordsize)/8/1024.^2; # size in MB There is currently no bounds checking in SDMP so be careful not to overflow the exponents. Below are the sizes of the monomials in various orders, not including one or more words for a coefficient: plex = (# variables) / pack grlex = (# variables + 1) / pack tdeg = (2*(# variables)-1) / pack