How does Macaulay2 represent polynomials?

[Taylor Ball]

This is a CS question: what data structure does Macaulay2 use to encode polynomials and perform polynomial arithmetic?

E.g., Maple uses DAGs, Singular uses monomial sorted lists, MAGMA uses hashmaps...

Does the data structure depend on the coefficient ring, monomial ordering, degree of the polynomials, or sparsity of the polynomials?

Finally, why use this (these) data structure(s) over others?

Best,

Taylor Ball

[mike stillman]

Dear Taylor,

The main data structure for polynomials is a linked list of terms (coefficient and monomial), sorted in decreasing order with respect to the monomial order, and with 0 elements not represented.  There are variants on this, but for computing Groebner bases this  is (or, appears to be the) the most useful version.  Sometimes polynomials are stored as 2 vectors: an array of coefficient elements, and an array of monomials.  This often has better cache behavior, and I plan on changing all uses of linked lists inside Groebner bases and resolutions to this structure (Some have been changed already: including for the "minimalBetti" free resolutions, for noncommutative polynomials, and in the mathicgb Groebner implementations).

For operations not involving Groebner bases, the hash table representation is often pretty good, and is used for example at top level in computations in the package NCAlgebras.  There are also heap based structures, which are are used during multiplication of polynomials.  These are not so good for Groebner computations, it appears, as one really wants an operation to find the lead monomial.

In Macaulay2, except for univariate polynomials (and even mostly for univariate polynomials), all polynomials are considered as sparse sums of monomials.  Truly huge exponents are not allowed though, currently.

Does this answer any of your questions?

Best,

Mike

[Taylor Ball]

Hello,

That was very helpful! But it also spawned some follow-up questions:

1. "The main data structure for polynomials is a linked list of terms (coefficient and monomial)"

Is this choice of data structure due to the "sparse sums of monomials" assumption? 

2. " an array of coefficient elements, and an array of monomials"

Do these arrays only store the monomials with nonzero coefficients? If so, that seems like it could complicate multiplication. If not, that seems like there's a lot of zeros with the  "sparse sums of monomials" assumption.

3. "There are also heap based structures, which are are used during multiplication of polynomials."

Does this mean Macaulay2 converts a polynomial with a linked list/two vector representation into a different heap-based representation for faster multiplication? 

4. Since all this discussion might be getting into the weeds too much, do you have any references? Specifically, I'm interested in any papers discussing the data structures and their polynomial arithmetic algorithms that Macaulay2 is based on.

This helps a lot! I wasn't sure where to find these data structures/polynomial arithmetic algorithms in the source code.

Best,
Taylor Ball

--
You received this message because you are subscribed to the Google Groups "Macaulay2" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaulay2+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/macaulay2/97bba64b-71fc-439a-bcbc-1e56be564366n%40googlegroups.com.

[Anton]

Hi Taylor,

You may be interested in joining M2internals: 

https://github.com/Macaulay2/M2/wiki/Internals%3A-Meeting-Notes

We have a slack space devoted to these, run regular meetings (one of them today), etc.

Please email Mike and/or me if interested.

--Anton