Thanks a lot Simon. Just trying to get my head around it now .... in order to compare it to my problem, I need to convert the finite field part into simple language that I can understand ...
Kind regards Gary On Wed, Apr 24, 2013 at 10:53 AM, Simon King <simon.k...@uni-jena.de> wrote: > Hi Gary, > > On 2013-04-22, Gary McConnell <garymako...@googlemail.com> wrote: > > I kind-of went quiet on this because Nicolas was way ahead of me :) .... > > but (obviously only if you have time) I would be fascinated to hear how > you > > resolve this because I have some not dissimilar problems in finite field > > vector spaces which may benefit from the techniques (see for example > > > https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/5i0IeAsyjTE > ) > > Before I explain my current heuristics, let's fix some notations: > > I have an approximation (knowing generators and relations out to a > certain degree) of a graded commutative algebra R over a finite (prime) > field F. I know a basis for the degree d part. I know a finite subset > P of the ring approximation which is guaranteed to generate an ideal in > R of Krull dimension 1. I have reasons to believe that there is a degree-d > element p of the ring approximation such that P and p together generate an > ideal of Krull dimension 0 in R (in fact, I know that there exists some > finite extension F' of F such that R\otimes_F F' contains such element > in degree d). > > The aim is to find p. > > Moreover, I have morphisms of graded algebras phi_i:R -> R_i (i=1,...,k), > where the R_i are free graded commutative algebras. The construction of > the phi_i ensures that a subset S of R generates an ideal of Krull > dimension 0 in R if and only if phi_i(S) generates an ideal of Krull > dimension 0 in R_i, for all i=1,...,k. > > And now comes the potentially most expensive part: I compute a Gröbner > basis of the radical of phi_i(P) for all i=1,...,k. Hence, for each > degree-d monomial s of R, I can compute the normal form of phi_i(s) with > respect to the radical of phi(P). For each s, I combine the sequences of > coefficients (for all i together) into a row. > > By Gaussian elimination, I get linear combinations c_1,...,c_t of the > degree-d monomials of R, such that the rows obtained from c_1,...,c_t > form a matrix in echelon form. > > For each i=1,...,k and each j=1,...,t, I can test whether phi_i(c_j) is > contained in the radical of phi_i(P) or whether phi_i(P\cup c_j) > generates an ideal of Krull dimension 0. > > By the dancing links algorithm, I try to find a subset > c_{j_1},...,c_{j_r}, such that for each i=1,...,k there is precisely one > c_{j_y} such that phi_i(P\cup c_{j_y}) generates an ideal of Krull > dimension 0, and all others are mapped to an element of the radical of > phi_i(P). > > It is easy to see that then the sum of the c_{j_1},...,c_{j_y} is an > element p that I was looking for. Because of the intermediate step of > computing an echelon form, it quite often happens that the dancing link > algorithm succeeds. If it does not succeed, then I enumerate a bounded > number (at most 512) of linear combinations of the c_{j_1},...,c_{j_y}. > > I have no idea if this heuristics is useful in your application. But in > my situation, I see that it succeeds far more often than my previous > heuristics (namely: try at most 512 linear combinations of degree-d > monomials of R). > > Best regards, > Simon > > > -- > You received this message because you are subscribed to a topic in the > Google Groups "sage-combinat-devel" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/sage-combinat-devel/eKNz3fM5yJo/unsubscribe?hl=en > . > To unsubscribe from this group and all its topics, send an email to > sage-combinat-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-combinat-devel@googlegroups.com. > Visit this group at > http://groups.google.com/group/sage-combinat-devel?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
