# Correct way to compute the modulus of a polynomial

I am dealing with a large list of monomials of degree 1. One such (small) example would be

x0x2x3x4 + x1x2x3x4 - x0x2x3 - x1x2x3 - x0x3x4 - x1x3x4 + x2x3x4 + x0x3 + x1x3 - x2x3 - x3x4 + x3

I need to create a dict that, encodes each of the above summands (recording the respective variable indices) and the respective value of the coefficient. So for the above expression I'd like to make the dictionary:

{'0,2,3': -1, '0,2,3,4': 1, '0,3': 1, '0,3,4': -1, '1,2,3': -1, '1,2,3,4': 1, '1,3': 1, '1,3,4': -1, '2,3': -1, '2,3,4': 1, '3': 1, '3,4': -1}

I would like this to be as efficient as possible. As far as I understand it is not possible to use coefficients() to return this and the only way I see how to accomplish this is by converting the expression to a string and parse it. Given that this is quite inefficient and ugly I was wondering

What would be an efficient way to extract the described dictionary from a given monomial expression?

edit retag close merge delete

To display blocks of code, indent the corresponding lines by 4 spaces. Alternatively, select the lines of code and click the "code" button (the one with '101 010').

( 2016-03-20 15:02:17 -0500 )edit

Sort by » oldest newest most voted

The correct way is to define the polynomial ring in which your polynomial lives, and then use the method dict(). For instance:

sage: R.<x0,x1,x2,x3,x4> = QQ[] # polynomials in x0, ..., x4 over the field of rational numbers
sage: p = x0*x2*x3*x4 + x1*x2*x3*x4 - x0*x2*x3 - x1*x2*x3 - x0*x3*x4 - x1*x3*x4 + x2*x3*x4 + x0*x3 + x1*x3 - x2*x3 - x3*x4 + x3
sage: p.dict()
{(0, 0, 0, 1, 0): 1,
(0, 0, 0, 1, 1): -1,
(0, 0, 1, 1, 0): -1,
(0, 0, 1, 1, 1): 1,
(0, 1, 0, 1, 0): 1,
(0, 1, 0, 1, 1): -1,
(0, 1, 1, 1, 0): -1,
(0, 1, 1, 1, 1): 1,
(1, 0, 0, 1, 0): 1,
(1, 0, 0, 1, 1): -1,
(1, 0, 1, 1, 0): -1,
(1, 0, 1, 1, 1): 1}


Now you can parse the ductionary to replace (1,0,0,1,0) by (0,3) for instance.

sage: dict1 = p.dict()
sage: dict2 = { tuple(i for i in range(5) if k[i] == 1): dict1[k] for k in dict1 }
sage: dict2
{(0, 2, 3): -1,
(0, 2, 3, 4): 1,
(0, 3): 1,
(0, 3, 4): -1,
(1, 2, 3): -1,
(1, 2, 3, 4): 1,
(1, 3): 1,
(1, 3, 4): -1,
(2, 3): -1,
(2, 3, 4): 1,
(3,): 1,
(3, 4): -1}

more

@Bruno Is there a way to use this when the variables in question are given in a list V of the form V = [var('x'+str(i)) for i in xrange(n)] ?

( 2016-03-20 13:28:11 -0500 )edit

It depends what you want: First, you can define your polynomial ring in a more programmatic way as follows:

sage: R = PolynomialRing(QQ, 'x', 5) # 5 is the number of variables


Then, you can use the method inject_variables to define the (Python) variables x0, ..., x5 to represent the (polynomial ring) indeterminates:

sage: R.inject_variables()


The second option is if you really want (or need) that the variables are symbolic variables (instead of polynomial indeterminates). Then you still define the polynomial ring as above but you do not use inject_variables. Now if you have a polynomial p defined over the symbolic variables (defined in V), you can convert it to a polynomial with R(p), and use the code of my answer.

( 2016-03-21 08:13:27 -0500 )edit