# Does anyone know how to implement a simple XL Algorithm in sage?

I need to implement the XL algorithm in sage, which i can use to solve over-determined systems of polynomial equations (more equations than variables). Any help on how to do this?

edit retag close merge delete

Is this relevant:

http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/multi_polynomial_sequence.html

Here, there is a line...

Using these building blocks we can implement a simple XL algorithm easily:

( 2018-03-29 15:07:57 +0200 )edit

I have had a look at that but i don't really understand what is going on there because it doesn't seem to provide a solution, also i need to do it for a polynomial system. They define a polynomial system with the following

sr = mq.SR(1,1,1,4, gf2=True, polybori=True, order='lex')

F,s = sr.polynomial_system()and i don't really get what kind of polynomial system has actually been implemented there :/

( 2018-03-29 15:40:59 +0200 )edit

The structure in encapsulated. To see the $36$ polynomials in F:

for pol in F: print pol


There are 20 variables in F.variables(). So there are $\binom{20}2=190$ monomials $ab$, where $a,b$ are variables, $a\ne b$.

Then we build F2 = Sequence(map(mul, cartesian_product_iterator((monomials, F)))). The cartesian product of all monomials $ab$ and all pols $f$ has then $190\cdot 36$ elements, we map them via mul getting all$ab\;f$ of this shape.

The tricky F2.coefficient_matrix(sparse=False) isolates the corresponding matrix, try F2.coefficient_matrix? to see in examples how this works.

From here, standard linear algebra gets the hands on it...

This example may not be related to the own problem, but then we have to know this other problem / situation.

( 2018-03-30 03:56:50 +0200 )edit