Bill Page wrote: > > On 16 May 2017 at 16:13, Waldek Hebisch <[email protected]> wrote: > > ... > > One trick is to substitute integers for some parameters. > > After > > > > oV := OrderedVariableList([mp,mq,mr,yqp,yrp,yrq]) > > evl := enumerate()$oV > > ideq2a := [map(c +-> eval(c, evl, [3, 5, 7, 9, 11, 13]), p) for p in ideq2]; > > > > I was able to compute groebner basis of the evaluated ideal > > in about 5 seconds. > > Wow, that is remarkable. I would not have expected this magnitude of speed > up. > > > For almost all possible values the evaluated ideal > > has Groebner basis with the same structure as the > > orignal one. > > OK, interesting but not so immediately useful. > > > It is possible to reconstruct (and verify) Groebner basis > > for the full ideal from Groebner basis for evaluated ideal, > > but ATM FriCAS contains no such code. > > > > Surely such reconstruction is likely to require a lot of computation, > no? Do you have a reference to any publications on this subject? Is > there already an implementation in some other system?
There is thesis by Elizabeth A. Arnold. Published in: Elizabeth A. Arnold, Modular algorithms for computing Groebner bases, Journal of Symbolic Computation 35 (2003) 403-419 There is also paper by Bernard Parisse Bernard Parisse. A probabilistic and deterministic modular algorithm for computing Groebnerbasis over Q 2013. <hal-00862416v1> where he describes implementation in Giac. Both articles deal with polynomials with rational coefficients and using reduction modulo prime, but the same idea works for coefficients involving variables. Concerning time for "lifting": the most expensive part may be verification. Currently in some examples FriCAS needs less time to compute Groebner basis from orignal data compared to case where it is already given Groebner basis (so the whole task i just to check that the input is indeed a Groebner basis). AFAICS this is because criteria used during computation tell FriCAS that some S-polynomials will be zero without need to compute them. When FriCAS has only basis, but no trace of computation that led to this basis FriCAS need to compute some S-polynomials which otherwise could be skipped. One idea which could be relatively easy to implement is recording of history of computation: which S-polynomials where computed and if they were useful to the final result. Then for full computation one could use the same sequence of steps as for evaluated polynomias, but skipping useless computations. The trick with recording history may be useful for groebnerFactorize > > groebnerFactorize for evaluated ideal takes 224.17 sec. > > I was also able to do groebnerFactorize after evaluating > > IIRC only 3 variables. I am not sure if it possible to > > reconstruct full result of groebnerFactorize from evaluated > > result, but at least you should be able to get some > > quantitative data like number of subsystems (1086) and > > degrees. > > > > There seems to be quite a lot of literature on algorithms for > triangular decomposition. > > Reconstruction sounds interesting but I am skeptical if it can be made > efficient. > > > BTW: After evaluating variables one could retract coefficients > > to rational numbers and then reduce modulo a prime. For > > Groebner basis this should give additianal speedup. For > > groebnerFactorize reducing modulo prime is dangerous, > > because then a lot of univariate polynomials will be reducible, > > so it may change structure of basis quite a lot. > > > > Thank you for these ideas. > > Bill. > > -- > You received this message because you are subscribed to the Google Groups > "FriCAS - computer algebra system" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at https://groups.google.com/group/fricas-devel. > For more options, visit https://groups.google.com/d/optout. > -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
