Groebner basis to solve linear system of equations

Anonymous

I am trying to solve a linear system of equation modulo some prime $p$ . I have a matrix which gives me the coefficients of the polynomials (i.e., first row would be ( $a, c, b, d$ ) for $ax+by+cz+d =0$ ). I would usually use solve_right(), writing my system as $Ax=b$ mod $p$ , but I am intrigued by the use of Groebner basis. I have read about their implementation but I am confused at the notion of ideal to define before solving the system. I would like to solve the system in the ring $Z/pZ$ . Also, can I feed a matrix to the function or should I first convert the matrix in a bunch of equations ? Any clarification would be welcome !

answered 7 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

Groebner bases are somehow overkill: they are used for polynomial systems (involving equations like $ax^3y^4+by^5z+cxz+d=0$ ).

Here your system is linear, so linear algebra (matrix computations) is definitely the appropriate tool. It is much faster, can handle larger system, etc.

If you want to work modulo some prime p, you should define your matrices over the finite field GF(p):

sage: matrix(GF(5), [[1, 2, 4, 2], [2, 4, 4, 0], [0, 4, 4, 1], [2, 0, 0, 2]])

If you really want to use ideals, you can easily define your polynomials over GF(p), here is an example:

sage: R.<x,y,z> = PolynomialRing(GF(5)) ; R
Multivariate Polynomial Ring in x, y, z over Finite Field of size 5
sage: P = 2*x+3*y+5*z+2
sage: Q = 2*x+y+5*z+2
sage: S = x+y+z
sage: I = R.ideal([P,Q,S]) ; I
Ideal (2*x - 2*y + 2, 2*x + y + 2, x + y + z) of Multivariate Polynomial Ring in x, y, z over Finite Field of size 5
sage: I.variety()
[{y: 0, z: 1, x: 4}]

Note that when the variety is not zero dimensional, you might encounter issues.

sage: I = R.ideal([P,Q])
sage: I.variety()
ValueError: The dimension of the ideal is 1, but it should be 0

In linear words, this case corresponds to to having a non-trivial kernel, a case that is very well handled with matrices, see the following list of examples:

link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Groebner basis to solve linear system of equations

1 Answer

Your Answer

Question Tools

Stats

Related questions

Groebner basis to solve linear system of equations savecancel

1 Answer

Your Answer

Question Tools

Stats

Related questions

Groebner basis to solve linear system of equations