| Singular https://www.singular.uni-kl.de/forum/ |
|
| the largest degree of variable when computing Groebner Basis https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1872 |
Page 1 of 1 |
| Author: | gepo [ Fri Oct 15, 2010 6:53 am ] |
| Post subject: | the largest degree of variable when computing Groebner Basis |
When I compute some Groebner Basis, I found the degree of some variables went up very quickly. Then I want to know whether there is a largest degree of variables when computing Groebner Basis. Thanks a lot. Gepo |
|
| Author: | etienne [ Fri Oct 15, 2010 11:46 am ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
This is fact of Groebner basis, If you look in the book of Cox Little O'shea "ideals, varietes and algo", they are some examples where the degree become very big with some order and very small with an other. I think that it is an open problem to bound the degree of the elements of a groebner basis. Etienne PS I am not a specialist of that topic, I just read the book above gepo wrote: When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis. Thanks a lot. Gepo |
|
| Author: | gepo [ Fri Oct 15, 2010 7:09 pm ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
I am also reading the book. But it seems it did not mention too much on this topic. Hope someone could give us some clues. etienne wrote: This is fact of Groebner basis, If you look in the book of Cox Little O'shea "ideals, varietes and algo", they are some examples where the degree become very big with some order and very small with an other.
I think that it is an open problem to bound the degree of the elements of a groebner basis. Etienne PS I am not a specialist of that topic, I just read the book above gepo wrote: When I compute some Groebner Basis, I found the degree of some variables went up very quickly. Then I want to know whether there is a largest degree of variables when computing Groebner Basis. Thanks a lot. Gepo |
|
| Author: | John Perry [ Mon Oct 18, 2010 1:21 pm ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
gepo wrote: When I compute some Groebner Basis, I found the degree of some variables went up very quickly. Then I want to know whether there is a largest degree of variables when computing Groebner Basis. Thanks a lot. Gepo The answer (which I don't know) depends on the term ordering. What ordering are you using? Using dp would keep the degree lower than using lp. |
|
| Author: | gepo [ Fri Oct 22, 2010 11:27 pm ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
I tried both. The thing I want to know is whether there is a theoretical bound for the degree. Thanks Gepo John Perry wrote: gepo wrote: When I compute some Groebner Basis, I found the degree of some variables went up very quickly. Then I want to know whether there is a largest degree of variables when computing Groebner Basis. Thanks a lot. Gepo The answer (which I don't know) depends on the term ordering. What ordering are you using? Using dp would keep the degree lower than using lp. |
|
| Author: | John Perry [ Sat Oct 23, 2010 9:35 pm ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
gepo wrote: I tried both. The thing I want to know is whether there is a theoretical bound for the degree. A paper written by Bardet, Faugere, and Salvy might be helpful. It's titled, "Asymptotic Expansion of the Degree of Regularity for Semi-Regular Sequences of Equations". They repeat an precise, sharp formula for regular systems that dates back to Lazard (1983). You can download it from Faugere's web page; they seem to have presented it at MEGA 2005, but I don't find any reference to a journal publication. Older than this is a paper by Mayr & Meyer, titled (I think) "The Complexity of the Word Problem for Commutative Semigroups and Polynomial Ideals". There's also a paper by Y. N. Lakshman, "On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal". Hope at least one of these helps. |
|
| Author: | daniel [ Fri Dec 03, 2010 2:24 pm ] |
| Post subject: | Re: the largest degree of variable when computing Groebner Basis |
In Dube's paper "The structure of polynomial ideals and Gröbner bases" [MR Number mr=1053942]there is a bound on the degree of the polynomials in a groebner basis. It depends on the degree d of the polynomials one starts with and on the number n of variables in the polynomial ring. Then for every monomial ordering there is a Groebner basis of degree less or equal to 2((d^2/2)+d)^{2^{n-1}}. If I recall correctly this bound does not even need the characteristic of the ground field to be zero (unlike the previous bound by Moeller Mora Bayer Giusti...). This bound is also mentioned (without reference i think) in the book "Modern Computer Algebra" - Gerhard, Gathen ( around p.590 ?) |
|
| Page 1 of 1 | All times are UTC + 1 hour [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|