ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 11 Apr 2019 22:44:25 +0200Quicker expansion of multivariate polynomialshttps://ask.sagemath.org/question/46098/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.
Thanks!Thu, 11 Apr 2019 19:41:03 +0200https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/Answer by tmonteil for <p>Hi everyone,</p>
<p>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 <code>build_polynomial</code> 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:</p>
<pre><code>(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)
</code></pre>
<p>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.</p>
<p>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 <code>expand</code> function, then using the <code>coefficient</code> function with the specific terms as arguments. </p>
<p>My issue is that as the polynomial grows, the completion time of the <code>expand</code> function also grows quite rapidly. For example, at medium-to-large complexity, the polynomial can take days to be expanded. </p>
<p>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.</p>
<p>Thanks!</p>
https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?answer=46099#post-id-46099You 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.
Thu, 11 Apr 2019 20:42:53 +0200https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?answer=46099#post-id-46099Comment by trenzafeeds for <p>You should provide the code of the <code>build_polynomial</code> function. </p>
<p>What is the degree of the polynomials ?</p>
<p>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.</p>
<p>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.</p>
https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?comment=46101#post-id-46101You'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!Thu, 11 Apr 2019 21:29:25 +0200https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?comment=46101#post-id-46101Comment by tmonteil for <p>You should provide the code of the <code>build_polynomial</code> function. </p>
<p>What is the degree of the polynomials ?</p>
<p>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.</p>
<p>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.</p>
https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?comment=46103#post-id-46103OK you decide. But you can also post a simplified version of the code that shows the issue.Thu, 11 Apr 2019 22:44:25 +0200https://ask.sagemath.org/question/46098/quicker-expansion-of-multivariate-polynomials/?comment=46103#post-id-46103