Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: linear dependence of polynomials + the function "eliminate"
PostPosted: Tue May 31, 2016 6:58 pm 

Joined: Sun Nov 15, 2015 12:13 am
Posts: 17
Hi all,
It is known that in the case of a zero-dimensional ideal, if we reduce successive powers of a variable, say
1,x,x^2,x^3, etc, until the remainders become linearly dependent, we can get a polynomial in x alone by using the same respective coefficients, which made the remainders linearly dependent.

simple illustrative example:

>ring r=0,(x,y),dp;
>ideal i=x3+y2-2,x+y;
>ideal g=std(i);
>g;
g[1]=x+y
g[2]=y3-y2+2

>poly r1=reduce(1,g);r1;
1
>poly rx=reduce(x,g);rx;
-y
>poly rx2=reduce(x2,g);rx2;
y2
>poly rx3=reduce(x3,g);rx3;
-y2+2

At this point, it can easily be seen that 1*rx3+1*rx2-2*rx1=0 and taking the same coefficients we get: 1*x3+1*x2-2*1=0 and so we have an equation in x alone (which is easily verified in this case).

-Now my question is, if this procedure has already been implemented in Singular?
-If not do you have any tips how to efficiently check for linear dependency of polynomials and access the coefficients, that make them linearly dependent?
I know that calculating a reduced Groebner basis with respect to lex order does the same, but it is sometimes not really efficient. The function eliminate does provide the same results too, and not only for zero-dimensional ideals. How exactly does eliminate work? Which algorithm is used? Does it calculates the intersection of an ideal with k[X(k+1), X(k+2), ...,X(n)] to eliminate the first k variables? If it does calculate the intersection, which exact algorithm is used? In general, I think that a few words about the algorithms in use in the inbuilt functions of Singular would be very helpful. Unfortunately, most of the time, the online manual doesn't contain information about the algorithms used!


Last edited by rambiz on Mon Jun 27, 2016 12:21 pm, edited 1 time in total.

Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: linear dependence of multivariate polynomials
PostPosted: Sat Jun 11, 2016 5:15 pm 

Joined: Sun Nov 15, 2015 12:13 am
Posts: 17
Hi all,
this is the code I could come up with. Please have a look, proof-read, and make possibly improvement suggestions.
Code:
LIB "matrix.lib";

ring r=0,(x,y),lp;

ideal i=x4+x2+xy3+2,x2+y2-1;

ideal g=std(i);
//option(redSB);
g;
dim(g);
vdim(g);

ideal B=kbase(g);
int   L=size(B);


matrix m[L][1];
matrix column[L][1];

int n=0;          //power of the ring variable for which we want to calculate the elimination ideal
int flag=1;       //flag is set to zero, when the reduced powers become linearly dependent
while(flag==1)
{

poly f=reduce(x^n,g);

for(int counter=1;counter<=L;counter=counter+1)
{
  column[counter,1]=jet(f/B[counter],0);
}

if (n==0)
    {m=column;}
else
     {m=concat(m,column);}

if (rank(m)<(n+1))
      {flag=0;}

n=n+1;

}

print(m);

///////////////////////////////////////////////////
option(noredefine);

int nc=ncols(m);

ring r2=0,(x(1..nc)),lp;    //number of variables must be the same as the number of columns of the matrix for which we want the reduced row echelon form

map f=r,x(1),x(2);
matrix m2=f(m);


print("m2=");print(m2);

int nr=nrows(m2);
int nc=ncols(m2);
int j;
int k;
for(j=1;j<=nr;j=j+1){for(k=1;k<=nc;k=k+1){m2[j,k]=m2[j,k]*x(k);}};
kill j;
kill k;
//print(m2);

matrix ONES[nc][1];
for(int j=1;j<=nc;j=j+1){ONES[j,1]=1;};
kill j;

ideal i=m2*ONES;
option(redSB);
ideal g=std(i);
option(redSB);
int L=size(g);
for(int j=1;j<=L;j=j+1) {g[j]=g[j]/leadcoef(g[j]);}
kill j;

matrix Output[L][nc];

int k;
for (int j=L;j>0;j=j-1){for (k=1;k<=nc;k=k+1){Output[j,k]=jet(g[L+1-j]/x(k),0);}};
kill j;
kill k;


print("Output=");print(Output);print("Output is the reduced row echelon form of matrix m");

setring r;

map phi=r2,x;
matrix rref=phi(Output);

print(rref);

poly EliminationIdeal=x^(nc-1);

for (int n=1;n<=(nc-1);n=n+1)
    {EliminationIdeal=EliminationIdeal+(-rref[n,nc])*x^(n-1);};
print(EliminationIdeal);


//ring r=0,(x,y),dp; ideal i=x3-yx+1,x2+y2-1;---->x6+x4+2x3-x2+1
//ring r=0,(x,y),dp; ideal i=x3-y2+xy,x+y-1; ---->x3-2x2+3x-1
//ring r=0,(x,y),lp; ideal i=x4+x2+xy3+2,x2+y2-1;---->x8-1/2x6+4x4+3/2x2+2


The last 3 lines are examples with the corresponding elimination ideal. I checked the answers manually and these solutions are right.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 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 Wed Dec 13, 2017 4:39 pm
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group