Solving multivariate polynomial systems over GF(2)
132 views
Skip to first unread message
lesshaste
Jul 27, 2009, 1:01:37 PM7/27/09
to sage-support
I am new to sage and am attempting to solve systems of multivariate
polys over GF(2). My first attempt with a small example is
R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
B= I.groebner_basis();
That works fine but how do I now solve B in sage to actually an
answer? In my case I only need one answer rather than the full list
of possible solutions.
Also, I read back in April that there was a plan to implement
Faugere's F4 algorithm. As the systems I want to solve are very large,
I would be particularly interested in that or any related tools that
are in development. (Anyone working on an XL variant?)
Raphael
polys over GF(2). My first attempt with a small example is
R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
B= I.groebner_basis();
That works fine but how do I now solve B in sage to actually an
answer? In my case I only need one answer rather than the full list
of possible solutions.
Also, I read back in April that there was a plan to implement
Faugere's F4 algorithm. As the systems I want to solve are very large,
I would be particularly interested in that or any related tools that
are in development. (Anyone working on an XL variant?)
Raphael
Harald Schilly
Jul 31, 2009, 1:06:45 PM7/31/09
to sage-support
bump, since there was no answer so far and despite i don't know the
answer it should be rather simple ... ?
answer it should be rather simple ... ?
Simon King
Jul 31, 2009, 9:59:26 PM7/31/09
to sage-support
Harald, thank you for reminding us of this post.
Raphael,
Actually I started an answer a while ago, but thought it wouldn't be
helpful and therefore didn't post it.
On 27 Jul., 19:01, lesshaste <drr...@gmail.com> wrote:
> I am new to sage and am attempting to solve systems of multivariate
> polys over GF(2). My first attempt with a small example is
>
> R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
> I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> B= I.groebner_basis();
This is of course a good starting point.
There is the "solve" command, but as much as I know,
- this can only work with symbolic expressions (hence, one must
transform the polynomials into symbolic expressions),
- it ignores that you work over GF(2), which is worse.
So, probably the following is not a solution for your problem:
sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 *
c111 +
....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 *
c112 ,
....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
sage: B= I.groebner_basis()
sage: B
[a111*a122*b111*b212*c112 + a121*a122*b211*b212*c112 + a111*b111,
a122*b112*b211*c112 + a122*b111*b212*c112 + b111, a112*a121*b212*c112
+ a111*a122*b212*c112 + a111, a111*b111*c111 + a122*b212*c112,
a121*b111*c111 + a122*b112*c112, a111*b211*c111 + a112*b212*c112,
a121*b211*c111 + a122*b212*c112 + 1, a112*b112*c112 + a122*b212*c112 +
1, a112*b111 + a122*b211, a111*b112 + a121*b212]
sage: X = var(','.join(R.variable_names()))
sage: solve([symbolic_expression(t)==0 for t in B],X)
[[a111 == 0, a112 == -1/(r1*r4), a121 == -1/(r2*r3), a122 == 0, b111
== 0, b112 == r1, b211 == r2, b212 == 0, c111 == r3, c112 == r4],
[a111 == 1/(r5*r7), a112 == 0, a121 == 0, a122 == -1/(r6*r8), b111 ==
r5, b112 == 0, b211 == 0, b212 == r6, c111 == r7, c112 == r8]]
> That works fine but how do I now solve B in sage to actually an
> answer? In my case I only need one answer rather than the full list
> of possible solutions.
Sorry, I don't know.
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm. As the systems I want to solve are very large,
> I would be particularly interested in that or any related tools that
> are in development. (Anyone working on an XL variant?)
Do you mean F5?
I was involved in the F5 toy implementation. But it really isn't more
than a toy, that might be useful for teaching. For example, one can
demonstrate that there are really only few reductions to zero in the
F5 algorithm.
But certainly the non-F5 algorithms in Singular are **much** (I mean
***MUCH***) better than our toy-F5.
If I understand correctly, not only your coefficients are in GF(2),
but the variables are in GF(2) as well, hence, you have in fact the
equation x==x^2 for any variable x, right?
Then you could start with
sage:
RB.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=BooleanPolynomialRing
()
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 *
sage: B
[a111 + b212, a112 + b211, a121 + b112, a122 + b111, b111*b112 + b111
+ b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1, b211*b212 + b211 + b212 + 1, c111 + 1,
c112 + 1]
As far as I know, this uses PolyBoRi in the background, which is
specialised for Groebner basis computations over GF(2) with the
relations x^2==x. And I think this could deal with pretty big
examples.
But again, I don't know how to actually find a solution.
Best regards,
Simon
Raphael,
Actually I started an answer a while ago, but thought it wouldn't be
helpful and therefore didn't post it.
On 27 Jul., 19:01, lesshaste <drr...@gmail.com> wrote:
> I am new to sage and am attempting to solve systems of multivariate
> polys over GF(2). My first attempt with a small example is
>
> R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
> I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> B= I.groebner_basis();
There is the "solve" command, but as much as I know,
- this can only work with symbolic expressions (hence, one must
transform the polynomials into symbolic expressions),
- it ignores that you work over GF(2), which is worse.
So, probably the following is not a solution for your problem:
sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 *
c111 +
....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 *
c112 ,
....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
sage: B= I.groebner_basis()
sage: B
[a111*a122*b111*b212*c112 + a121*a122*b211*b212*c112 + a111*b111,
a122*b112*b211*c112 + a122*b111*b212*c112 + b111, a112*a121*b212*c112
+ a111*a122*b212*c112 + a111, a111*b111*c111 + a122*b212*c112,
a121*b111*c111 + a122*b112*c112, a111*b211*c111 + a112*b212*c112,
a121*b211*c111 + a122*b212*c112 + 1, a112*b112*c112 + a122*b212*c112 +
1, a112*b111 + a122*b211, a111*b112 + a121*b212]
sage: X = var(','.join(R.variable_names()))
sage: solve([symbolic_expression(t)==0 for t in B],X)
[[a111 == 0, a112 == -1/(r1*r4), a121 == -1/(r2*r3), a122 == 0, b111
== 0, b112 == r1, b211 == r2, b212 == 0, c111 == r3, c112 == r4],
[a111 == 1/(r5*r7), a112 == 0, a121 == 0, a122 == -1/(r6*r8), b111 ==
r5, b112 == 0, b211 == 0, b212 == r6, c111 == r7, c112 == r8]]
> That works fine but how do I now solve B in sage to actually an
> answer? In my case I only need one answer rather than the full list
> of possible solutions.
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm. As the systems I want to solve are very large,
> I would be particularly interested in that or any related tools that
> are in development. (Anyone working on an XL variant?)
I was involved in the F5 toy implementation. But it really isn't more
than a toy, that might be useful for teaching. For example, one can
demonstrate that there are really only few reductions to zero in the
F5 algorithm.
But certainly the non-F5 algorithms in Singular are **much** (I mean
***MUCH***) better than our toy-F5.
If I understand correctly, not only your coefficients are in GF(2),
but the variables are in GF(2) as well, hence, you have in fact the
equation x==x^2 for any variable x, right?
Then you could start with
sage:
RB.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=BooleanPolynomialRing
()
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 *
c111 +
a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
a121 * b211 * c111 + a122 * b212 * c112 - 1)*RB
sage: B= I.groebner_basis()
a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
a121 * b211 * c111 + a122 * b212 * c112 - 1)*RB
sage: B
[a111 + b212, a112 + b211, a121 + b112, a122 + b111, b111*b112 + b111
+ b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1, b211*b212 + b211 + b212 + 1, c111 + 1,
c112 + 1]
As far as I know, this uses PolyBoRi in the background, which is
specialised for Groebner basis computations over GF(2) with the
relations x^2==x. And I think this could deal with pretty big
examples.
But again, I don't know how to actually find a solution.
Best regards,
Simon
Martin Albrecht
Aug 1, 2009, 11:09:22 AM8/1/09
to sage-s...@googlegroups.com
On Monday 27 July 2009, lesshaste wrote:
> I am new to sage and am attempting to solve systems of multivariate
> polys over GF(2). My first attempt with a small example is
>
> R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
> I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> B= I.groebner_basis();
>
> That works fine but how do I now solve B in sage to actually an
> answer? In my case I only need one answer rather than the full list
> of possible solutions.
> I am new to sage and am attempting to solve systems of multivariate
> polys over GF(2). My first attempt with a small example is
>
> R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
> I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> B= I.groebner_basis();
>
> That works fine but how do I now solve B in sage to actually an
> answer? In my case I only need one answer rather than the full list
> of possible solutions.
Sorry, for the late reply, I am on vacation this week:
If you are looking for solutions in GF(2) you should use the boolean
polynomial ring. Also, your original system of equations has dimension 6, i.e.
it does not have a finite set of solutions. You should definitely add the
field polynomials (x_i^2 + x_i) to gain a system which is zero dimensional
(the BooleanPolynomialRing does this implicitly btw.)
Finally, for solving you should use a lexicographical term ordering:
sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
BooleanPolynomialRing(order='lex')
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
sage: I.groebner_basis()
[a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
Then, the Gröbner basis has a triangular shape and allows you to read the
solution.
The introduction of my Diplomarbeit describes this in more detail:
http://bit.ly/B4zdT
http://sage.math.washington.edu/home/malb/thesis-1.0.pdf
(sorry for the self reference)
Alternatively, you can use the variety() function -- a variety is a solution
set to a set of polynomial equations -- which only works polynomial rings
right now:
sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=GF(2)[]
sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
sage: J = I + sage.rings.ideal.FieldIdeal(R)
sage: J.variety()
[{a112: 0, a111: 0, a122: 0, a121: 0, b211: 0, c111: 1, b212: 0, b112: 0,
c112: 1, b111: 0}, {a112: 0, a111: 0, a122: 1, a121: 0, b211: 0, c111: 1,
b212: 0, b112: 0, c112: 1, b111: 1}, {a112: 0, a111: 0, a122: 0, a121: 1,
b211: 0, c111: 1, b212: 0, b112: 1, c112: 1, b111: 0}, {a112: 0, a111: 0,
a122: 1, a121: 1, b211: 0, c111: 1, b212: 0, b112: 1, c112: 1, b111: 1},
{a112: 1, a111: 0, a122: 0, a121: 0,b211: 1, c111: 1, b212: 0, b112: 0, c112:
1, b111: 0}, {a112: 1, a111: 0, a122: 1, a121: 0, b211: 1, c111: 1, b212: 0,
b112: 0, c112: 1, b111: 1}, {a112: 1, a111: 0, a122: 0, a121: 1, b211: 1,
c111: 1, b212: 0, b112: 1, c112: 1, b111: 0}, {a112: 1, a111: 0, a122: 1,
a121: 1, b211: 1, c111: 1, b212: 0, b112: 1, c112: 1, b111: 1}, {a112: 0,
a111: 1, a122: 0, a121: 0, b211: 0, c111: 1, b212: 1, b112: 0, c112: 1, b111:
0}, {a112: 0, a111: 1, a122: 1, a121: 0, b211: 0, c111: 1, b212: 1, b112: 0,
c112: 1, b111: 1}, {a112: 0, a111: 1, a122: 0, a121: 1, b211: 0, c111: 1,
b212: 1, b112: 1, c112: 1, b111: 0}, {a112: 0, a111: 1, a122: 1, a121: 1,
b211: 0, c111: 1, b212: 1, b112: 1, c112: 1, b111: 1}, {a112: 1, a111: 1,
a122: 0, a121: 0, b211: 1, c111: 1, b212: 1, b112: 0, c112: 1, b111: 0},
{a112: 1, a111: 1, a122: 1, a121: 0, b211: 1, c111: 1, b212: 1, b112: 0, c112:
1, b111: 1}, {a112: 1, a111: 1, a122: 0, a121: 1, b211: 1, c111: 1, b212: 1,
b112: 1, c112: 1, b111: 0}, {a112: 1, a111: 1, a122: 1, a121: 1, b211: 1,
c111: 1, b212: 1, b112: 1, c112: 1, b111: 1}]
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm.
There have been numerous attempts to implement F4 efficiently in the open-
source world but non of them succeeded to satisfaction. However, PolyBoRi's
SlimGB algorithm is heavily inspired by F4 and you can even use linear
algebra. PolyBoRi is used behind the scene when you construct a
BooleanPolynomialRing.
> As the systems I want to solve are very large,
> I would be particularly interested in that or any related tools that
> are in development. (Anyone working on an XL variant?)
Btw. XL is a redundant version of F4 and I have little faith in its
performance.
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: martinr...@jabber.ccc.de
Simon King
Aug 1, 2009, 11:47:58 AM8/1/09
to sage-support
Hi Martin,
On Aug 1, 4:09 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
interpretation of the meaning of "lex" (I use sage 4.1, and you?), or
a misprint on my side (but so far I can't see any)?
sage:
RB.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=BooleanPolynomialRing
(order='lex')
sage: IB = (a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211
sage: GB
c112 + 1]
It seems that your answer is not a Groebner Basis:
sage: G = Sequence([a111 + b212, a112 + b211, a121 + b112, a122 +
b111, c111 + 1, c112 + 1])
sage: [p.reduce(G) for p in GB]
[0,
0,
0,
0,
0]
sage: [p.reduce(GB) for p in G]
[0, 0, 0, 0, 0, 0]
Cheers,
Simon
On Aug 1, 4:09 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
> sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
> BooleanPolynomialRing(order='lex')
> sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
>
> sage: I.groebner_basis()
> [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
Why do I get a different result? Bug in PolyBoRi, a changed
> BooleanPolynomialRing(order='lex')
> sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
>
> sage: I.groebner_basis()
> [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
interpretation of the meaning of "lex" (I use sage 4.1, and you?), or
a misprint on my side (but so far I can't see any)?
sage:
RB.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112>=BooleanPolynomialRing
(order='lex')
sage: IB = (a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211
* c111 + a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 *
c112 , a121 * b211 * c111 + a122 * b212 * c112 - 1)*RB
sage: GB = IB.groebner_basis()
c112 , a121 * b211 * c111 + a122 * b212 * c112 - 1)*RB
sage: GB
[a111 + b212, a112 + b211, a121 + b112, a122 + b111, b111*b112 + b111
+ b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1, b211*b212 + b211 + b212 + 1, c111 + 1,
+ b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1,
c112 + 1]
It seems that your answer is not a Groebner Basis:
sage: G = Sequence([a111 + b212, a112 + b211, a121 + b112, a122 +
b111, c111 + 1, c112 + 1])
sage: [p.reduce(G) for p in GB]
[0,
0,
0,
0,
b111*b112 + b111 + b112 + 1,
b111*b211 + b111 + b211 + 1,
b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1,
b211*b212 + b211 + b212 + 1,
0,
b111*b211 + b111 + b211 + 1,
b111*b212 + b112*b211 + 1,
b112*b212 + b112 + b212 + 1,
b211*b212 + b211 + b212 + 1,
0]
sage: [p.reduce(GB) for p in G]
[0, 0, 0, 0, 0, 0]
Cheers,
Simon
lesshaste
Aug 1, 2009, 5:09:31 PM8/1/09
to sage-support
Thanks very much for the reply.
> Finally, for solving you should use a lexicographical term ordering:
>
> sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
> BooleanPolynomialRing(order='lex')
> sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
>
> sage: I.groebner_basis()
> [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
>
> Then, the Gröbner basis has a triangular shape and allows you to read the
> solution.
>
> The introduction of my Diplomarbeit describes this in more detail:
>
> http://bit.ly/B4zdThttp://sage.math.washington.edu/home/malb/thesis-1.0.pdf
>
Thanks, that's very helpful.
> > Also, I read back in April that there was a plan to implement
> > Faugere's F4 algorithm.
>
> There have been numerous attempts to implement F4 efficiently in the open-
> source world but non of them succeeded to satisfaction. However, PolyBoRi's
> SlimGB algorithm is heavily inspired by F4 and you can even use linear
> algebra. PolyBoRi is used behind the scene when you construct a
> BooleanPolynomialRing.
>
The problem in my case is really one of scale. I have put a larger
example at the bottom of this message. When I try to find the
groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
memory usage goes over 1.6GB and then sage crashes. It is possible
that it just isn't realistic to solve it using Groebner Bases.
However, I should say that when reformulated as a SAT solving problem,
the standard off the shelf minisat 2.0 code can solve it in 0.04
seconds. This is despite the fact that minisat only takes CNF as the
input which means that all the structure of the problem has been
removed before it sees it.
Raphael
--- Larger example that crashes sage/polybori but which can be solved
instantly by minisat ---
R.<a111,a112,a113,a114,a115,a116,a117,a121,a122,a123,a124,a125,a126,a127,a211,a212,a213,a214,a215,a216,a217,a221,a222,a223,a224,a225,a226,a227,b111,b112,b113,b114,b115,b116,b117,b121,b122,b123,b124,b125,b126,b127,b211,b212,b213,b214,b215,b216,b217,b221,b222,b223,b224,b225,b226,b227,c111,c112,c113,c114,c115,c116,c117,c121,c122,c123,c124,c125,c126,c127,c211,c212,c213,c214,c215,c216,c217,c221,c222,c223,c224,c225,c226,c227>
= BooleanPolynomialRing(order='lex')
I = ( a111 * b111 * c111 + a112 * b112 * c112 + a113 * b113 * c113 +
a114 * b114 * c114 + a115 * b115 * c115 + a116 * b116 * c116 + a117 *
b117 * c117 -1, a111 * b111 * c121 + a112 * b112 * c122 + a113 * b113
* c123 + a114 * b114 * c124 + a115 * b115 * c125 + a116 * b116 * c126
+ a117 * b117 * c127 , a111 * b111 * c211 + a112 * b112 * c212 + a113
* b113 * c213 + a114 * b114 * c214 + a115 * b115 * c215 + a116 * b116
* c216 + a117 * b117 * c217 , a111 * b111 * c221 + a112 * b112 * c222
+ a113 * b113 * c223 + a114 * b114 * c224 + a115 * b115 * c225 + a116
* b116 * c226 + a117 * b117 * c227 , a111 * b121 * c111 + a112 * b122
* c112 + a113 * b123 * c113 + a114 * b124 * c114 + a115 * b125 * c115
+ a116 * b126 * c116 + a117 * b127 * c117 , a111 * b121 * c121 + a112
* b122 * c122 + a113 * b123 * c123 + a114 * b124 * c124 + a115 * b125
* c125 + a116 * b126 * c126 + a117 * b127 * c127 , a111 * b121 * c211
+ a112 * b122 * c212 + a113 * b123 * c213 + a114 * b124 * c214 + a115
* b125 * c215 + a116 * b126 * c216 + a117 * b127 * c217 -1, a111 *
b121 * c221 + a112 * b122 * c222 + a113 * b123 * c223 + a114 * b124 *
c224 + a115 * b125 * c225 + a116 * b126 * c226 + a117 * b127 * c227 ,
a111 * b211 * c111 + a112 * b212 * c112 + a113 * b213 * c113 + a114 *
b214 * c114 + a115 * b215 * c115 + a116 * b216 * c116 + a117 * b217 *
c117 , a111 * b211 * c121 + a112 * b212 * c122 + a113 * b213 * c123 +
a114 * b214 * c124 + a115 * b215 * c125 + a116 * b216 * c126 + a117 *
b217 * c127 , a111 * b211 * c211 + a112 * b212 * c212 + a113 * b213 *
c213 + a114 * b214 * c214 + a115 * b215 * c215 + a116 * b216 * c216 +
a117 * b217 * c217 , a111 * b211 * c221 + a112 * b212 * c222 + a113 *
b213 * c223 + a114 * b214 * c224 + a115 * b215 * c225 + a116 * b216 *
c226 + a117 * b217 * c227 , a111 * b221 * c111 + a112 * b222 * c112 +
a113 * b223 * c113 + a114 * b224 * c114 + a115 * b225 * c115 + a116 *
b226 * c116 + a117 * b227 * c117 , a111 * b221 * c121 + a112 * b222 *
c122 + a113 * b223 * c123 + a114 * b224 * c124 + a115 * b225 * c125 +
a116 * b226 * c126 + a117 * b227 * c127 , a111 * b221 * c211 + a112 *
b222 * c212 + a113 * b223 * c213 + a114 * b224 * c214 + a115 * b225 *
c215 + a116 * b226 * c216 + a117 * b227 * c217 , a111 * b221 * c221 +
a112 * b222 * c222 + a113 * b223 * c223 + a114 * b224 * c224 + a115 *
b225 * c225 + a116 * b226 * c226 + a117 * b227 * c227 , a121 * b111 *
c111 + a122 * b112 * c112 + a123 * b113 * c113 + a124 * b114 * c114 +
a125 * b115 * c115 + a126 * b116 * c116 + a127 * b117 * c117 , a121 *
b111 * c121 + a122 * b112 * c122 + a123 * b113 * c123 + a124 * b114 *
c124 + a125 * b115 * c125 + a126 * b116 * c126 + a127 * b117 * c127 ,
a121 * b111 * c211 + a122 * b112 * c212 + a123 * b113 * c213 + a124 *
b114 * c214 + a125 * b115 * c215 + a126 * b116 * c216 + a127 * b117 *
c217 , a121 * b111 * c221 + a122 * b112 * c222 + a123 * b113 * c223 +
a124 * b114 * c224 + a125 * b115 * c225 + a126 * b116 * c226 + a127 *
b117 * c227 , a121 * b121 * c111 + a122 * b122 * c112 + a123 * b123 *
c113 + a124 * b124 * c114 + a125 * b125 * c115 + a126 * b126 * c116 +
a127 * b127 * c117 , a121 * b121 * c121 + a122 * b122 * c122 + a123 *
b123 * c123 + a124 * b124 * c124 + a125 * b125 * c125 + a126 * b126 *
c126 + a127 * b127 * c127 , a121 * b121 * c211 + a122 * b122 * c212 +
a123 * b123 * c213 + a124 * b124 * c214 + a125 * b125 * c215 + a126 *
b126 * c216 + a127 * b127 * c217 , a121 * b121 * c221 + a122 * b122 *
c222 + a123 * b123 * c223 + a124 * b124 * c224 + a125 * b125 * c225 +
a126 * b126 * c226 + a127 * b127 * c227 , a121 * b211 * c111 + a122 *
b212 * c112 + a123 * b213 * c113 + a124 * b214 * c114 + a125 * b215 *
c115 + a126 * b216 * c116 + a127 * b217 * c117 -1, a121 * b211 * c121
+ a122 * b212 * c122 + a123 * b213 * c123 + a124 * b214 * c124 + a125
* b215 * c125 + a126 * b216 * c126 + a127 * b217 * c127 , a121 * b211
* c211 + a122 * b212 * c212 + a123 * b213 * c213 + a124 * b214 * c214
+ a125 * b215 * c215 + a126 * b216 * c216 + a127 * b217 * c217 , a121
* b211 * c221 + a122 * b212 * c222 + a123 * b213 * c223 + a124 * b214
* c224 + a125 * b215 * c225 + a126 * b216 * c226 + a127 * b217 *
c227 , a121 * b221 * c111 + a122 * b222 * c112 + a123 * b223 * c113 +
a124 * b224 * c114 + a125 * b225 * c115 + a126 * b226 * c116 + a127 *
b227 * c117 , a121 * b221 * c121 + a122 * b222 * c122 + a123 * b223 *
c123 + a124 * b224 * c124 + a125 * b225 * c125 + a126 * b226 * c126 +
a127 * b227 * c127 , a121 * b221 * c211 + a122 * b222 * c212 + a123 *
b223 * c213 + a124 * b224 * c214 + a125 * b225 * c215 + a126 * b226 *
c216 + a127 * b227 * c217 -1, a121 * b221 * c221 + a122 * b222 * c222
+ a123 * b223 * c223 + a124 * b224 * c224 + a125 * b225 * c225 + a126
* b226 * c226 + a127 * b227 * c227 , a211 * b111 * c111 + a212 * b112
* c112 + a213 * b113 * c113 + a214 * b114 * c114 + a215 * b115 * c115
+ a216 * b116 * c116 + a217 * b117 * c117 , a211 * b111 * c121 + a212
* b112 * c122 + a213 * b113 * c123 + a214 * b114 * c124 + a215 * b115
* c125 + a216 * b116 * c126 + a217 * b117 * c127 -1, a211 * b111 *
c211 + a212 * b112 * c212 + a213 * b113 * c213 + a214 * b114 * c214 +
a215 * b115 * c215 + a216 * b116 * c216 + a217 * b117 * c217 , a211 *
b111 * c221 + a212 * b112 * c222 + a213 * b113 * c223 + a214 * b114 *
c224 + a215 * b115 * c225 + a216 * b116 * c226 + a217 * b117 * c227 ,
a211 * b121 * c111 + a212 * b122 * c112 + a213 * b123 * c113 + a214 *
b124 * c114 + a215 * b125 * c115 + a216 * b126 * c116 + a217 * b127 *
c117 , a211 * b121 * c121 + a212 * b122 * c122 + a213 * b123 * c123 +
a214 * b124 * c124 + a215 * b125 * c125 + a216 * b126 * c126 + a217 *
b127 * c127 , a211 * b121 * c211 + a212 * b122 * c212 + a213 * b123 *
c213 + a214 * b124 * c214 + a215 * b125 * c215 + a216 * b126 * c216 +
a217 * b127 * c217 , a211 * b121 * c221 + a212 * b122 * c222 + a213 *
b123 * c223 + a214 * b124 * c224 + a215 * b125 * c225 + a216 * b126 *
c226 + a217 * b127 * c227 -1, a211 * b211 * c111 + a212 * b212 * c112
+ a213 * b213 * c113 + a214 * b214 * c114 + a215 * b215 * c115 + a216
* b216 * c116 + a217 * b217 * c117 , a211 * b211 * c121 + a212 * b212
* c122 + a213 * b213 * c123 + a214 * b214 * c124 + a215 * b215 * c125
+ a216 * b216 * c126 + a217 * b217 * c127 , a211 * b211 * c211 + a212
* b212 * c212 + a213 * b213 * c213 + a214 * b214 * c214 + a215 * b215
* c215 + a216 * b216 * c216 + a217 * b217 * c217 , a211 * b211 * c221
+ a212 * b212 * c222 + a213 * b213 * c223 + a214 * b214 * c224 + a215
* b215 * c225 + a216 * b216 * c226 + a217 * b217 * c227 , a211 * b221
* c111 + a212 * b222 * c112 + a213 * b223 * c113 + a214 * b224 * c114
+ a215 * b225 * c115 + a216 * b226 * c116 + a217 * b227 * c117 , a211
* b221 * c121 + a212 * b222 * c122 + a213 * b223 * c123 + a214 * b224
* c124 + a215 * b225 * c125 + a216 * b226 * c126 + a217 * b227 *
c127 , a211 * b221 * c211 + a212 * b222 * c212 + a213 * b223 * c213 +
a214 * b224 * c214 + a215 * b225 * c215 + a216 * b226 * c216 + a217 *
b227 * c217 , a211 * b221 * c221 + a212 * b222 * c222 + a213 * b223 *
c223 + a214 * b224 * c224 + a215 * b225 * c225 + a216 * b226 * c226 +
a217 * b227 * c227 , a221 * b111 * c111 + a222 * b112 * c112 + a223 *
b113 * c113 + a224 * b114 * c114 + a225 * b115 * c115 + a226 * b116 *
c116 + a227 * b117 * c117 , a221 * b111 * c121 + a222 * b112 * c122 +
a223 * b113 * c123 + a224 * b114 * c124 + a225 * b115 * c125 + a226 *
b116 * c126 + a227 * b117 * c127 , a221 * b111 * c211 + a222 * b112 *
c212 + a223 * b113 * c213 + a224 * b114 * c214 + a225 * b115 * c215 +
a226 * b116 * c216 + a227 * b117 * c217 , a221 * b111 * c221 + a222 *
b112 * c222 + a223 * b113 * c223 + a224 * b114 * c224 + a225 * b115 *
c225 + a226 * b116 * c226 + a227 * b117 * c227 , a221 * b121 * c111 +
a222 * b122 * c112 + a223 * b123 * c113 + a224 * b124 * c114 + a225 *
b125 * c115 + a226 * b126 * c116 + a227 * b127 * c117 , a221 * b121 *
c121 + a222 * b122 * c122 + a223 * b123 * c123 + a224 * b124 * c124 +
a225 * b125 * c125 + a226 * b126 * c126 + a227 * b127 * c127 , a221 *
b121 * c211 + a222 * b122 * c212 + a223 * b123 * c213 + a224 * b124 *
c214 + a225 * b125 * c215 + a226 * b126 * c216 + a227 * b127 * c217 ,
a221 * b121 * c221 + a222 * b122 * c222 + a223 * b123 * c223 + a224 *
b124 * c224 + a225 * b125 * c225 + a226 * b126 * c226 + a227 * b127 *
c227 , a221 * b211 * c111 + a222 * b212 * c112 + a223 * b213 * c113 +
a224 * b214 * c114 + a225 * b215 * c115 + a226 * b216 * c116 + a227 *
b217 * c117 , a221 * b211 * c121 + a222 * b212 * c122 + a223 * b213 *
c123 + a224 * b214 * c124 + a225 * b215 * c125 + a226 * b216 * c126 +
a227 * b217 * c127 -1, a221 * b211 * c211 + a222 * b212 * c212 + a223
* b213 * c213 + a224 * b214 * c214 + a225 * b215 * c215 + a226 * b216
* c216 + a227 * b217 * c217 , a221 * b211 * c221 + a222 * b212 * c222
+ a223 * b213 * c223 + a224 * b214 * c224 + a225 * b215 * c225 + a226
* b216 * c226 + a227 * b217 * c227 , a221 * b221 * c111 + a222 * b222
* c112 + a223 * b223 * c113 + a224 * b224 * c114 + a225 * b225 * c115
+ a226 * b226 * c116 + a227 * b227 * c117 , a221 * b221 * c121 + a222
* b222 * c122 + a223 * b223 * c123 + a224 * b224 * c124 + a225 * b225
* c125 + a226 * b226 * c126 + a227 * b227 * c127 , a221 * b221 * c211
+ a222 * b222 * c212 + a223 * b223 * c213 + a224 * b224 * c214 + a225
* b225 * c215 + a226 * b226 * c216 + a227 * b227 * c217 , a221 * b221
* c221 + a222 * b222 * c222 + a223 * b223 * c223 + a224 * b224 * c224
+ a225 * b225 * c225 + a226 * b226 * c226 + a227 * b227 * c227 -1)*R
I.groebner_basis()
> Finally, for solving you should use a lexicographical term ordering:
>
> sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
> BooleanPolynomialRing(order='lex')
> sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111 +
> ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112 ,
> ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
>
> sage: I.groebner_basis()
> [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
>
> Then, the Gröbner basis has a triangular shape and allows you to read the
> solution.
>
> The introduction of my Diplomarbeit describes this in more detail:
>
> http://bit.ly/B4zdThttp://sage.math.washington.edu/home/malb/thesis-1.0.pdf
>
> > Also, I read back in April that there was a plan to implement
> > Faugere's F4 algorithm.
>
> There have been numerous attempts to implement F4 efficiently in the open-
> source world but non of them succeeded to satisfaction. However, PolyBoRi's
> SlimGB algorithm is heavily inspired by F4 and you can even use linear
> algebra. PolyBoRi is used behind the scene when you construct a
> BooleanPolynomialRing.
>
example at the bottom of this message. When I try to find the
groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
memory usage goes over 1.6GB and then sage crashes. It is possible
that it just isn't realistic to solve it using Groebner Bases.
However, I should say that when reformulated as a SAT solving problem,
the standard off the shelf minisat 2.0 code can solve it in 0.04
seconds. This is despite the fact that minisat only takes CNF as the
input which means that all the structure of the problem has been
removed before it sees it.
Raphael
--- Larger example that crashes sage/polybori but which can be solved
instantly by minisat ---
R.<a111,a112,a113,a114,a115,a116,a117,a121,a122,a123,a124,a125,a126,a127,a211,a212,a213,a214,a215,a216,a217,a221,a222,a223,a224,a225,a226,a227,b111,b112,b113,b114,b115,b116,b117,b121,b122,b123,b124,b125,b126,b127,b211,b212,b213,b214,b215,b216,b217,b221,b222,b223,b224,b225,b226,b227,c111,c112,c113,c114,c115,c116,c117,c121,c122,c123,c124,c125,c126,c127,c211,c212,c213,c214,c215,c216,c217,c221,c222,c223,c224,c225,c226,c227>
= BooleanPolynomialRing(order='lex')
I = ( a111 * b111 * c111 + a112 * b112 * c112 + a113 * b113 * c113 +
a114 * b114 * c114 + a115 * b115 * c115 + a116 * b116 * c116 + a117 *
b117 * c117 -1, a111 * b111 * c121 + a112 * b112 * c122 + a113 * b113
* c123 + a114 * b114 * c124 + a115 * b115 * c125 + a116 * b116 * c126
+ a117 * b117 * c127 , a111 * b111 * c211 + a112 * b112 * c212 + a113
* b113 * c213 + a114 * b114 * c214 + a115 * b115 * c215 + a116 * b116
* c216 + a117 * b117 * c217 , a111 * b111 * c221 + a112 * b112 * c222
+ a113 * b113 * c223 + a114 * b114 * c224 + a115 * b115 * c225 + a116
* b116 * c226 + a117 * b117 * c227 , a111 * b121 * c111 + a112 * b122
* c112 + a113 * b123 * c113 + a114 * b124 * c114 + a115 * b125 * c115
+ a116 * b126 * c116 + a117 * b127 * c117 , a111 * b121 * c121 + a112
* b122 * c122 + a113 * b123 * c123 + a114 * b124 * c124 + a115 * b125
* c125 + a116 * b126 * c126 + a117 * b127 * c127 , a111 * b121 * c211
+ a112 * b122 * c212 + a113 * b123 * c213 + a114 * b124 * c214 + a115
* b125 * c215 + a116 * b126 * c216 + a117 * b127 * c217 -1, a111 *
b121 * c221 + a112 * b122 * c222 + a113 * b123 * c223 + a114 * b124 *
c224 + a115 * b125 * c225 + a116 * b126 * c226 + a117 * b127 * c227 ,
a111 * b211 * c111 + a112 * b212 * c112 + a113 * b213 * c113 + a114 *
b214 * c114 + a115 * b215 * c115 + a116 * b216 * c116 + a117 * b217 *
c117 , a111 * b211 * c121 + a112 * b212 * c122 + a113 * b213 * c123 +
a114 * b214 * c124 + a115 * b215 * c125 + a116 * b216 * c126 + a117 *
b217 * c127 , a111 * b211 * c211 + a112 * b212 * c212 + a113 * b213 *
c213 + a114 * b214 * c214 + a115 * b215 * c215 + a116 * b216 * c216 +
a117 * b217 * c217 , a111 * b211 * c221 + a112 * b212 * c222 + a113 *
b213 * c223 + a114 * b214 * c224 + a115 * b215 * c225 + a116 * b216 *
c226 + a117 * b217 * c227 , a111 * b221 * c111 + a112 * b222 * c112 +
a113 * b223 * c113 + a114 * b224 * c114 + a115 * b225 * c115 + a116 *
b226 * c116 + a117 * b227 * c117 , a111 * b221 * c121 + a112 * b222 *
c122 + a113 * b223 * c123 + a114 * b224 * c124 + a115 * b225 * c125 +
a116 * b226 * c126 + a117 * b227 * c127 , a111 * b221 * c211 + a112 *
b222 * c212 + a113 * b223 * c213 + a114 * b224 * c214 + a115 * b225 *
c215 + a116 * b226 * c216 + a117 * b227 * c217 , a111 * b221 * c221 +
a112 * b222 * c222 + a113 * b223 * c223 + a114 * b224 * c224 + a115 *
b225 * c225 + a116 * b226 * c226 + a117 * b227 * c227 , a121 * b111 *
c111 + a122 * b112 * c112 + a123 * b113 * c113 + a124 * b114 * c114 +
a125 * b115 * c115 + a126 * b116 * c116 + a127 * b117 * c117 , a121 *
b111 * c121 + a122 * b112 * c122 + a123 * b113 * c123 + a124 * b114 *
c124 + a125 * b115 * c125 + a126 * b116 * c126 + a127 * b117 * c127 ,
a121 * b111 * c211 + a122 * b112 * c212 + a123 * b113 * c213 + a124 *
b114 * c214 + a125 * b115 * c215 + a126 * b116 * c216 + a127 * b117 *
c217 , a121 * b111 * c221 + a122 * b112 * c222 + a123 * b113 * c223 +
a124 * b114 * c224 + a125 * b115 * c225 + a126 * b116 * c226 + a127 *
b117 * c227 , a121 * b121 * c111 + a122 * b122 * c112 + a123 * b123 *
c113 + a124 * b124 * c114 + a125 * b125 * c115 + a126 * b126 * c116 +
a127 * b127 * c117 , a121 * b121 * c121 + a122 * b122 * c122 + a123 *
b123 * c123 + a124 * b124 * c124 + a125 * b125 * c125 + a126 * b126 *
c126 + a127 * b127 * c127 , a121 * b121 * c211 + a122 * b122 * c212 +
a123 * b123 * c213 + a124 * b124 * c214 + a125 * b125 * c215 + a126 *
b126 * c216 + a127 * b127 * c217 , a121 * b121 * c221 + a122 * b122 *
c222 + a123 * b123 * c223 + a124 * b124 * c224 + a125 * b125 * c225 +
a126 * b126 * c226 + a127 * b127 * c227 , a121 * b211 * c111 + a122 *
b212 * c112 + a123 * b213 * c113 + a124 * b214 * c114 + a125 * b215 *
c115 + a126 * b216 * c116 + a127 * b217 * c117 -1, a121 * b211 * c121
+ a122 * b212 * c122 + a123 * b213 * c123 + a124 * b214 * c124 + a125
* b215 * c125 + a126 * b216 * c126 + a127 * b217 * c127 , a121 * b211
* c211 + a122 * b212 * c212 + a123 * b213 * c213 + a124 * b214 * c214
+ a125 * b215 * c215 + a126 * b216 * c216 + a127 * b217 * c217 , a121
* b211 * c221 + a122 * b212 * c222 + a123 * b213 * c223 + a124 * b214
* c224 + a125 * b215 * c225 + a126 * b216 * c226 + a127 * b217 *
c227 , a121 * b221 * c111 + a122 * b222 * c112 + a123 * b223 * c113 +
a124 * b224 * c114 + a125 * b225 * c115 + a126 * b226 * c116 + a127 *
b227 * c117 , a121 * b221 * c121 + a122 * b222 * c122 + a123 * b223 *
c123 + a124 * b224 * c124 + a125 * b225 * c125 + a126 * b226 * c126 +
a127 * b227 * c127 , a121 * b221 * c211 + a122 * b222 * c212 + a123 *
b223 * c213 + a124 * b224 * c214 + a125 * b225 * c215 + a126 * b226 *
c216 + a127 * b227 * c217 -1, a121 * b221 * c221 + a122 * b222 * c222
+ a123 * b223 * c223 + a124 * b224 * c224 + a125 * b225 * c225 + a126
* b226 * c226 + a127 * b227 * c227 , a211 * b111 * c111 + a212 * b112
* c112 + a213 * b113 * c113 + a214 * b114 * c114 + a215 * b115 * c115
+ a216 * b116 * c116 + a217 * b117 * c117 , a211 * b111 * c121 + a212
* b112 * c122 + a213 * b113 * c123 + a214 * b114 * c124 + a215 * b115
* c125 + a216 * b116 * c126 + a217 * b117 * c127 -1, a211 * b111 *
c211 + a212 * b112 * c212 + a213 * b113 * c213 + a214 * b114 * c214 +
a215 * b115 * c215 + a216 * b116 * c216 + a217 * b117 * c217 , a211 *
b111 * c221 + a212 * b112 * c222 + a213 * b113 * c223 + a214 * b114 *
c224 + a215 * b115 * c225 + a216 * b116 * c226 + a217 * b117 * c227 ,
a211 * b121 * c111 + a212 * b122 * c112 + a213 * b123 * c113 + a214 *
b124 * c114 + a215 * b125 * c115 + a216 * b126 * c116 + a217 * b127 *
c117 , a211 * b121 * c121 + a212 * b122 * c122 + a213 * b123 * c123 +
a214 * b124 * c124 + a215 * b125 * c125 + a216 * b126 * c126 + a217 *
b127 * c127 , a211 * b121 * c211 + a212 * b122 * c212 + a213 * b123 *
c213 + a214 * b124 * c214 + a215 * b125 * c215 + a216 * b126 * c216 +
a217 * b127 * c217 , a211 * b121 * c221 + a212 * b122 * c222 + a213 *
b123 * c223 + a214 * b124 * c224 + a215 * b125 * c225 + a216 * b126 *
c226 + a217 * b127 * c227 -1, a211 * b211 * c111 + a212 * b212 * c112
+ a213 * b213 * c113 + a214 * b214 * c114 + a215 * b215 * c115 + a216
* b216 * c116 + a217 * b217 * c117 , a211 * b211 * c121 + a212 * b212
* c122 + a213 * b213 * c123 + a214 * b214 * c124 + a215 * b215 * c125
+ a216 * b216 * c126 + a217 * b217 * c127 , a211 * b211 * c211 + a212
* b212 * c212 + a213 * b213 * c213 + a214 * b214 * c214 + a215 * b215
* c215 + a216 * b216 * c216 + a217 * b217 * c217 , a211 * b211 * c221
+ a212 * b212 * c222 + a213 * b213 * c223 + a214 * b214 * c224 + a215
* b215 * c225 + a216 * b216 * c226 + a217 * b217 * c227 , a211 * b221
* c111 + a212 * b222 * c112 + a213 * b223 * c113 + a214 * b224 * c114
+ a215 * b225 * c115 + a216 * b226 * c116 + a217 * b227 * c117 , a211
* b221 * c121 + a212 * b222 * c122 + a213 * b223 * c123 + a214 * b224
* c124 + a215 * b225 * c125 + a216 * b226 * c126 + a217 * b227 *
c127 , a211 * b221 * c211 + a212 * b222 * c212 + a213 * b223 * c213 +
a214 * b224 * c214 + a215 * b225 * c215 + a216 * b226 * c216 + a217 *
b227 * c217 , a211 * b221 * c221 + a212 * b222 * c222 + a213 * b223 *
c223 + a214 * b224 * c224 + a215 * b225 * c225 + a216 * b226 * c226 +
a217 * b227 * c227 , a221 * b111 * c111 + a222 * b112 * c112 + a223 *
b113 * c113 + a224 * b114 * c114 + a225 * b115 * c115 + a226 * b116 *
c116 + a227 * b117 * c117 , a221 * b111 * c121 + a222 * b112 * c122 +
a223 * b113 * c123 + a224 * b114 * c124 + a225 * b115 * c125 + a226 *
b116 * c126 + a227 * b117 * c127 , a221 * b111 * c211 + a222 * b112 *
c212 + a223 * b113 * c213 + a224 * b114 * c214 + a225 * b115 * c215 +
a226 * b116 * c216 + a227 * b117 * c217 , a221 * b111 * c221 + a222 *
b112 * c222 + a223 * b113 * c223 + a224 * b114 * c224 + a225 * b115 *
c225 + a226 * b116 * c226 + a227 * b117 * c227 , a221 * b121 * c111 +
a222 * b122 * c112 + a223 * b123 * c113 + a224 * b124 * c114 + a225 *
b125 * c115 + a226 * b126 * c116 + a227 * b127 * c117 , a221 * b121 *
c121 + a222 * b122 * c122 + a223 * b123 * c123 + a224 * b124 * c124 +
a225 * b125 * c125 + a226 * b126 * c126 + a227 * b127 * c127 , a221 *
b121 * c211 + a222 * b122 * c212 + a223 * b123 * c213 + a224 * b124 *
c214 + a225 * b125 * c215 + a226 * b126 * c216 + a227 * b127 * c217 ,
a221 * b121 * c221 + a222 * b122 * c222 + a223 * b123 * c223 + a224 *
b124 * c224 + a225 * b125 * c225 + a226 * b126 * c226 + a227 * b127 *
c227 , a221 * b211 * c111 + a222 * b212 * c112 + a223 * b213 * c113 +
a224 * b214 * c114 + a225 * b215 * c115 + a226 * b216 * c116 + a227 *
b217 * c117 , a221 * b211 * c121 + a222 * b212 * c122 + a223 * b213 *
c123 + a224 * b214 * c124 + a225 * b215 * c125 + a226 * b216 * c126 +
a227 * b217 * c127 -1, a221 * b211 * c211 + a222 * b212 * c212 + a223
* b213 * c213 + a224 * b214 * c214 + a225 * b215 * c215 + a226 * b216
* c216 + a227 * b217 * c217 , a221 * b211 * c221 + a222 * b212 * c222
+ a223 * b213 * c223 + a224 * b214 * c224 + a225 * b215 * c225 + a226
* b216 * c226 + a227 * b217 * c227 , a221 * b221 * c111 + a222 * b222
* c112 + a223 * b223 * c113 + a224 * b224 * c114 + a225 * b225 * c115
+ a226 * b226 * c116 + a227 * b227 * c117 , a221 * b221 * c121 + a222
* b222 * c122 + a223 * b223 * c123 + a224 * b224 * c124 + a225 * b225
* c125 + a226 * b226 * c126 + a227 * b227 * c127 , a221 * b221 * c211
+ a222 * b222 * c212 + a223 * b223 * c213 + a224 * b224 * c214 + a225
* b225 * c215 + a226 * b226 * c216 + a227 * b227 * c217 , a221 * b221
* c221 + a222 * b222 * c222 + a223 * b223 * c223 + a224 * b224 * c224
+ a225 * b225 * c225 + a226 * b226 * c226 + a227 * b227 * c227 -1)*R
I.groebner_basis()
john_perry_usm
Aug 1, 2009, 9:59:14 PM8/1/09
to sage-support, christian eder
Raphael,
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm. As the systems I want to solve are very large,
> I would be particularly interested in that or any related tools that
> are in development. (Anyone working on an XL variant?)
There is some work being done to implement F4 & F5 in Singular, which
would then make it into Sage, but the work proceeds slowly. A working
F5 implementation for Singular exists (I have a copy), but it's not
very optimized and does not use linear algebra, and so it is a little
slower than Singular's default slimgb.
If I understand correctly, they are currently working on a complete
revision of Singular's linear algebra, to allow for efficient
implementations of F4 & F5. I've forwarded this email to Christian
Eder, to whom we owe the current F5 implementation in Singular. He
will correct me if I'm wrong, & perhaps comment further.
regards
john perry
> Also, I read back in April that there was a plan to implement
> Faugere's F4 algorithm. As the systems I want to solve are very large,
> I would be particularly interested in that or any related tools that
> are in development. (Anyone working on an XL variant?)
would then make it into Sage, but the work proceeds slowly. A working
F5 implementation for Singular exists (I have a copy), but it's not
very optimized and does not use linear algebra, and so it is a little
slower than Singular's default slimgb.
If I understand correctly, they are currently working on a complete
revision of Singular's linear algebra, to allow for efficient
implementations of F4 & F5. I've forwarded this email to Christian
Eder, to whom we owe the current F5 implementation in Singular. He
will correct me if I'm wrong, & perhaps comment further.
regards
john perry
lesshaste
Aug 2, 2009, 5:16:09 AM8/2/09
to sage-support
example, if there were a way to export the presumably very large
linear algebra problem that needs to be solved, then one option would
be to run that separately on one of the many large clusters available
(over MPI say). Just a thought.
Raphael
Martin Albrecht
Aug 3, 2009, 2:25:02 PM8/3/09
to sage-s...@googlegroups.com, polybori...@lists.sourceforge.net
On Saturday 01 August 2009, Simon King wrote:
> Hi Martin,
>
> On Aug 1, 4:09 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
>
> wrote:
> > sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
> > BooleanPolynomialRing(order='lex')
> > sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111
> > + ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112
> > , ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> >
> > sage: I.groebner_basis()
> > [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
>
> Why do I get a different result? Bug in PolyBoRi, a changed
> interpretation of the meaning of "lex" (I use sage 4.1, and you?), or
> a misprint on my side (but so far I can't see any)?
> Hi Martin,
>
> On Aug 1, 4:09 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
>
> wrote:
> > sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> =
> > BooleanPolynomialRing(order='lex')
> > sage: I=(a111 * b111 * c111 + a112 * b112 * c112 - 1 , a111 * b211 * c111
> > + ....: a112 * b212 * c112 - 0 , a121 * b111 * c111 + a122 * b112 * c112
> > , ....: a121 * b211 * c111 + a122 * b212 * c112 - 1)*R
> >
> > sage: I.groebner_basis()
> > [a111 + b212, a112 + b211, a121 + b112, a122 + b111, c111 + 1, c112 + 1]
>
> Why do I get a different result? Bug in PolyBoRi, a changed
> interpretation of the meaning of "lex" (I use sage 4.1, and you?), or
> a misprint on my side (but so far I can't see any)?
I am using PolyBoRi 0.6.3 and this indeed seems to be a bug either in PolyBoRi
0.6.3 or in our Sage wrapper (most likely). I've CCed the PolyBoRi list.
Thanks for pointing this out!
Martin Albrecht
Aug 3, 2009, 2:39:36 PM8/3/09
to sage-s...@googlegroups.com
> The problem in my case is really one of scale. I have put a larger
> example at the bottom of this message. When I try to find the
> groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
> memory usage goes over 1.6GB and then sage crashes. It is possible
> that it just isn't realistic to solve it using Groebner Bases.
> However, I should say that when reformulated as a SAT solving problem,
> the standard off the shelf minisat 2.0 code can solve it in 0.04
> seconds. This is despite the fact that minisat only takes CNF as the
> input which means that all the structure of the problem has been
> removed before it sees it.
> example at the bottom of this message. When I try to find the
> groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
> memory usage goes over 1.6GB and then sage crashes. It is possible
> that it just isn't realistic to solve it using Groebner Bases.
> However, I should say that when reformulated as a SAT solving problem,
> the standard off the shelf minisat 2.0 code can solve it in 0.04
> seconds. This is despite the fact that minisat only takes CNF as the
> input which means that all the structure of the problem has been
> removed before it sees it.
Hi Raphael,
note that Gröbner basis methods will always return a complete algebraic
description of the solution set while SAT solving approaches terminate once
*one* solution is found. Thus if there are many solutions they have an
advantage. You can try to guess some variables in order to improve the
efficiency of the Gröbner basis based methods.
Cheers,
lesshaste
Aug 3, 2009, 3:54:55 PM8/3/09
to sage-support
Hi,
On Aug 3, 7:39 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
there are in fact a really large number of solutions.
However ( :) ) attached below is another slightly smaller example
where there is in fact no solution, making it a fairer comparison I
hope. It takes minisat 2 mins 22 seconds on my computer to work that
out. Using polybori in sage as above takes 700-800MB of RAM and
doesn't terminate in the hour or so I gave it. I only mention this in
case anyone working on polybori is interested in specific examples.
Raphael
---- attached system of polys with no solution ---
R.<a111,a112,a113,a114,a115,a116,a121,a122,a123,a124,a125,a126,a211,a212,a213,a214,a215,a216,a221,a222,a223,a224,a225,a226,b111,b112,b113,b114,b115,b116,b121,b122,b123,b124,b125,b126,b211,b212,b213,b214,b215,b216,b221,b222,b223,b224,b225,b226,c111,c112,c113,c114,c115,c116,c121,c122,c123,c124,c125,c126,c211,c212,c213,c214,c215,c216,c221,c222,c223,c224,c225,c226
+ a114 * b124 * c124 + a115 * b125 * c125 + a116 * b126 * c126 , a111
c213 + a114 * b214 * c214 + a115 * b215 * c215 + a116 * b216 * c216 ,
c223 + a114 * b224 * c224 + a115 * b225 * c225 + a116 * b226 * c226 ,
c113 + a124 * b124 * c114 + a125 * b125 * c115 + a126 * b126 * c116 ,
a124 * b214 * c214 + a125 * b215 * c215 + a126 * b216 * c216 , a121 *
+ a124 * b224 * c224 + a125 * b225 * c225 + a126 * b226 * c226 , a211
c113 + a214 * b124 * c114 + a215 * b125 * c115 + a216 * b126 * c116 ,
a214 * b214 * c214 + a215 * b215 * c215 + a216 * b216 * c216 , a211 *
a214 * b224 * c224 + a215 * b225 * c225 + a216 * b226 * c226 , a221 *
a224 * b124 * c114 + a225 * b125 * c115 + a226 * b126 * c116 , a221 *
a224 * b214 * c124 + a225 * b215 * c125 + a226 * b216 * c126 -1, a221
+ a224 * b224 * c214 + a225 * b225 * c215 + a226 * b226 * c216 , a221
I.groebner_basis()
On Aug 3, 7:39 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
> > The problem in my case is really one of scale. I have put a larger
> > example at the bottom of this message. When I try to find the
> > groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
> > memory usage goes over 1.6GB and then sage crashes. It is possible
> > that it just isn't realistic to solve it using Groebner Bases.
> > However, I should say that when reformulated as a SAT solving problem,
> > the standard off the shelf minisat 2.0 code can solve it in 0.04
> > seconds. This is despite the fact that minisat only takes CNF as the
> > input which means that all the structure of the problem has been
> > removed before it sees it.
>
> Hi Raphael,
>
> note that Gröbner basis methods will always return a complete algebraic
> description of the solution set while SAT solving approaches terminate once
> *one* solution is found. Thus if there are many solutions they have an
> advantage. You can try to guess some variables in order to improve the
> efficiency of the Gröbner basis based methods.
>
You are quite right of course. My example wasn't fair as in this case
> > example at the bottom of this message. When I try to find the
> > groebner basis in sage 4.1 (which seems to use polybori-0.5rc.p8) the
> > memory usage goes over 1.6GB and then sage crashes. It is possible
> > that it just isn't realistic to solve it using Groebner Bases.
> > However, I should say that when reformulated as a SAT solving problem,
> > the standard off the shelf minisat 2.0 code can solve it in 0.04
> > seconds. This is despite the fact that minisat only takes CNF as the
> > input which means that all the structure of the problem has been
> > removed before it sees it.
>
> Hi Raphael,
>
> note that Gröbner basis methods will always return a complete algebraic
> description of the solution set while SAT solving approaches terminate once
> *one* solution is found. Thus if there are many solutions they have an
> advantage. You can try to guess some variables in order to improve the
> efficiency of the Gröbner basis based methods.
>
there are in fact a really large number of solutions.
However ( :) ) attached below is another slightly smaller example
where there is in fact no solution, making it a fairer comparison I
hope. It takes minisat 2 mins 22 seconds on my computer to work that
out. Using polybori in sage as above takes 700-800MB of RAM and
doesn't terminate in the hour or so I gave it. I only mention this in
case anyone working on polybori is interested in specific examples.
Raphael
---- attached system of polys with no solution ---
R.<a111,a112,a113,a114,a115,a116,a121,a122,a123,a124,a125,a126,a211,a212,a213,a214,a215,a216,a221,a222,a223,a224,a225,a226,b111,b112,b113,b114,b115,b116,b121,b122,b123,b124,b125,b126,b211,b212,b213,b214,b215,b216,b221,b222,b223,b224,b225,b226,c111,c112,c113,c114,c115,c116,c121,c122,c123,c124,c125,c126,c211,c212,c213,c214,c215,c216,c221,c222,c223,c224,c225,c226
> = BooleanPolynomialRing(order='lex')
I = ( a111 * b111 * c111 + a112 * b112 * c112 + a113 * b113 * c113 +
a114 * b114 * c114 + a115 * b115 * c115 + a116 * b116 * c116 -1, a111
I = ( a111 * b111 * c111 + a112 * b112 * c112 + a113 * b113 * c113 +
* b111 * c121 + a112 * b112 * c122 + a113 * b113 * c123 + a114 * b114
* c124 + a115 * b115 * c125 + a116 * b116 * c126 , a111 * b111 * c211
+ a112 * b112 * c212 + a113 * b113 * c213 + a114 * b114 * c214 + a115
* b115 * c215 + a116 * b116 * c216 , a111 * b111 * c221 + a112 * b112
* c222 + a113 * b113 * c223 + a114 * b114 * c224 + a115 * b115 * c225
+ a116 * b116 * c226 , a111 * b121 * c111 + a112 * b122 * c112 + a113
* b123 * c113 + a114 * b124 * c114 + a115 * b125 * c115 + a116 * b126
* c116 , a111 * b121 * c121 + a112 * b122 * c122 + a113 * b123 * c123
+ a114 * b124 * c124 + a115 * b125 * c125 + a116 * b126 * c126 , a111
* b121 * c211 + a112 * b122 * c212 + a113 * b123 * c213 + a114 * b124
* c214 + a115 * b125 * c215 + a116 * b126 * c216 -1, a111 * b121 *
c221 + a112 * b122 * c222 + a113 * b123 * c223 + a114 * b124 * c224 +
a115 * b125 * c225 + a116 * b126 * c226 , a111 * b211 * c111 + a112 *
b212 * c112 + a113 * b213 * c113 + a114 * b214 * c114 + a115 * b215 *
c115 + a116 * b216 * c116 , a111 * b211 * c121 + a112 * b212 * c122 +
a113 * b213 * c123 + a114 * b214 * c124 + a115 * b215 * c125 + a116 *
b216 * c126 , a111 * b211 * c211 + a112 * b212 * c212 + a113 * b213 *
c213 + a114 * b214 * c214 + a115 * b215 * c215 + a116 * b216 * c216 ,
a111 * b211 * c221 + a112 * b212 * c222 + a113 * b213 * c223 + a114 *
b214 * c224 + a115 * b215 * c225 + a116 * b216 * c226 , a111 * b221 *
c111 + a112 * b222 * c112 + a113 * b223 * c113 + a114 * b224 * c114 +
a115 * b225 * c115 + a116 * b226 * c116 , a111 * b221 * c121 + a112 *
b222 * c122 + a113 * b223 * c123 + a114 * b224 * c124 + a115 * b225 *
c125 + a116 * b226 * c126 , a111 * b221 * c211 + a112 * b222 * c212 +
a113 * b223 * c213 + a114 * b224 * c214 + a115 * b225 * c215 + a116 *
b226 * c216 , a111 * b221 * c221 + a112 * b222 * c222 + a113 * b223 *
c223 + a114 * b224 * c224 + a115 * b225 * c225 + a116 * b226 * c226 ,
a121 * b111 * c111 + a122 * b112 * c112 + a123 * b113 * c113 + a124 *
b114 * c114 + a125 * b115 * c115 + a126 * b116 * c116 , a121 * b111 *
c121 + a122 * b112 * c122 + a123 * b113 * c123 + a124 * b114 * c124 +
a125 * b115 * c125 + a126 * b116 * c126 , a121 * b111 * c211 + a122 *
b112 * c212 + a123 * b113 * c213 + a124 * b114 * c214 + a125 * b115 *
c215 + a126 * b116 * c216 , a121 * b111 * c221 + a122 * b112 * c222 +
a123 * b113 * c223 + a124 * b114 * c224 + a125 * b115 * c225 + a126 *
b116 * c226 , a121 * b121 * c111 + a122 * b122 * c112 + a123 * b123 *
c113 + a124 * b124 * c114 + a125 * b125 * c115 + a126 * b126 * c116 ,
a121 * b121 * c121 + a122 * b122 * c122 + a123 * b123 * c123 + a124 *
b124 * c124 + a125 * b125 * c125 + a126 * b126 * c126 , a121 * b121 *
c211 + a122 * b122 * c212 + a123 * b123 * c213 + a124 * b124 * c214 +
a125 * b125 * c215 + a126 * b126 * c216 , a121 * b121 * c221 + a122 *
b122 * c222 + a123 * b123 * c223 + a124 * b124 * c224 + a125 * b125 *
c225 + a126 * b126 * c226 , a121 * b211 * c111 + a122 * b212 * c112 +
a123 * b213 * c113 + a124 * b214 * c114 + a125 * b215 * c115 + a126 *
b216 * c116 -1, a121 * b211 * c121 + a122 * b212 * c122 + a123 * b213
* c123 + a124 * b214 * c124 + a125 * b215 * c125 + a126 * b216 *
c126 , a121 * b211 * c211 + a122 * b212 * c212 + a123 * b213 * c213 +
a124 * b214 * c214 + a125 * b215 * c215 + a126 * b216 * c216 , a121 *
b211 * c221 + a122 * b212 * c222 + a123 * b213 * c223 + a124 * b214 *
c224 + a125 * b215 * c225 + a126 * b216 * c226 , a121 * b221 * c111 +
a122 * b222 * c112 + a123 * b223 * c113 + a124 * b224 * c114 + a125 *
b225 * c115 + a126 * b226 * c116 , a121 * b221 * c121 + a122 * b222 *
c122 + a123 * b223 * c123 + a124 * b224 * c124 + a125 * b225 * c125 +
a126 * b226 * c126 , a121 * b221 * c211 + a122 * b222 * c212 + a123 *
b223 * c213 + a124 * b224 * c214 + a125 * b225 * c215 + a126 * b226 *
c216 -1, a121 * b221 * c221 + a122 * b222 * c222 + a123 * b223 * c223
+ a124 * b224 * c224 + a125 * b225 * c225 + a126 * b226 * c226 , a211
* b111 * c111 + a212 * b112 * c112 + a213 * b113 * c113 + a214 * b114
* c114 + a215 * b115 * c115 + a216 * b116 * c116 , a211 * b111 * c121
+ a212 * b112 * c122 + a213 * b113 * c123 + a214 * b114 * c124 + a215
* b115 * c125 + a216 * b116 * c126 -1, a211 * b111 * c211 + a212 *
b112 * c212 + a213 * b113 * c213 + a214 * b114 * c214 + a215 * b115 *
c215 + a216 * b116 * c216 , a211 * b111 * c221 + a212 * b112 * c222 +
a213 * b113 * c223 + a214 * b114 * c224 + a215 * b115 * c225 + a216 *
b116 * c226 , a211 * b121 * c111 + a212 * b122 * c112 + a213 * b123 *
c113 + a214 * b124 * c114 + a215 * b125 * c115 + a216 * b126 * c116 ,
a211 * b121 * c121 + a212 * b122 * c122 + a213 * b123 * c123 + a214 *
b124 * c124 + a215 * b125 * c125 + a216 * b126 * c126 , a211 * b121 *
c211 + a212 * b122 * c212 + a213 * b123 * c213 + a214 * b124 * c214 +
a215 * b125 * c215 + a216 * b126 * c216 , a211 * b121 * c221 + a212 *
b122 * c222 + a213 * b123 * c223 + a214 * b124 * c224 + a215 * b125 *
c225 + a216 * b126 * c226 -1, a211 * b211 * c111 + a212 * b212 * c112
+ a213 * b213 * c113 + a214 * b214 * c114 + a215 * b215 * c115 + a216
* b216 * c116 , a211 * b211 * c121 + a212 * b212 * c122 + a213 * b213
* c123 + a214 * b214 * c124 + a215 * b215 * c125 + a216 * b216 *
c126 , a211 * b211 * c211 + a212 * b212 * c212 + a213 * b213 * c213 +
a214 * b214 * c214 + a215 * b215 * c215 + a216 * b216 * c216 , a211 *
b211 * c221 + a212 * b212 * c222 + a213 * b213 * c223 + a214 * b214 *
c224 + a215 * b215 * c225 + a216 * b216 * c226 , a211 * b221 * c111 +
a212 * b222 * c112 + a213 * b223 * c113 + a214 * b224 * c114 + a215 *
b225 * c115 + a216 * b226 * c116 , a211 * b221 * c121 + a212 * b222 *
c122 + a213 * b223 * c123 + a214 * b224 * c124 + a215 * b225 * c125 +
a216 * b226 * c126 , a211 * b221 * c211 + a212 * b222 * c212 + a213 *
b223 * c213 + a214 * b224 * c214 + a215 * b225 * c215 + a216 * b226 *
c216 , a211 * b221 * c221 + a212 * b222 * c222 + a213 * b223 * c223 +
a214 * b224 * c224 + a215 * b225 * c225 + a216 * b226 * c226 , a221 *
b111 * c111 + a222 * b112 * c112 + a223 * b113 * c113 + a224 * b114 *
c114 + a225 * b115 * c115 + a226 * b116 * c116 , a221 * b111 * c121 +
a222 * b112 * c122 + a223 * b113 * c123 + a224 * b114 * c124 + a225 *
b115 * c125 + a226 * b116 * c126 , a221 * b111 * c211 + a222 * b112 *
c212 + a223 * b113 * c213 + a224 * b114 * c214 + a225 * b115 * c215 +
a226 * b116 * c216 , a221 * b111 * c221 + a222 * b112 * c222 + a223 *
b113 * c223 + a224 * b114 * c224 + a225 * b115 * c225 + a226 * b116 *
c226 , a221 * b121 * c111 + a222 * b122 * c112 + a223 * b123 * c113 +
a224 * b124 * c114 + a225 * b125 * c115 + a226 * b126 * c116 , a221 *
b121 * c121 + a222 * b122 * c122 + a223 * b123 * c123 + a224 * b124 *
c124 + a225 * b125 * c125 + a226 * b126 * c126 , a221 * b121 * c211 +
a222 * b122 * c212 + a223 * b123 * c213 + a224 * b124 * c214 + a225 *
b125 * c215 + a226 * b126 * c216 , a221 * b121 * c221 + a222 * b122 *
c222 + a223 * b123 * c223 + a224 * b124 * c224 + a225 * b125 * c225 +
a226 * b126 * c226 , a221 * b211 * c111 + a222 * b212 * c112 + a223 *
b213 * c113 + a224 * b214 * c114 + a225 * b215 * c115 + a226 * b216 *
c116 , a221 * b211 * c121 + a222 * b212 * c122 + a223 * b213 * c123 +
a224 * b214 * c124 + a225 * b215 * c125 + a226 * b216 * c126 -1, a221
* b211 * c211 + a222 * b212 * c212 + a223 * b213 * c213 + a224 * b214
* c214 + a225 * b215 * c215 + a226 * b216 * c216 , a221 * b211 * c221
+ a222 * b212 * c222 + a223 * b213 * c223 + a224 * b214 * c224 + a225
* b215 * c225 + a226 * b216 * c226 , a221 * b221 * c111 + a222 * b222
* c112 + a223 * b223 * c113 + a224 * b224 * c114 + a225 * b225 * c115
+ a226 * b226 * c116 , a221 * b221 * c121 + a222 * b222 * c122 + a223
* b223 * c123 + a224 * b224 * c124 + a225 * b225 * c125 + a226 * b226
* c126 , a221 * b221 * c211 + a222 * b222 * c212 + a223 * b223 * c213
+ a224 * b224 * c214 + a225 * b225 * c215 + a226 * b226 * c216 , a221
* b221 * c221 + a222 * b222 * c222 + a223 * b223 * c223 + a224 * b224
* c224 + a225 * b225 * c225 + a226 * b226 * c226 -1)*R
I.groebner_basis()
Michael Brickenstein
Aug 3, 2009, 4:12:54 PM8/3/09
to sage-support
Hi!
I can't sleep, when fearing PolyBoRi could calculate wrong:
Actually, it's probably just about the wrapper.
My CVS, which is very much the same as 0.6.3 gives me:
l="a111,a112,a121,a122,b111,b112,b211,b212,c111,c112".split(",")
In [2]:declare_ring(l, globals())
Out[2]:<polybori.dynamic.PyPolyBoRi.Ring object at 0xb02578>
In [3]:ideal=[a111 * b111 * c111 + a112 * b112 * c112 + 1 , a111 *
b211 * c111 +
...: a112 * b212 * c112 + 0 , a121 * b111 * c111 + a122 * b112 *
c112 , ...: a121 * b211 * c111 + a122 * b212 * c112 + 1]
In [4]:grogroebner/CVS groebner/libgroebner.a groebner/
src
groebner/doc groebner/libgroebner.so groebner_basis
In [4]:groebner_basis(ideal)
Out[4]:
[b211*b212 + b211 + b212 + 1,
b112*b212 + b112 + b212 + 1,
b111*b112 + b111 + b112 + 1,
a122 + b111,
a121 + b112,
a112 + b211,
a111 + b212,
tweaks.
Can you send it as proper attachment it to me? What kind of
application is it?
Michael
> + a226 * b226 * c116 , a221 * b221 * c121 + a222 * ...
>
> Erfahren Sie mehr »
I can't sleep, when fearing PolyBoRi could calculate wrong:
Actually, it's probably just about the wrapper.
My CVS, which is very much the same as 0.6.3 gives me:
l="a111,a112,a121,a122,b111,b112,b211,b212,c111,c112".split(",")
In [2]:declare_ring(l, globals())
Out[2]:<polybori.dynamic.PyPolyBoRi.Ring object at 0xb02578>
In [3]:ideal=[a111 * b111 * c111 + a112 * b112 * c112 + 1 , a111 *
b211 * c111 +
...: a112 * b212 * c112 + 0 , a121 * b111 * c111 + a122 * b112 *
c112 , ...: a121 * b211 * c111 + a122 * b212 * c112 + 1]
In [4]:grogroebner/CVS groebner/libgroebner.a groebner/
src
groebner/doc groebner/libgroebner.so groebner_basis
In [4]:groebner_basis(ideal)
Out[4]:
[b211*b212 + b211 + b212 + 1,
b112*b212 + b112 + b212 + 1,
b111*b212 + b112*b211 + 1,
b111*b211 + b111 + b211 + 1,
b111*b112 + b111 + b112 + 1,
a122 + b111,
a121 + b112,
a112 + b211,
a111 + b212,
c111 + 1,
c112 + 1]
Tomorrow, I'll have a look at the bigger system, if there are some
c112 + 1]
tweaks.
Can you send it as proper attachment it to me? What kind of
application is it?
Michael
>
> Erfahren Sie mehr »
Michael Brickenstein
Aug 4, 2009, 3:46:01 AM8/4/09
to sage-support
Hi!
I think the problem is quite hard using Gröbner bases, I also talked
to Gregory Bard about the topic in Sage days 10.
Nevertheless it is interesting.
Did you convert the polynomial system to cnf using Martins converter.
Does it also solve the bigger problem, you gave me?
Can you please give me some code snippet for the conversion?
I'd like to have some look into it.
I think Gregory said, the full problem is resistant against all
general sort of tricks and
algorithms.
From what I understand about the algorithm, it is obvious, that you
can fix some ones or at least one, as it is highly symmetric.
Michael
> ...
>
> Erfahren Sie mehr »
I think the problem is quite hard using Gröbner bases, I also talked
to Gregory Bard about the topic in Sage days 10.
Nevertheless it is interesting.
Did you convert the polynomial system to cnf using Martins converter.
Does it also solve the bigger problem, you gave me?
Can you please give me some code snippet for the conversion?
I'd like to have some look into it.
I think Gregory said, the full problem is resistant against all
general sort of tricks and
algorithms.
From what I understand about the algorithm, it is obvious, that you
can fix some ones or at least one, as it is highly symmetric.
Michael
>
> Erfahren Sie mehr »
Reply all
Reply to author
Forward
0 new messages