On Wednesday 04 February 2009, Adela wrote: > I need to solve a big system of nonlinear equations(it consists of 114 > equations, with 61 indeterminates, all of them can be only 0 and 1 and > I work modulo 2).
> I solve it using Groebner bases. So, my problem coms to finding the > reduced Groebner base for an ideal generated by 114 polynomials. As mentioned earlier, you probably want to work in the boolean polynomial ring sage: B.<a,b,c,d,e> = BooleanPolynomialRing(5, order='lex') sage: I = B.ideal([a*b + a*c + c*e + e + 1, b*d + c*e + c + d + 1, a*b + a*c + c + e + 1, a + b*c + c*d + c + d*e, a*b + a*e + c*d + c + 1] sage: I.groebner_basis() [a + 1, b, d + 1, e + 1] > Can you tell me if Sage can face it, or approximatively how long would > take to do that? Well, the worst case scenario is O(2^61) and the best case O(61^3) (a linear system ;)). That's as much as one can say a priori. Since your system is overdefined I'd guess you should do better than O(2^61) but likely only an experiment can tell. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://www.informatik.uni-bremen.de/~malb _jab: [email protected] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
