Ask Your Question
2

Reduce multivariate polynomial coefficients to 1

asked 2016-12-02 12:45:15 +0100

Natassa Theodouli gravatar image

Hi all,

I'm new to Python and SAGE and would like to ask a question: I have a multivariate polynomial, of a degree 3, i.e:

g.<x1,x2,x3>=x1^2 + 2x1x2 + x2^2 + 2x1x3 + 2x2x3 + x3^2 + 2x1 + 2x2 + 2*x3 + 1 Its type is <type 'sage.rings.polynomial.multi_polynomial_libsingular.mpolynomial_libsingu\="" lar'="">

The question is how can I reduce all its leading coefficients to 1, i.e. transform ig to:

g.<x1,x2,x3>=x1^2 + x1x2 + x2^2 + x1x3 + x2x3 + x3^2 + *x1 + *x2 + *x3 + 1

I tried to get the coefficients of the polynomial (which is a list), iterate through its items, and set the values of the items to 1, i.e.

for s in g.coefficients(): if s==2: s=1

I think that the problem is that list items can't be cast to integer (TypeError).

How could I solve this? Is there a more efficient way to do this? Thank you for your responses! Regards, Natassa

edit retag flag offensive close merge delete

Comments

If speed matters, see compared timings in my answer.

slelievre gravatar imageslelievre ( 2016-12-22 14:29:26 +0100 )edit

To display blocks of code, separate them by a blank line from the rest of the text, and either indent them with 4 spaces, or select the corresponding lines and click the "code" button (the icon with '101 010').

Can you edit your question to do that?

slelievre gravatar imageslelievre ( 2016-12-22 14:33:04 +0100 )edit

4 Answers

Sort by » oldest newest most voted
1

answered 2016-12-02 16:41:36 +0100

tmonteil gravatar image

The shortest way i could think of is to sum its nonzero monomials:

Setup:

sage: R = PolynomialRing(ZZ,'x',4)
sage: R.inject_variables()
Defining x0, x1, x2, x3
sage: g = x1^2 + 2*x1*x2 + x2^2 + 2*x1*x3 + 2*x2*x3 + x3^2 + 2*x1 + 2*x2 + 2*x3 + 1
sage: g
x1^2 + 2*x1*x2 + x2^2 + 2*x1*x3 + 2*x2*x3 + x3^2 + 2*x1 + 2*x2 + 2*x3 + 1

Then:

sage: sum(g.monomials())
x1^2 + x1*x2 + x2^2 + x1*x3 + x2*x3 + x3^2 + x1 + x2 + x3 + 1
edit flag offensive delete link more
1

answered 2016-12-09 12:45:50 +0100

slelievre gravatar image

Reducing coefficients to one for multivariate polynomials

Taking the sum of monomials as suggested in the other answers works fine.

It is however faster to map all coefficients to one using map_coefficients.

Context

sage: R.<x1, x2, x3> = QQbar[]
sage: P = x1^2 + 2*x1*x2 + x2^2 + 2*x1*x3 + 2*x2*x3 + x3^2 + 2*x1 + 2*x2 + 2*x3 + 1

First approach: summing monomials

Summing monomials using the monomials method:

sage: sum(P.monomials())
x1^2 + x1*x2 + x2^2 + x1*x3 + x2*x3 + x3^2 + x1 + x2 + x3 + 1

Summing monomials iterating through the polynomial's coefficients and monomials:

sage: sum(m for c, m in P)
x1^2 + x1*x2 + x2^2 + x1*x3 + x2*x3 + x3^2 + x1 + x2 + x3 + 1

Second approach: applying a map to coefficients

Using map_coefficients and plain 1:

sage: P.map_coefficients(lambda _: 1)
x1^2 + x1*x2 + x2^2 + x1*x3 + x2*x3 + x3^2 + x1 + x2 + x3 + 1

Using map_coefficients and QQbar's version of 1.

sage: QQbar_one = QQbar.one()
sage: to_QQbar_one = lambda _: QQbar_one
sage: P.map_coefficients(to_QQbar_one)
x1^2 + x1*x2 + x2^2 + x1*x3 + x2*x3 + x3^2 + x1 + x2 + x3 + 1

Timings

Summing the monomials one way or another takes on the order of 700 µs.

sage: timeit('sum(P.monomials())')
625 loops, best of 3: 678 µs per loop

sage: timeit('sum(m for c, m in P)')
625 loops, best of 3: 682 µs per loop

Using map_coefficients is roughly ten times faster.

sage: QQbar_one = QQbar.one()
sage: to_QQbar_one = lambda _: QQbar_one
sage: timeit('P.map_coefficients(to_QQbar_one)')
625 loops, best of 3: 68.1 µs per loop

Note that the more naïve version wastes time since 1 gets converted to QQbar's 1 for each coefficient.

sage: timeit('P.map_coefficients(lambda _: 1)')
625 loops, best of 3: 139 µs per loop

Further remarks

Depending on how the reduced polynomials are used later on, it might make more sense to change their base ring to some version of the boolean ring.

edit flag offensive delete link more
1

answered 2016-12-03 12:23:41 +0100

Natassa Theodouli gravatar image

Thank you all,

Indeed, considering sum of all monomials does the trick! As a reference, a slightly tweaked solution below that worked for me:

g # the polynomial 
list(g) # convert polynomial to list
g1=sum(mon for coeff, mon in g) # get the sum of all monomials
edit flag offensive delete link more
1

answered 2016-12-02 16:36:31 +0100

B r u n o gravatar image

updated 2016-12-02 16:39:41 +0100

The code you provide is not valid, so I don't think this is what you have... The example below show the definition of a polynomial ring, a random polynomial from this ring, and then the polynomial with all coefficients replaced by $1$. The idea is to get the list of monomials, and then simply sum this list.

sage: R.<x1, x2, x3> = QQ[] # polynomial ring over QQ
sage: g = R.random_element(10) # random polynomial of degree 10
sage: g
3*x1^4*x2^5*x3 - 4*x1^7*x2*x3 + 8*x1*x2^7*x3 + 1/3*x1^4*x3^5 - 5*x1^6*x3
sage: g.monomials() # the monomials of g
[x1^4*x2^5*x3, x1^7*x2*x3, x1*x2^7*x3, x1^4*x3^5, x1^6*x3]
sage: sum(g.monomials()) # their sum
x1^4*x2^5*x3 + x1^7*x2*x3 + x1*x2^7*x3 + x1^4*x3^5 + x1^6*x3

Note that the use of sum(...) is equivalent to the following:

sage: g0 = R.zero() # the polynomial equal to zero
sage: for m in g.monomials():
....:     g0 += m
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2016-12-02 12:45:15 +0100

Seen: 488 times

Last updated: Dec 09 '16