Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Largest monomial subideal of an polynomial ideal
PostPosted: Fri Feb 04, 2011 1:53 pm 

Joined: Wed Feb 02, 2011 11:36 am
Posts: 2
Hi,
given a polynomial ideal, is there a function that gives me the generators of the largest monomial subideal?
Thanks!


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Largest monomial subideal of an polynomial ideal
PostPosted: Wed Feb 09, 2011 4:26 pm 

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 108
Location: Germany, Münster
What do you intend to get?

Supposed I = <x^2+y, xy, x^2, z+y>

then the result should be <xy, x^2> ?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Largest monomial subideal of an polynomial ideal
PostPosted: Fri Feb 11, 2011 2:43 pm 

Joined: Wed Feb 02, 2011 11:36 am
Posts: 2
gorzel wrote:
What do you intend to get?

Supposed I = <x^2+y, xy, x^2, z+y>

then the result should be <xy, x^2> ?


The largest monomial ideal in RR[x,y,z] which is contained in I=<x^2+y,xy,x^2,z+y> is J=<x^2,y,z>.
It can be calculated by Algorithm 4.4.2 of the book "Groebner deformations of hypergeometric differential equations" of Saito, Sturmfels and Takayama, which computes a multi-homogenization H of I (w.r.t. new variables u,v,w) and a reduced GB of the saturation ideal H : <u,v,w>.


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Largest monomial subideal of an polynomial ideal
PostPosted: Thu Mar 03, 2011 1:56 pm 

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 108
Location: Germany, Münster
By the reference, your question became clear.
There has not been a command yet.
Did you manage to implement it?

Multi-homogenization may be a bit tricky, so here is an proc.

Note that the library elim.lib has to be loaded.
Code:
proc monomid(ideal I)
"USAGE: monomid(I); I ideal 
RETURN: ideal, the largest monomial subideal in I
NOTE: implements Algorithm 4.4.2
        Saito, Sturmfels, Takayama,
        Groebner Deformations of Hypergeometric Differential Equations
EXAMPLE: example monomid; shows an example
"
{
  def d = basering;
  int n = nvars(basering);
  int i,j,k;
   
  intvec v,w;
 
  // step 0 extend ring

  list rl = ringlist(d);
  for (i=1;i<=n;i++)
  {
    rl[2]= insert(rl[2],"@u("+string(i) +")",n+i-1);
  }
  def rnew = ring(rl);
  setring rnew;
  poly g,h;
  ideal I = fetch(d,I);
 
  // step 1 multi-homogenize
   
  for (i=1;i<=ncols(I);i++)  // each ideal entry
  {
    h = I[i];
    v = 0:2*n;
   
    for (k=1;k<=n;k++)   // determine multidegree
    {
      v[k] = 1;
      w[k] = deg(h,v);   // deg w.r.t. e_k
      v = 0:2*n;
    }
    // w is the multi-degree
   
    for(j=1;j<=size(h);j++)    // each term
    {
      v = leadexp(h[j]);
      v = 0:n,intvec(w[1..n])-intvec(v[1..n]);  // exponent vector
      g = g + h[j]*monomial(v);
    }
    I[i] = g;
  }
  // step 2 saturated quotient

  option(redSB);
  h = 1;
  for (i=1;i<=n;i++) { h = h * var(n+i);}
  I = sat(I,h)[1];
 
  // step 3 select monomials
  ideal J;
  j=0;
 
  for (i=1;i<=ncols(I);i++)
  {
    if (size(I[i])==1 and deg(I[i])>0)
    {
      j++;
      J[j]=I[i];
    }
  }
  setring d;
  ideal J = fetch(rnew,J);
return(J);
}


Two examples:
Code:
> LIB "elim.lib";
> ring r=0,(x,y,z),dp;

> // The example in Saito' et al. book on p. 176
>  ideal J = x+y+z,x2+y2+z2,x3+y3+z3;
> momomid(J);
_[1]=z3
_[2]=xyz
_[3]=y3
_[4]=x3
_[5]=y2z2
_[6]=x2z2
_[7]=x2y2

> // The example discussed in this forum:
> ideal I = x^2+y, xy, x^2, z+y;
> monomid(I);
_[1]=z
_[2]=y
_[3]=x2


which shows that your answer is correct.
-----------------

Ch. Gorzel


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Fri May 13, 2022 10:56 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group