# Singular

 Page 1 of 1 [ 2 posts ]
 Print view | E-mail friend Previous topic | Next topic
Author Message
 Post subject: linear dependence of polynomials + the function "eliminate"Posted: Tue May 31, 2016 6:58 pm

Joined: Sun Nov 15, 2015 12:13 am
Posts: 20
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.

Top

 Post subject: Re: linear dependence of multivariate polynomialsPosted: Sat Jun 11, 2016 5:15 pm

Joined: Sun Nov 15, 2015 12:13 am
Posts: 20
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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

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

 It is currently Wed Sep 19, 2018 11:00 pm
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group