monomials methods for multivariate polynomial rings?

108 views
Skip to first unread message

John Cremona

unread,
Mar 24, 2013, 10:03:06 AM3/24/13
to sage-a...@googlegroups.com
In my current work I am often needing a list of monomials in a
polynomial ring, typically:

RXYZ.<X,Y,Z> = QQ[]
mons4 = ((X+Y+Z)^4).monomials()

to get the list of 15 monomials of degree 4 in X,Y,Z. Is there a
better way, and if not, should there be? Something like
RXYZ.monomials(degree=4)?

John

David Roe

unread,
Mar 24, 2013, 11:52:41 AM3/24/13
to sage-a...@googlegroups.com
I don't see an easier way; RXYZ.monomials(degree=4) sounds good to me.
David



John

--
You received this message because you are subscribed to the Google Groups "sage-algebra" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-algebra...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.



John Cremona

unread,
Mar 24, 2013, 12:43:25 PM3/24/13
to sage-a...@googlegroups.com
On 24 March 2013 15:52, David Roe <roed...@gmail.com> wrote:
> I don't see an easier way; RXYZ.monomials(degree=4) sounds good to me.
> David

--but surely there's a better implementation which goes straight to
the dict for of the polynomials? I found that there is a top-level
general fcuntion monomials():

sage: RXYZ.<X,Y,Z> = QQ[]
sage: [m for m in monomials(RXYZ.gens(),[4]*3) if m.degree()==3]
[Z^3, Y*Z^2, Y^2*Z, Y^3, X*Z^2, X*Y*Z, X*Y^2, X^2*Z, X^2*Y, X^3]

which allows to specify a maximum degree for each variable but has no
flag for total degree / homogeneity. And I spent ages browsing all
the combinatorial variations on Partitions but they do not allow 0
parts.

For higher degree, expanding (X+Y+Z)^d just to extract its monomials
would be inefficient. So far I have needed this for d=39.

John

Nils Bruin

unread,
Mar 24, 2013, 12:52:07 PM3/24/13
to sage-algebra
On Mar 24, 9:43 am, John Cremona <john.crem...@gmail.com> wrote:
> For higher degree, expanding (X+Y+Z)^d just to extract its monomials
> would be inefficient.  So far I have needed this for d=39.

I ended up using

def monomials_of_degree(R,d):
n=R.ngens()
return [R({tuple(v):1}) for v in IntegerVectors(d,n)]

Since IntegerVectors produces a lazy iterable, you can make
monomials_of_degree also lazy if you want.

John Cremona

unread,
Mar 24, 2013, 1:33:37 PM3/24/13
to sage-a...@googlegroups.com
Brilliant! I did not know of the IntegerVectors class, it does what I
was trying for.

My next issue is working out why it takes so long to evaluate
monomials in 3 variables on a triple of power series of precision 200
over a cubic field...

Nicolas M. Thiery

unread,
Mar 24, 2013, 4:10:55 PM3/24/13
to sage-a...@googlegroups.com
Hi John!
A good start is:

sage: IntegerVectors(4,3).list()
[[4, 0, 0],
[3, 1, 0],
[3, 0, 1],
[2, 2, 0],
[2, 1, 1],
[2, 0, 2],
[1, 3, 0],
[1, 2, 1],
[1, 1, 2],
[1, 0, 3],
[0, 4, 0],
[0, 3, 1],
[0, 2, 2],
[0, 1, 3],
[0, 0, 4]]

With that, we would want to do something like:

sage: [ RXYZ.monomial(v) for v in IntegerVectors(4,3)]

In general, we would want Sage's polynomials (and FreeModule's for
that matter) to implement the ModulesWithBasis protocol, with fast
implementations of all the trivial-yet-life-saving constructors /
accessors that we have in CombinatorialFreeModule.

Oh, and IntegerVectors and its underlying kernel IntegerListsLex,
should be optimized too ...

For immediate purposes: I think I remember seeing some way to
construct a polynomial for monomials in exponent-vector notation ...

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

Nicolas M. Thiery

unread,
Mar 24, 2013, 4:16:17 PM3/24/13
to sage-a...@googlegroups.com
On Sun, Mar 24, 2013 at 09:52:07AM -0700, Nils Bruin wrote:
> I ended up using
>
> def monomials_of_degree(R,d):
> n=R.ngens()
> return [R({tuple(v):1}) for v in IntegerVectors(d,n)]
>
> Since IntegerVectors produces a lazy iterable, you can make
> monomials_of_degree also lazy if you want.

:-)

Thanks for being quicker than me *and* being explicit about the
appropriate syntax to construct polymonomials from exponent-vector
notations!

From John's comments, it seems we should add some cross-links between
Partitions, IntegerVectors and the like.

John Cremona

unread,
Mar 24, 2013, 4:20:38 PM3/24/13
to sage-a...@googlegroups.com
On 24 March 2013 20:16, Nicolas M. Thiery <Nicolas...@u-psud.fr> wrote:
> On Sun, Mar 24, 2013 at 09:52:07AM -0700, Nils Bruin wrote:
>> I ended up using
>>
>> def monomials_of_degree(R,d):
>> n=R.ngens()
>> return [R({tuple(v):1}) for v in IntegerVectors(d,n)]
>>
>> Since IntegerVectors produces a lazy iterable, you can make
>> monomials_of_degree also lazy if you want.
>
> :-)
>
> Thanks for being quicker than me *and* being explicit about the
> appropriate syntax to construct polymonomials from exponent-vector
> notations!
>
> From John's comments, it seems we should add some cross-links between
> Partitions, IntegerVectors and the like.

Yes, that would be helpful. Finding Partitions was not hard but I had
literally never heard the term "Composition" before (not that it was
what I needed anyway).

Thanks,

John

>
> Cheers,
> Nicolas
> --
> Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
> http://Nicolas.Thiery.name/
Reply all
Reply to author
Forward
0 new messages