Ask Your Question
0

Division algorithm in a polynomial ring with variable coefficients

asked 2017-03-27 14:26:48 -0600

KittyL gravatar image

I am working on an algorithm to divide a polynomial f by a list of polynomials [g1, g2, ..., gm]. The following is my algorithm:

def div(f,g): # Division algorithm on Page 11 of Using AG by Cox;
# f is the dividend;
# g is a list of ordered divisors;
# The output consists of a list of coefficients for g and the remainder;
# p is the intermediate dividend;
n = len(g)
p, r, q = f, 0,  [0 for x in range(0,n)]
while p != 0:
    i, divisionoccured = 0, False
    print(p,r,q);
    while i < n and divisionoccured == False:
        if g[i].lt().divides(p.lt()):
            q[i] = q[i] + p.lt()//g[i].lt()
            p = p - (p.lt()//g[i].lt())*g[i]
            divisionoccured = True
        else:
            i = i + 1
    if divisionoccured == False:
        r = r + p.lt()
        p = p - p.lt()
return q, r

Here is an example of implementing the algorithm:

K.<a,b> = FractionField(PolynomialRing(QQ,'a, b'))
P.<x,y,z> = PolynomialRing(K,order='lex')
f=a*x^2*y^3+x*y+2*b
g1=a^2*x+2
g2=x*y-b
div(f,[g1,g2])

Here is the result:

(a*x^2*y^3 + x*y + 2*b, 0, [0, 0])
(((-2)/a)*x*y^3 + x*y + 2*b, 0, [1/a*x*y^3, 0])
(x*y + 4/a^3*y^3 + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3, 0])
(4/a^3*y^3 + ((-2)/a^2)*y + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(((-2)/a^2)*y + 2*b, 4/a^3*y^3, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(2*b, 4/a^3*y^3 + ((-2)/a^2)*y, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
Error in lines 6-6
Traceback (most recent call last):

and some other error messages.

We can see that it worked well until the leading term is 2b. it does not recognize the 2b as a term. I tried:

(x).lt().divides(1)

It gives the answer False. But I tried

(x).lt().divides(a)

It gives error message. Is there a way to solve this? Thank you for your help!

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-04-08 09:21:41 -0600

dan_fulea gravatar image

The following worked for me:

def div( f, g, ring ):
    """
    Division algorithm on Page 11 of Using AG by Cox;
    f is the dividend;
    g is a list of ordered divisors;
    The output consists of a list of coefficients for g and the remainder;
    p is the intermediate dividend;
    """
    n = len(g)
    p, r, q = f, 0,  [0 for _ in range(0,n)]

    count = 0
    while p != 0:
        count += 1
        i, divisionoccured = 0, False
        print ( "Step %s:\n\tp = %s\n\tr = %s\n\tq = %s"
                % ( count, p, r, q ) )

        while i < n and not divisionoccured:
            glt, plt = g[i].lt(), p.lt()

            if glt and plt / glt in ring:
                q[i] = q[i] + plt // glt
                p    =    p - plt // glt * g[i]
                divisionoccured = True
                print "\t\tChange:\n\t\tq[%s] = %s\n\t\tp = %s" % ( i, q[i], p )
            else:
                i = i + 1
                print "\t\tIncrementing i: i = %s" % i
        if not divisionoccured:
            r = r + p.lt()
            p = p - p.lt()

    return q, r

R.<a,b>    = PolynomialRing( QQ )
K          = FractionField( R )
RK.<x,y,z> = PolynomialRing( K, order='lex' )

f  = a*x^2*y^3 + x*y + 2*b
g1 = a^2*x + 2
g2 = x*y   - b

div( f, [g1,g2], RK )

This replaces the line with the divides method call by a test if the division (makes sens and) lands still in the ring.

Results with many verbose prints in the one test case submitted:

Step 1:
    p = a*x^2*y^3 + x*y + 2*b
    r = 0
    q = [0, 0]
        Change:
        q[0] = 1/a*x*y^3
        p = ((-2)/a)*x*y^3 + x*y + 2*b
Step 2:
    p = ((-2)/a)*x*y^3 + x*y + 2*b
    r = 0
    q = [1/a*x*y^3, 0]
        Change:
        q[0] = 1/a*x*y^3 + ((-2)/a^3)*y^3
        p = x*y + 4/a^3*y^3 + 2*b
Step 3:
    p = x*y + 4/a^3*y^3 + 2*b
    r = 0
    q = [1/a*x*y^3 + ((-2)/a^3)*y^3, 0]
        Change:
        q[0] = 1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y
        p = 4/a^3*y^3 + ((-2)/a^2)*y + 2*b
Step 4:
    p = 4/a^3*y^3 + ((-2)/a^2)*y + 2*b
    r = 0
    q = [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0]
        Incrementing i: i = 1
        Incrementing i: i = 2
Step 5:
    p = ((-2)/a^2)*y + 2*b
    r = 4/a^3*y^3
    q = [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0]
        Incrementing i: i = 1
        Incrementing i: i = 2
Step 6:
    p = 2*b
    r = 4/a^3*y^3 + ((-2)/a^2)*y
    q = [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0]
        Incrementing i: i = 1
        Incrementing i: i = 2
([1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0], 4/a^3*y^3 + ((-2)/a^2)*y + 2*b)
edit flag offensive delete link more

Comments

Thank you for the detailed answer! It worked!

KittyL gravatar imageKittyL ( 2017-04-15 04:18:18 -0600 )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: 2017-03-27 14:26:48 -0600

Seen: 123 times

Last updated: Apr 08