Ask Your Question
0

Correct way to compute the modulus of a polynomial

asked 2016-03-20 08:47:17 -0500

Jernej gravatar image

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 flag offensive close merge delete

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 gravatar imageslelievre ( 2016-03-20 15:02:17 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-03-20 09:02:41 -0500

B r u n o gravatar image

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 more

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 gravatar imageJernej ( 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.

B r u n o gravatar imageB r u n o ( 2016-03-21 08:13:27 -0500 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-03-20 08:47:17 -0500

Seen: 127 times

Last updated: Mar 20 '16