ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 18 Dec 2018 21:26:42 -0600Roots of multivariable polynomials with respect to one variable?http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/This question was previously titled "Finding residues of a huge multivariable rational function."
From my understanding, when computing with huge rational functions, we shouldn't use symbolic variables. However, I don't see how to find roots and residues without symbolic variables. Here is a small scale example of the issue. I have a rational function that looks like below:
$f(u_1,x_1,u_2,x_2,u_3,x_3) = \frac{1}{{\left(u_{1} u_{2} u_{3} - x_{1} x_{2} x_{3}\right)} {\left(u_{1} u_{2} u_{3} - 1\right)} {\left(u_{1} u_{2} - x_{1} x_{2}\right)} {\left(u_{1} u_{2} - 1\right)} {\left(u_{1} - x_{1}\right)} {\left(u_{1} - 1\right)}}$
First I want to solve for $u_1$ in the denominator and find those roots (poles) that have $x_1$ as below.
Then I will loop through the roots and compute the residue of $f$ w.r.t. $u_1$ at those poles.
u1,u2,u3,x1,x2,x3 = var('u1,u2,u3,x1,x2,x3') #symbolic variables
f=1/((u1*u2*u3 - x1*x2*x3)*(u1*u2*u3 - 1)*(u1*u2 - x1*x2)*(u1*u2 - 1)*(u1 - x1)*(u1 - 1))
fden=f.denominator() #denominator of f
list1=fden.roots(u1) #poles of u1
[root for (root, multiplicity) in list1] #list of roots
The output is
[x1*x2*x3/(u2*u3), x1*x2/u2, x1, 1/(u2*u3), 1/u2, 1]
Then we choose those roots that have $x1$
poles1 = [x1*x2*x3/(u2*u3), x1*x2/u2, x1] #choose those that have x1
Finally, we find the residue of $f$ w.r.t $u1$ of the rational function at the poles containing $x1.$
ans1=0
for ff in poles1:
tmp=f.residue(u1==ff)
ans1+=tmp #ans1 is the residue of f w.r.t u1 at all the poles containing x1
ans1
The output is then
1/((u2*u3*x1 - x1*x2*x3)*(u2*u3*x1 - 1)*(u2*x1 - x1*x2)*(u2*x1 - 1)*(x1 - 1)) - 1/((u3*x1*x2 - x1*x2*x3)*(u3*x1*x2 - 1)* (x1*x2 - 1)*u2*(x1 - x1*x2/u2)*(x1*x2/u2 - 1)) + 1/((x1*x2*x3 - 1)*(x1*x2 - x1*x2*x3/u3)*(x1*x2*x3/u3 - 1)*u2*u3*(x1 x1*x2*x3/(u2*u3))*(x1*x2*x3/(u2*u3) - 1))
Then I replace $f$ with $ans1$ to continue to do the same process w.r.t $u2$ and poles containing $x2$ and finally w.r.t $u3$ and poles containing $x3.$ However, this consumes about 800GB of memory on an HPC when I feed it a larger rational function.
Is there a way to find
1. roots of multivariable polynomials with respect to one variable?
2. residue of a rational function avoiding symbolic variables?
Both .roots() and .residue() are not defined for rational functions that are not defined in terms of symbolic variables.Sun, 16 Dec 2018 16:32:23 -0600http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/Answer by rburing for <p>This question was previously titled "Finding residues of a huge multivariable rational function."</p>
<p>From my understanding, when computing with huge rational functions, we shouldn't use symbolic variables. However, I don't see how to find roots and residues without symbolic variables. Here is a small scale example of the issue. I have a rational function that looks like below:</p>
<p>$f(u_1,x_1,u_2,x_2,u_3,x_3) = \frac{1}{{\left(u_{1} u_{2} u_{3} - x_{1} x_{2} x_{3}\right)} {\left(u_{1} u_{2} u_{3} - 1\right)} {\left(u_{1} u_{2} - x_{1} x_{2}\right)} {\left(u_{1} u_{2} - 1\right)} {\left(u_{1} - x_{1}\right)} {\left(u_{1} - 1\right)}}$</p>
<p>First I want to solve for $u_1$ in the denominator and find those roots (poles) that have $x_1$ as below. </p>
<p>Then I will loop through the roots and compute the residue of $f$ w.r.t. $u_1$ at those poles. </p>
<pre><code>u1,u2,u3,x1,x2,x3 = var('u1,u2,u3,x1,x2,x3') #symbolic variables
f=1/((u1*u2*u3 - x1*x2*x3)*(u1*u2*u3 - 1)*(u1*u2 - x1*x2)*(u1*u2 - 1)*(u1 - x1)*(u1 - 1))
fden=f.denominator() #denominator of f
list1=fden.roots(u1) #poles of u1
[root for (root, multiplicity) in list1] #list of roots
</code></pre>
<p>The output is </p>
<pre><code>[x1*x2*x3/(u2*u3), x1*x2/u2, x1, 1/(u2*u3), 1/u2, 1]
</code></pre>
<p>Then we choose those roots that have $x1$</p>
<pre><code>poles1 = [x1*x2*x3/(u2*u3), x1*x2/u2, x1] #choose those that have x1
</code></pre>
<p>Finally, we find the residue of $f$ w.r.t $u1$ of the rational function at the poles containing $x1.$</p>
<pre><code>ans1=0
for ff in poles1:
tmp=f.residue(u1==ff)
ans1+=tmp #ans1 is the residue of f w.r.t u1 at all the poles containing x1
ans1
</code></pre>
<p>The output is then </p>
<pre><code>1/((u2*u3*x1 - x1*x2*x3)*(u2*u3*x1 - 1)*(u2*x1 - x1*x2)*(u2*x1 - 1)*(x1 - 1)) - 1/((u3*x1*x2 - x1*x2*x3)*(u3*x1*x2 - 1)* (x1*x2 - 1)*u2*(x1 - x1*x2/u2)*(x1*x2/u2 - 1)) + 1/((x1*x2*x3 - 1)*(x1*x2 - x1*x2*x3/u3)*(x1*x2*x3/u3 - 1)*u2*u3*(x1 x1*x2*x3/(u2*u3))*(x1*x2*x3/(u2*u3) - 1))
</code></pre>
<p>Then I replace $f$ with $ans1$ to continue to do the same process w.r.t $u2$ and poles containing $x2$ and finally w.r.t $u3$ and poles containing $x3.$ However, this consumes about 800GB of memory on an HPC when I feed it a larger rational function. </p>
<p>Is there a way to find </p>
<ol>
<li><p>roots of multivariable polynomials with respect to one variable?</p></li>
<li><p>residue of a rational function avoiding symbolic variables? </p></li>
</ol>
<p>Both .roots() and .residue() are not defined for rational functions that are not defined in terms of symbolic variables.</p>
http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?answer=44694#post-id-44694Instead of working with symbolic variables you can work in (fraction fields of) polynomial rings, as follows.
R.<u1,u2,u3,x1,x2,x3> = PolynomialRing(QQ)
f=1/((u1*u2*u3 - x1*x2*x3)*(u1*u2*u3 - 1)*(u1*u2 - x1*x2)*(u1*u2 - 1)*(u1 - x1)*(u1 - 1))
fden=f.denominator() #denominator of f
Division of polynomials automatically yields elements of the fraction field.
You can re-interpret a multivariate polynomial as being a polynomial in one variable, putting the remaining variables in the base ring:
sage: f_u1 = fden.polynomial(u1)
sage: f_u1.parent()
Univariate Polynomial Ring in u1 over Multivariate Polynomial Ring in u2, u3, x1, x2, x3 over Rational Field
But now the base ring is not a field, so it is hard to find roots there. But we can search for roots in the fraction field of the base ring:
sage: f_u1.roots(f_u1.base_ring().fraction_field())
[(1, 1),
(x1, 1),
(1/u2, 1),
(x1*x2/u2, 1),
(1/(u2*u3), 1),
(x1*x2*x3/(u2*u3), 1)]
This should be much more efficient than using symbolic variables. Let me know if this works for you.
As for residues, indeed they are not implemented for rational functions. But you can easily implement the formulas yourself. For example, the residue of $p(z)/q(z)$ at a *simple* pole $z=r$ is $p(r)/q'(r)$.
**Edit**: In the second step, the roots of the denominator with respect to $u_2$ may live in a larger field (when there are irreducible factors of degree $\gt 1$ w.r.t $u_2$ in the denominator), so you have to add these to your field when searching for roots. Basically you want the splitting field of the denominator. Since the variables are still undetermined it seems you would have to create a function field (extension).Mon, 17 Dec 2018 11:07:42 -0600http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?answer=44694#post-id-44694Comment by Holden for <p>Instead of working with symbolic variables you can work in (fraction fields of) polynomial rings, as follows.</p>
<pre><code>R.<u1,u2,u3,x1,x2,x3> = PolynomialRing(QQ)
f=1/((u1*u2*u3 - x1*x2*x3)*(u1*u2*u3 - 1)*(u1*u2 - x1*x2)*(u1*u2 - 1)*(u1 - x1)*(u1 - 1))
fden=f.denominator() #denominator of f
</code></pre>
<p>Division of polynomials automatically yields elements of the fraction field.</p>
<p>You can re-interpret a multivariate polynomial as being a polynomial in one variable, putting the remaining variables in the base ring:</p>
<pre><code>sage: f_u1 = fden.polynomial(u1)
sage: f_u1.parent()
Univariate Polynomial Ring in u1 over Multivariate Polynomial Ring in u2, u3, x1, x2, x3 over Rational Field
</code></pre>
<p>But now the base ring is not a field, so it is hard to find roots there. But we can search for roots in the fraction field of the base ring:</p>
<pre><code>sage: f_u1.roots(f_u1.base_ring().fraction_field())
[(1, 1),
(x1, 1),
(1/u2, 1),
(x1*x2/u2, 1),
(1/(u2*u3), 1),
(x1*x2*x3/(u2*u3), 1)]
</code></pre>
<p>This should be much more efficient than using symbolic variables. Let me know if this works for you.</p>
<p>As for residues, indeed they are not implemented for rational functions. But you can easily implement the formulas yourself. For example, the residue of $p(z)/q(z)$ at a <em>simple</em> pole $z=r$ is $p(r)/q'(r)$.</p>
<p><strong>Edit</strong>: In the second step, the roots of the denominator with respect to $u_2$ may live in a larger field (when there are irreducible factors of degree $\gt 1$ w.r.t $u_2$ in the denominator), so you have to add these to your field when searching for roots. Basically you want the splitting field of the denominator. Since the variables are still undetermined it seems you would have to create a function field (extension).</p>
http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?comment=44711#post-id-44711I wrote down a one liner to define residue
def Res(f,var, pole, multi):
return (1/factorial(multi-1))*limit( diff((var-pole)^multi*f ,var,multi-1), var=pole)
but the limiting part takes a huge amount of memory for a moderately big rational function in several variables. I am looking for other methods now.Tue, 18 Dec 2018 21:26:42 -0600http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?comment=44711#post-id-44711Comment by Holden for <p>Instead of working with symbolic variables you can work in (fraction fields of) polynomial rings, as follows.</p>
<pre><code>R.<u1,u2,u3,x1,x2,x3> = PolynomialRing(QQ)
f=1/((u1*u2*u3 - x1*x2*x3)*(u1*u2*u3 - 1)*(u1*u2 - x1*x2)*(u1*u2 - 1)*(u1 - x1)*(u1 - 1))
fden=f.denominator() #denominator of f
</code></pre>
<p>Division of polynomials automatically yields elements of the fraction field.</p>
<p>You can re-interpret a multivariate polynomial as being a polynomial in one variable, putting the remaining variables in the base ring:</p>
<pre><code>sage: f_u1 = fden.polynomial(u1)
sage: f_u1.parent()
Univariate Polynomial Ring in u1 over Multivariate Polynomial Ring in u2, u3, x1, x2, x3 over Rational Field
</code></pre>
<p>But now the base ring is not a field, so it is hard to find roots there. But we can search for roots in the fraction field of the base ring:</p>
<pre><code>sage: f_u1.roots(f_u1.base_ring().fraction_field())
[(1, 1),
(x1, 1),
(1/u2, 1),
(x1*x2/u2, 1),
(1/(u2*u3), 1),
(x1*x2*x3/(u2*u3), 1)]
</code></pre>
<p>This should be much more efficient than using symbolic variables. Let me know if this works for you.</p>
<p>As for residues, indeed they are not implemented for rational functions. But you can easily implement the formulas yourself. For example, the residue of $p(z)/q(z)$ at a <em>simple</em> pole $z=r$ is $p(r)/q'(r)$.</p>
<p><strong>Edit</strong>: In the second step, the roots of the denominator with respect to $u_2$ may live in a larger field (when there are irreducible factors of degree $\gt 1$ w.r.t $u_2$ in the denominator), so you have to add these to your field when searching for roots. Basically you want the splitting field of the denominator. Since the variables are still undetermined it seems you would have to create a function field (extension).</p>
http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?comment=44697#post-id-44697Thank you @rburing. Yes, the roots are instantaneous. I am working on the residues now. I will let you know if I have further questions.Mon, 17 Dec 2018 13:36:26 -0600http://ask.sagemath.org/question/44686/roots-of-multivariable-polynomials-with-respect-to-one-variable/?comment=44697#post-id-44697