How to implement the multivariable division algorithm without passing to Grobner bases?

asked 2016-03-31 21:01:31 +0200

rmg512
23 ●1 ●1 ●4

updated 2024-04-18 20:08:17 +0200

5125 ●3 ●43 ●111

Hi, I'm new to Sage, and I'm wondering how to implement the multivariable division algorithm in Sage. I pulled up the "Multivariate Polynomials via libSINGULAR" page of the Sage Reference Manual v7.1, but it wasn't helpful. What I'm wanting is a generalization of the quo_rem command that can take in more than one argument on the right and follows the division algorithm with respect to a fixed monomial ordering and the order that the polynomials are entered in. Is there any set of commands that does that for me? If so, would you please include the code, say for the following example?

Divide the polynomial yx^2 + xy^2 + y^2 by xy-1 and y2 -1 (in that order) using the lexicographic ordering with x>y. I would like to process more complicated examples, perhaps with that order and dividing by 8 things at once rather than 2.

I've learned about the p.mod(I) and p.reduce(I) commands where p is a polynomial and I is an ideal. The problem with those is that they seem to pass to a Grobner basis for I to get a "canonical" remainder rather than the remainder we'd get from the given order of the polynomials, as I tested switching the order of the polynomials in defining an ideal I and it did not change my answer for p.mod(I) or p.reduce(I).

Thanks!

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2016-04-01 11:29:10 +0200

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

It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:

sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1

Now if you want a more general function, you can implement it as follows:

sage: def remainder(p, L):
....:     r = p
....:     for q in L:
....:         r = r % q
....:     return r
....: 
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1

You may also want to keep the quotients:

sage: def list_quo_rem(p, L):
....:     r = p
....:     quo = []
....:     for q in L:
....:         Q, R = r.quo_rem(q)
....:         quo.append(Q)
....:         r = R
....:     return (quo, r)
....: 
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)

edit flag offensive delete link

Comments

Thank you so much! I wish I could at least award you karma for this, but it seems I can't since I don't have enough myself.

One more question: How are we defining the object L? Is it the ideal generated by the pair q and r, is it an ordered list, or is it something else?

Thanks again!

rmg512 ( 2016-04-01 18:00:31 +0200 )edit

The object L in my code is any iterable, a list for instance. If you work with an ideal I, I.gens() is such an iterable so you can call remainder(p, I.gens()) for instance.

B r u n o ( 2016-04-01 20:29:22 +0200 )edit

Great! That makes sense. Thanks again!

rmg512 ( 2016-04-01 21:03:24 +0200 )edit

As a corollary question: would you happen to know how I could get all possible remainders from all possible orders with one command? If I'm dividing 5 or 6 things at once, iterating the program you've written to get all possible remainders isn't very practical to type out. It looks like I might need to do that to test the examples I've come up with to test my conjecture. Thanks!

rmg512 ( 2016-04-01 21:27:49 +0200 )edit

You can use the permutation groups. Suppose you have a list L of polynomials (which can be I.gens() for some ideal), then you can do the following:

sage: S = SymmetricGroup(len(L))
sage: for s in S: # = for each permutation of the elements
....:     print list_quo_rem(p, s(L))

B r u n o ( 2016-04-02 15:14:58 +0200 )edit

see more comments

answered 2020-02-23 00:16:33 +0200

Asma
1

Write a function "division" such that division(f,F) returns the quotient(s) and remainder of a polynomial f divided by an ordered tuple F of polynomials, where all polynomials live in a ring with an arbitrary number of variables.

Since you don't know a priori the number of elements in F, one option is to pass F to your function as a list. You can get the length of the list with #F and you can access its entries with F_0, F_1, etc. Similarly, you can return the quotients in a list {q1,q2,...,qs}. There is a section on lists in the M2 documentation under The Macaulay2 Language -> lists and sequences.

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

How to implement the multivariable division algorithm without passing to Grobner bases?

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

How to implement the multivariable division algorithm without passing to Grobner bases? edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

How to implement the multivariable division algorithm without passing to Grobner bases?