Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Quicker expansion of multivariate polynomials

Hi everyone,

I'm working on a project that involves first generating polynomials, then checking to see if certain terms exist within them. Essentially, I have a function build_polynomial that builds polynomials in un-expanded form according to a certain set of specifications. The polynomials produced by this function usually look something like this:

(x1 - x2 - x3 + y1 - y2 + y3 - y4)*(x1 - x2)*(x1 - x3)*(x1 + y1 - y2)*(x2 + x3 - y1 + y2 - y3 + y4)*(x2 + x3 + y2 - y3)*(x2 + x3 - y3 + y4)*(x2 + x3)*(x2 - x3)*(x2 + y2 - y3)*(y1 - y2)*(y1 - y3)*(y1 - y4)*(y2 - y3)*(y2 - y4)*(y3 - y4)

This is a particularly small example, the polynomials expand quite rapidly as the problem grows in size, but this example should give an idea of generally what they look like.

Next, my program must check too see if specific terms exist in the expanded form of the polynomial. Currently, I do this by first expanding the polynomial with the Sage expand function, then using the coefficient function with the specific terms as arguments.

My issue is that as the polynomial grows, the completion time of the expand function also grows quite rapidly. For example, at medium-to-large complexity, the polynomial can take days to be expanded.

Is there any way around this? Possibly a more efficient function that anybody knows of? I know that Sage is not really the best option for large computations like this, but I'm looking for a way to at least slightly improve performance while I research a longer-term solution.