Ask Your Question

Quicker expansion of multivariate polynomials

asked 2019-04-11 19:41:03 +0200

trenzafeeds gravatar image

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.


edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2019-04-11 20:42:53 +0200

tmonteil gravatar image

You should provide the code of the build_polynomial function.

What is the degree of the polynomials ?

My understanding is that your polynomials are symbolic expressions, not genuine polynomials, which would explain part of the slowness. But it is hard to advise something interesting without more details.

Also, in very high degree, one could imagine to answer your questions from the list of factors without having to build a polynomial by multipliying the factors. Having the factors is a rich information, that might be sad to lose by expanding the product.

edit flag offensive delete link more


You're completely right, they are symbolic expressions! I think I'll investigate the savings I can make by switching over to real polynomials before I go any further down the expansion rabbit hole. If I ask the question again I'll certainly post my code, but for now I think it's better left unposted, its a bit of a behemoth. Thanks!

trenzafeeds gravatar imagetrenzafeeds ( 2019-04-11 21:29:25 +0200 )edit

OK you decide. But you can also post a simplified version of the code that shows the issue.

tmonteil gravatar imagetmonteil ( 2019-04-11 22:44:25 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-04-11 19:41:03 +0200

Seen: 357 times

Last updated: Apr 11 '19