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.Sun, 26 Jan 2020 06:21:45 +0100Computing a Basis of Polynomials (As a Vector Space)https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/Hello everyone! I'm fairly new to sage, so this is probably super simple but I can't quite figure it out.
So $S_n$ acts on the multivariate polynomial ring $M = \mathbb{C} [x_1,x_2,...,x_n,y_1,y_2,...y_n]$ by simply $\sigma*x_i = x_{\sigma(i)}$ (and same for the $y_i$'s). This turns $M$ into a $S_n$-Module, and by extension of linearity a module of the group ring $\mathbb{C}S_n$.
This isn't the important part however; I'm studying submodules of the thing above, and the problem right now is I have a bunch of polynomials (hundreds) of considerable length, but I want a minimal generating set (only additively). Is there a command that does this quickly without having to convert everything into a giant $(n+1)^{n+1}$-dimensional vector space?
Thanks so much in advance!Mon, 20 Jan 2020 06:23:50 +0100https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/Comment by RaymondChou for <p>Hello everyone! I'm fairly new to sage, so this is probably super simple but I can't quite figure it out.</p>
<p>So $S_n$ acts on the multivariate polynomial ring $M = \mathbb{C} [x_1,x_2,...,x_n,y_1,y_2,...y_n]$ by simply $\sigma*x_i = x_{\sigma(i)}$ (and same for the $y_i$'s). This turns $M$ into a $S_n$-Module, and by extension of linearity a module of the group ring $\mathbb{C}S_n$. </p>
<p>This isn't the important part however; I'm studying submodules of the thing above, and the problem right now is I have a bunch of polynomials (hundreds) of considerable length, but I want a minimal generating set (only additively). Is there a command that does this quickly without having to convert everything into a giant $(n+1)^{n+1}$-dimensional vector space?</p>
<p>Thanks so much in advance!</p>
https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?comment=49635#post-id-49635I ended up spending the weekend implementing it (with my caveman programming skills), so it's not the most elegant thing in the world...but if anyone wants to use what I have, please feel free to contact me!Wed, 22 Jan 2020 00:44:17 +0100https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?comment=49635#post-id-49635Answer by mwageringel for <p>Hello everyone! I'm fairly new to sage, so this is probably super simple but I can't quite figure it out.</p>
<p>So $S_n$ acts on the multivariate polynomial ring $M = \mathbb{C} [x_1,x_2,...,x_n,y_1,y_2,...y_n]$ by simply $\sigma*x_i = x_{\sigma(i)}$ (and same for the $y_i$'s). This turns $M$ into a $S_n$-Module, and by extension of linearity a module of the group ring $\mathbb{C}S_n$. </p>
<p>This isn't the important part however; I'm studying submodules of the thing above, and the problem right now is I have a bunch of polynomials (hundreds) of considerable length, but I want a minimal generating set (only additively). Is there a command that does this quickly without having to convert everything into a giant $(n+1)^{n+1}$-dimensional vector space?</p>
<p>Thanks so much in advance!</p>
https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?answer=49669#post-id-49669One way to do this in Sage is to compute an echolonization of the coefficient matrix of the polynomials:
sage: R.<x1,x2,y1,y2> = QQ[]
sage: s = Sequence([x1^2, x2^2, x1^2+x1*x2+x2^2, x1^2-x1*x2, x1*y1+x1^3, y1^2+y1*y2+y2^2])
sage: C, m = s.coefficient_matrix(); C, m
(
[ x1^3]
[ x1^2]
[ 0 1 0 0 0 0 0 0] [x1*x2]
[ 0 0 0 1 0 0 0 0] [ x2^2]
[ 0 1 1 1 0 0 0 0] [x1*y1]
[ 0 1 -1 0 0 0 0 0] [ y1^2]
[ 1 0 0 0 1 0 0 0] [y1*y2]
[ 0 0 0 0 0 1 1 1], [ y2^2]
)
sage: B = C.row_space().basis_matrix(); B
[1 0 0 0 1 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1]
sage: (B * m).list()
[x1^3 + x1*y1, x1^2, x1*x2, x2^2, y1^2 + y1*y2 + y2^2]
This does convert everything to a large vector space however, but it is only as large as necessary to encode all the monomials that occur in the sequence of polynomials.
Note that this assumes you are working over an exact field such as `QQ`. Over an inexact field such as ℂ, this problem is more delicate. In that case, I would start by looking at the singular value decomposition of `C`, but the quality of the result largly depends on the input polynomials:
U, D, V = matrix(CDF, C, sparse=False).SVD()Fri, 24 Jan 2020 18:56:42 +0100https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?answer=49669#post-id-49669Comment by RaymondChou for <p>One way to do this in Sage is to compute an echolonization of the coefficient matrix of the polynomials:</p>
<pre><code>sage: R.<x1,x2,y1,y2> = QQ[]
sage: s = Sequence([x1^2, x2^2, x1^2+x1*x2+x2^2, x1^2-x1*x2, x1*y1+x1^3, y1^2+y1*y2+y2^2])
sage: C, m = s.coefficient_matrix(); C, m
(
[ x1^3]
[ x1^2]
[ 0 1 0 0 0 0 0 0] [x1*x2]
[ 0 0 0 1 0 0 0 0] [ x2^2]
[ 0 1 1 1 0 0 0 0] [x1*y1]
[ 0 1 -1 0 0 0 0 0] [ y1^2]
[ 1 0 0 0 1 0 0 0] [y1*y2]
[ 0 0 0 0 0 1 1 1], [ y2^2]
)
sage: B = C.row_space().basis_matrix(); B
[1 0 0 0 1 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1]
sage: (B * m).list()
[x1^3 + x1*y1, x1^2, x1*x2, x2^2, y1^2 + y1*y2 + y2^2]
</code></pre>
<p>This does convert everything to a large vector space however, but it is only as large as necessary to encode all the monomials that occur in the sequence of polynomials.</p>
<p>Note that this assumes you are working over an exact field such as <code>QQ</code>. Over an inexact field such as ℂ, this problem is more delicate. In that case, I would start by looking at the singular value decomposition of <code>C</code>, but the quality of the result largly depends on the input polynomials:</p>
<pre><code>U, D, V = matrix(CDF, C, sparse=False).SVD()
</code></pre>
https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?comment=49680#post-id-49680Thank you so much!Sun, 26 Jan 2020 06:21:45 +0100https://ask.sagemath.org/question/49610/computing-a-basis-of-polynomials-as-a-vector-space/?comment=49680#post-id-49680