Back to Forum | View unanswered posts | View active topics
|
Page 1 of 1
|
[ 3 posts ] |
|
Author |
Message |
BeniBela
|
Post subject: Gröbner basis of polynomials with unknown coefficients Posted: 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...) )
|
|
|
Top |
|
|
hannes
|
Post subject: Re: Gröbner basis of polynomials with unknown coefficients Posted: 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.
|
|
|
Top |
|
|
BeniBela
|
Post subject: Re: Gröbner basis of polynomials with unknown coefficients Posted: 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.
|
|
|
Top |
|
|
|
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 10:54 am
|
|