next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc > rings > monomial orderings > packing monomials for efficiency

packing monomials for efficiency

Sometimes for efficiency reasons, it is important to pack exponent vectors several exponents per machine word. Polynomials take less space, and monomial operations such as comparison and multiplication become faster.

The monomial order keys Lex and GRevLex allow packing. The MonomialSize => n option allows one to set the minimum packing size, in number of bits. Monomials are stored as signed exponent vectors, so maximum exponents of 2^(n-1)-1 are possible for packed variables. Useful values include 8, 16, 32, and (on 64-bit machines) 64. The default monomial size is 32.

i1 : A = QQ[a..d,MonomialSize=>8]

o1 = A

o1 : PolynomialRing
i2 : B = QQ[x,y,z,w,MonomialSize=>16,MonomialOrder=>Lex]     

o2 = B

o2 : PolynomialRing
The maximum degree for monomials in A is 127. Monomials of higher degree will encounter a monomial overflow. In the second example, the maximum exponent is 32767 (2^15-1).

It is possible to pack different parts of the monomial with different sizes. For example, the following order has two blocks: a graded reverse lexicographic block of 3 variables, packed into one 32-bit word, and a second lexicographic block for 4 variables, taking 4 32-bit words. Each monomial will be packed into 5 32-bit words (on a computer with a 32-bit word size).

i3 : C = QQ[a,b,c,x,y,z,w,MonomialOrder=>{MonomialSize=>8,3,MonomialSize=>32,Lex=>4}];

i4 : D = QQ[a..d,MonomialOrder=>Lex];
i5 : a^1000000000

      1000000000
o5 = a

o5 : D

This exponent would give a monomial overflow error in the next two rings.

i6 : E = QQ[a..d,MonomialSize=>16,MonomialOrder=>Lex];
i7 : F = QQ[a..d,MonomialSize=>8,MonomialOrder=>Lex];