Correct way to compute the modulus of a polynomial

asked 2016-03-20 14:47:17 +0200

Jernej
67 ●3 ●4 ●12

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?

Comments

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').

slelievre ( 2016-03-20 21:02:17 +0200 )edit

add a comment

answered 2016-03-20 15:02:41 +0200

B r u n o
1603 ●5 ●21 ●43

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}

edit flag offensive delete link

Comments

@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)] ?

Jernej ( 2016-03-20 19:28:11 +0200 )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.

B r u n o ( 2016-03-21 14:13:27 +0200 )edit

add a comment

Your Answer

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

Correct way to compute the modulus of a polynomial

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Correct way to compute the modulus of a polynomial edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Correct way to compute the modulus of a polynomial