Back to Forum | View unanswered posts | View active topics



Post new topic Reply to topic  Page 1 of 1
  [ 3 posts ] 
  Print view | E-mail friend Previous topic | Next topic 
Author Message
BeniBela
 Post subject: Gröbner basis of polynomials with unknown coefficients
PostPosted: Thu May 19, 2016 6:25 pm 

Joined: Thu May 19, 2016 4:33 pm
Posts: 2
If you have polynomials of certain structure, with unknown coefficients, you can represent the coefficients with invariates, e.g. for a very simple polynomial in x: "x^2 + a x + b" , where we do not know the coefficients a and b.

What is best way to calculate a Gröbner basis of such polynomials in x, while not calculating one in a and b?

More concrete I have equation (polynomial) systems of this structure:

L1*L3*s13-L1*s14-L3*s23+s24
L1*L4*s14-L1*s15-L4*s24+s25
L2*L3*s23-L2*s24-L3*s33+s34
L2*L4*s24-L2*s25-L4*s34+s35
L3*L4*s34-L3*s35-L4*s44+s45

with L variables that are relevant and the s variables as placeholders.

Now I calculate a Gröbner Basis:

Code:
ring r = 0,(L1,L2,L3,L4,L5,L6,L7,L8,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),dp;
groebner(ideal(L1*L3*s13-L1*s14-L3*s23+s24, L1*L4*s14-L1*s15-L4*s24+s25, L2*L3*s23-L2*s24-L3*s33+s34, L2*L4*s24-L2*s25-L4*s34+s35, L3*L4*s34-L3*s35-L4*s44+s45));

_[1]=L3*L4*s34-L3*s35-L4*s44+s45
_[2]=s15*s24*s33-s14*s25*s33-s15*s23*s34+s13*s25*s34+s14*s23*s35-s13*s24*s35
_[3]=L2*L4*s24-L2*s25-L4*s34+s35
_[4]=L2*L3*s23-L2*s24-L3*s33+s34
_[5]=L1*L4*s14-L1*s15-L4*s24+s25
_[6]=L1*L3*s13-L1*s14-L3*s23+s24
_[7]=L2*L4*s23*s44-L2*s25*s34+L2*s24*s35-L4*s33*s44-L2*s23*s45+s33*s45
_[8]=L1*L4*s13*s44-L1*s15*s34+L1*s14*s35-L4*s23*s44-L1*s13*s45+s25*s34-s24*s35+s23*s45
_[9]=L3*s25*s33*s34-L3*s24*s33*s35-L4*s24*s33*s44+L4*s23*s34*s44-s25*s34^2+s24*s34*s35+s24*s33*s45-s23*s34*s45
_[10]=L3*s15*s33*s34-L3*s14*s33*s35-L4*s14*s33*s44+L4*s13*s34*s44-s15*s34^2+s14*s34*s35+s14*s33*s45-s13*s34*s45
_[11]=L2*s24*s25*s34-L2*s24^2*s35-L2*s23*s25*s44+L4*s24*s33*s44-L4*s23*s34*s44+L2*s23*s24*s45+s23*s35*s44-s24*s33*s45
_[12]=L2*L3*s25*s34-L2*L3*s24*s35-L2*s25*s44+L2*s24*s45+s35*s44-s34*s45
_[13]=L3*s15*s23*s34-L3*s13*s25*s34-L3*s14*s23*s35+L3*s13*s24*s35-L4*s14*s23*s44+L4*s13*s24*s44-s15*s24*s34+s14*s25*s34+s14*s23*s45-s13*s24*s45
_[14]=L1*s14*s15*s34-L1*s14^2*s35-L1*s13*s15*s44+L4*s14*s23*s44-L4*s13*s24*s44+L1*s13*s14*s45-s14*s25*s34+s14*s24*s35+s13*s25*s44-s14*s23*s45
_[15]=L1*L3*s15*s34-L1*L3*s14*s35-L3*s25*s34+L3*s24*s35-L1*s15*s44+L1*s14*s45+s25*s44-s24*s45
_[16]=L3*L4*s24*s33-L3*s25*s33-L4*s23*s44+s25*s34-s24*s35+s23*s45
_[17]=L3*L4*s14*s33-L3*s15*s33-L4*s13*s44+s15*s34-s14*s35+s13*s45
_[18]=L1*L2*s15*s24-L1*L2*s14*s25-L1*s15*s34+L1*s14*s35+s25*s34-s24*s35
_[19]=L1*L2*s15*s23-L1*L2*s13*s25-L1*s15*s33+L1*s13*s35+s25*s33-s23*s35
_[20]=L3*L4*s14*s23-L3*L4*s13*s24-L3*s15*s23+L3*s13*s25+s15*s24-s14*s25
_[21]=L1*L2*s14*s23-L1*L2*s13*s24-L1*s14*s33+L1*s13*s34+s24*s33-s23*s34
_[22]=L4^2*s24*s33*s44-L4^2*s23*s34*s44+L4*s25*s34^2-L4*s24*s34*s35-L4*s25*s33*s44+L4*s23*s35*s44-L4*s24*s33*s45+L4*s23*s34*s45-s25*s34*s35+s24*s35^2+s25*s33*s45-s23*s35*s45
_[23]=L4^2*s14*s33*s44-L4^2*s13*s34*s44+L4*s15*s34^2-L4*s14*s34*s35-L4*s15*s33*s44+L4*s13*s35*s44-L4*s14*s33*s45+L4*s13*s34*s45-s15*s34*s35+s14*s35^2+s15*s33*s45-s13*s35*s45
_[24]=L4^2*s14*s23*s44-L4^2*s13*s24*s44+L4*s15*s24*s34-L4*s14*s25*s34-L4*s15*s23*s44+L4*s13*s25*s44-L4*s14*s23*s45+L4*s13*s24*s45-s15*s24*s35+s14*s25*s35+s15*s23*s45-s13*s25*s45
_[25]=L1*L2*s14*s25*s34-L1*L2*s14*s24*s35-L1*L2*s13*s25*s44+L1*L2*s13*s24*s45+L4*s24*s33*s44-L4*s23*s34*s44+L1*s13*s35*s44-L1*s13*s34*s45-s24*s33*s45+s23*s34*s45
_[26]=L2*L4*s14*s25*s33+L2*L4*s15*s23*s34-L2*L4*s13*s25*s34-L2*L4*s14*s23*s35-L2*s15*s25*s33-L4*s15*s33*s34+L2*s13*s25*s35+L4*s13*s34*s35+s15*s33*s35-s13*s35^2
_[27]=L2*s14*s25^2*s33*s34+L2*s15*s23*s25*s34^2-L2*s13*s25^2*s34^2-L2*s14*s24*s25*s33*s35-L2*s15*s23*s24*s34*s35-L2*s14*s23*s25*s34*s35+L2*s14*s23*s24*s35^2+L2*s13*s24^2*s35^2-L2*s15*s23*s25*s33*s44+L4*s14*s25*s33^2*s44-L4*s13*s25*s33*s34*s44+2*L2*s13*s23*s25*s35*s44-L4*s14*s23*s33*s35*s44-L4*s13*s24*s33*s35*s44+2*L4*s13*s23*s34*s35*s44+L2*s14*s23*s25*s33*s45+L2*s15*s23^2*s34*s45-L2*s13*s23*s25*s34*s45-L2*s14*s23^2*s35*s45-L2*s13*s23*s24*s35*s45+s15*s23*s33*s35*s44-2*s13*s23*s35^2*s44-s14*s25*s33^2*s45-s15*s23*s33*s34*s45+s13*s25*s33*s34*s45+s14*s23*s33*s35*s45+s13*s24*s33*s35*s45
_[28]=L1*s14^2*s25*s33*s34-L1*s13*s14*s25*s34^2-L1*s14^2*s24*s33*s35+L1*s13*s14*s24*s34*s35+L4*s14*s23*s24*s33*s44-L4*s13*s24^2*s33*s44-L1*s13*s14*s25*s33*s44-L4*s14*s23^2*s34*s44+L4*s13*s23*s24*s34*s44+L1*s13^2*s25*s34*s44+L1*s13*s14*s23*s35*s44-L1*s13^2*s24*s35*s44+L1*s13*s14*s24*s33*s45-L1*s13*s14*s23*s34*s45-s14*s24*s25*s33*s34+s14*s23*s25*s34^2+s14*s24^2*s33*s35-s14*s23*s24*s34*s35+s13*s24*s25*s33*s44-s13*s23*s25*s34*s44-s14*s23*s24*s33*s45+s14*s23^2*s34*s45


and it includes

Code:
_[2]=s15*s24*s33-s14*s25*s33-s15*s23*s34+s13*s25*s34+s14*s23*s35-s13*s24*s35


which is a completely irrelevant polynomial as it does not contain any L, hence I want to get rid of it.

Could it drop those s-polynomials during the calculation, or does it need to keep them to know which combinations of s-coefficients are zero to remove (s-polynomial)*(L polynomial) from the L-polynomials?

I thought eliminate would do the job, but it outputs nothing at all:
Code:
> eliminate(ideal(L1*L3*s13-L1*s14-L3*s23+s24, L1*L4*s14-L1*s15-L4*s24+s25, L2*L3*s23-L2*s24-L3*s33+s34, L2*L4*s24-L2*s25-L4*s34+s35, L3*L4*s34-L3*s35-L4*s44+s45), s12*s13*s14*s23*s24*s34);
_[1]=0



Also, I thought it might help to group the variables

Code:
> ring r = 0,(L1,L2,L3,L4,L5,L6,L7,L8,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),(dp(8), dp);
> groebner(ideal(L1*L3*s13-L1*s14-L3*s23+s24, L1*L4*s14-L1*s15-L4*s24+s25, L2*L3*s23-L2*s24-L3*s33+s34, L2*L4*s24-L2*s25-L4*s34+s35, L3*L4*s34-L3*s35-L4*s44+s45));
_[1]=s15*s24*s33-s14*s25*s33-s15*s23*s34+s13*s25*s34+s14*s23*s35-s13*s24*s35
_[2]=L3*s25*s33*s34-L3*s24*s33*s35-L4*s24*s33*s44+L4*s23*s34*s44-s25*s34^2+s24*s34*s35+s24*s33*s45-s23*s34*s45
_[3]=L3*s15*s33*s34-L3*s14*s33*s35-L4*s14*s33*s44+L4*s13*s34*s44-s15*s34^2+s14*s34*s35+s14*s33*s45-s13*s34*s45
_[4]=L3*s15*s23*s34-L3*s13*s25*s34-L3*s14*s23*s35+L3*s13*s24*s35-L4*s14*s23*s44+L4*s13*s24*s44-s15*s24*s34+s14*s25*s34+s14*s23*s45-s13*s24*s45
_[5]=L2*s24*s25*s34-L2*s24^2*s35-L2*s23*s25*s44+L2*s23*s24*s45+L4*s24*s33*s44-L4*s23*s34*s44+s23*s35*s44-s24*s33*s45
_[6]=L2*s14*s25^2*s33*s34+L2*s15*s23*s25*s34^2-L2*s13*s25^2*s34^2-L2*s15*s24^2*s33*s35-L2*s14*s23*s25*s34*s35+L2*s13*s24*s25*s34*s35-L2*s15*s23*s25*s33*s44+L2*s15*s23*s24*s33*s45+L4*s15*s24*s33^2*s44-L4*s15*s23*s33*s34*s44+s15*s23*s33*s35*s44-s15*s24*s33^2*s45
_[7]=L1*s14*s15*s34-L1*s14^2*s35-L1*s13*s15*s44+L1*s13*s14*s45+L4*s14*s23*s44-L4*s13*s24*s44-s14*s25*s34+s14*s24*s35+s13*s25*s44-s14*s23*s45
_[8]=L1*s14^2*s25*s33*s34+L1*s14*s15*s23*s34^2-L1*s13*s14*s25*s34^2-L1*s14^2*s24*s33*s35-L1*s14^2*s23*s34*s35+L1*s13*s14*s24*s34*s35-L1*s13*s15*s24*s33*s44+L1*s13*s14*s24*s33*s45+L4*s14*s23*s24*s33*s44-L4*s13*s24^2*s33*s44+s15*s24^2*s33*s34-2*s14*s24*s25*s33*s34-s15*s23*s24*s34^2+s13*s24*s25*s34^2+s14*s24^2*s33*s35+s14*s23*s24*s34*s35-s13*s24^2*s34*s35+s13*s24*s25*s33*s44-s14*s23*s24*s33*s45
_[9]=L4^2*s24*s33*s44-L4^2*s23*s34*s44+L4*s25*s34^2-L4*s24*s34*s35-L4*s25*s33*s44+L4*s23*s35*s44-L4*s24*s33*s45+L4*s23*s34*s45-s25*s34*s35+s24*s35^2+s25*s33*s45-s23*s35*s45
_[10]=L4^2*s14*s33*s44-L4^2*s13*s34*s44+L4*s15*s34^2-L4*s14*s34*s35-L4*s15*s33*s44+L4*s13*s35*s44-L4*s14*s33*s45+L4*s13*s34*s45-s15*s34*s35+s14*s35^2+s15*s33*s45-s13*s35*s45
_[11]=L4^2*s14*s23*s44-L4^2*s13*s24*s44+L4*s15*s24*s34-L4*s14*s25*s34-L4*s15*s23*s44+L4*s13*s25*s44-L4*s14*s23*s45+L4*s13*s24*s45-s15*s24*s35+s14*s25*s35+s15*s23*s45-s13*s25*s45
_[12]=L3*L4*s34-L3*s35-L4*s44+s45
_[13]=L3*L4*s24*s33-L3*L4*s23*s34-L3*s25*s33+L3*s23*s35+s25*s34-s24*s35
_[14]=L3*L4*s14*s33-L3*L4*s13*s34-L3*s15*s33+L3*s13*s35+s15*s34-s14*s35
_[15]=L3*L4*s14*s23-L3*L4*s13*s24-L3*s15*s23+L3*s13*s25+s15*s24-s14*s25
_[16]=L2*L4*s24-L2*s25-L4*s34+s35
_[17]=L2*L4*s23*s44-L3*L4*s33*s34-L2*s25*s34+L2*s24*s35-L2*s23*s45+L3*s33*s35
_[18]=L2*L4*s14*s25*s33+L2*L4*s15*s23*s34-L2*L4*s13*s25*s34-L2*L4*s14*s23*s35+L2*L4*s13*s24*s35-L2*s15*s25*s33-L4*s15*s33*s34+s15*s33*s35
_[19]=L1*L4*s14-L1*s15-L4*s24+s25
_[20]=L1*L4*s13*s44-L3*L4*s23*s34-L1*s15*s34+L1*s14*s35-L1*s13*s45+L3*s23*s35+s25*s34-s24*s35
_[21]=L2*L3*s23-L2*s24-L3*s33+s34
_[22]=L2*L3*s25*s34-L2*L3*s24*s35-L2*L4*s24*s44+L3*L4*s34^2+L2*s24*s45-L3*s34*s35
_[23]=L1*L3*s13-L1*s14-L3*s23+s24
_[24]=L1*L3*s15*s34-L1*L3*s14*s35-L1*L4*s14*s44+L3*L4*s24*s34+L1*s14*s45-L3*s25*s34
_[25]=L1*L2*s15*s24-L1*L2*s14*s25-L1*L4*s14*s34+L2*L4*s24^2+L1*s14*s35-L2*s24*s25
_[26]=L1*L2*s15*s23-L1*L2*s13*s25-L1*L4*s14*s33+L2*L4*s23*s24+L1*s13*s35-L2*s23*s25+L4*s24*s33-L4*s23*s34
_[27]=L1*L2*s14*s23-L1*L2*s13*s24-L1*L3*s13*s33+L2*L3*s23^2+L1*s13*s34-L2*s23*s24
_[28]=L1*L2*s14*s25*s34-L1*L2*s14*s24*s35-L1*L2*s13*s25*s44+L1*L2*s13*s24*s45+L1*L4*s14*s34^2-L1*L4*s13*s34*s44-L2*L4*s24^2*s34+L2*L4*s23*s24*s44-L1*s14*s34*s35+L1*s13*s35*s44+L2*s24^2*s35-L2*s23*s24*s45


but it does not. Not only is _[1]=s15*s24*s33-s14*s25*s33-s15*s23*s34+s13*s25*s34+s14*s23*s35-s13*s24*s35 still there (and moved to the beginning), the calculation has become 100 times slower. huh? ( for the input L1*L2*s12-L1*s13-L2*s22+s23, L1*L3*s13-L1*s14-L3*s23+s24, L1*L4*s14-L1*s15-L4*s24+s25, L2*L3*s23-L2*s24-L3*s33+s34, L2*L4*s24-L2*s25-L4*s34+s35, L3*L4*s34-L3*s35-L4*s44+s45 It takes all the time. The others are only like 50 % slower )


( to avoid an xy-problem: I do not actually need the entire Gröbner basis. I need to know if the equations contain a solution for each/some individual L, i.e. if the ideal contains a polynomial that depends only one a single L, like (s..) L1^2 + (s..) L1 + (s...) )


Report this post
Top
 Profile  
Reply with quote  
hannes
 Post subject: Re: Gröbner basis of polynomials with unknown coefficients
PostPosted: Fri May 20, 2016 12:40 pm 

Joined: Wed May 25, 2005 4:16 pm
Posts: 275
Thre are two ways to compute Groebner bases with parameters:
- move the s.. to the coefficients (i.e. work with rational function in s...,
Code:
ring r=(0,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),(L1,L2,L3,L4,L5,L6,L7,L8),,dp;

- or (recommended), choose an ordering which separates the s.. from the L.. variables:
Code:
ring r = 0,(L1,L2,L3,L4,L5,L6,L7,L8,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),(dp(8),dp);


In this second, recommend case the Groebner basis contains
Code:
s15*s24*s33-s14*s25*s33-s15*s23*s34+s13*s25*s34+s14*s23*s35-s13*s24*s35=0

i.e. you have a condition on the parameters:: if this condition is not met the whole system cannot be fulfilled.

If you choose the first variant, the Groeber basis is simply
Code:
groebner(ideal(L1*L3*s13-L1*s14-L3*s23+s24, L1*L4*s14-L1*s15-L4*s24+s25, L2*L3*s23-L2*s24-L3*s33+s34, L2*L4*s24-L2*s25-L4*s34+s35, L3*L4*s34-L3*s35-L4*s44+s45));
_[1]=1

i.e. the system is (in general: with the exception of some condition on the parameters) not solvable.


Report this post
Top
 Profile  
Reply with quote  
BeniBela
 Post subject: Re: Gröbner basis of polynomials with unknown coefficients
PostPosted: Fri May 20, 2016 1:13 pm 

Joined: Thu May 19, 2016 4:33 pm
Posts: 2
hannes wrote:
Thre are two ways to compute Groebner bases with parameters:
- move the s.. to the coefficients (i.e. work with rational function in s...,
Code:
ring r=(0,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),(L1,L2,L3,L4,L5,L6,L7,L8),,dp;




That looks interesting. One less comma, though

But I guess, it does not help if it turns into _[1]=1

hannes wrote:

- or (recommended), choose an ordering which separates the s.. from the L.. variables:
Code:
ring r = 0,(L1,L2,L3,L4,L5,L6,L7,L8,s11,s12,s13,s14,s15,s16,s17,s18,s21,s22,s23,s24,s25,s26,s27,s28,s31,s32,s33,s34,s35,s36,s37,s38,s41,s42,s43,s44,s45,s46,s47,s48,s51,s52,s53,s54,s55,s56,s57,s58,s61,s62,s63,s64,s65,s66,s67,s68,s71,s72,s73,s74,s75,s76,s77,s78,s81,s82,s83,s84,s85,s86,s87,s88),(dp(8),dp);



I tried that, but it becomes 100 times slower than the unseparated case.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 3 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 11:05 am
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group