Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Shift function taking a lot of time for higher degree multivariate polynomials

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

Shift function taking a lot of time for higher degree multivariate polynomials

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

Shift function Subresultant algorithm taking a lot of time for higher degree multivariate polynomials

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

Subresultant algorithm taking a lot of time for higher degree multivariate polynomialsunivariate polynomials with coefficients from fraction fields

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

Sample input: sage: A.<x,y>=ZZ[]

sage: B= Frac(A)

sage: C.<z> = B[]

sage: p = C.random_element(6)

sage: q = C.random_element(6)

sage: gcd(p,q) The following function is what I copied into fraction_field.py from unique_factorisation_domain.py.

def _gcd_univariate_polynomial(self, f, g):

    if f.degree() < g.degree():
        A,B = g, f
    else:
        A,B = f, g

    if B.is_zero():
        return A

    a = b = self.zero()
    for c in A.coefficients():
        a = a.gcd(c)
        if a.is_one():
            break
    for c in B.coefficients():
        b = b.gcd(c)
        if b.is_one():
            break

    d = a.gcd(b)

    #d=1
    A = A // a
    B = B // b
    g = h = 1

    delta = A.degree()-B.degree()
    _,R = A.pseudo_quo_rem(B)

    while R.degree() > 0:
        A = B
        B = R // (g*h**delta)
        g = A.leading_coefficient()
        h = h*g**delta // h**delta
        delta = A.degree() - B.degree()
        _, R = A.pseudo_quo_rem(B)
       # print("i am here")


    if R.is_zero():
        b = self.zero()
        for c in B.coefficients():
            b = b.gcd(c)
            if b.is_one():
                break

        return d*B // b

    return d

This calls the following pseudo quo remainder function in polynomial_element.pyx. It is in this function I was able to see that it hangs at R = dR - cB.shift(diffdeg).

def pseudo_quo_rem(self,other):

    if other.is_zero():
        raise ZeroDivisionError("Pseudo-division by zero is not possible")

    # if other is a constant, then R = 0 and Q = self * other^(deg(self))
    if other in self.parent().base_ring():
        return (self * other**(self.degree()), self._parent.zero())

    R = self
    B = other
    Q = self._parent.zero()
    e = self.degree() - other.degree() + 1
    d = B.leading_coefficient()

    while not R.degree() < B.degree():

        c = R.leading_coefficient()

        diffdeg = R.degree() - B.degree()

        Q = d*Q + self.parent()(c).shift(diffdeg)

        R = d*R - c*B.shift(diffdeg)

        e -= 1

    q = d**e
    return (q*Q,q*R)

Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

(Note: In the current version of sage it uses the regular Euclidean algorithm implemented in rings.py for computing gcd in this case. It is much slower than the subresultant algorithm which is why I thought the subresultant algorithm will improve things.)

Sample input: sage: A.<x,y>=ZZ[]

sage: B= Frac(A)

sage: C.<z> = B[]

sage: p = C.random_element(6)

sage: q = C.random_element(6)

sage: gcd(p,q) gcd(p,q)

The following function is what I copied into fraction_field.py from unique_factorisation_domain.py.

def _gcd_univariate_polynomial(self, f, g):

    if f.degree() < g.degree():
        A,B = g, f
    else:
        A,B = f, g

    if B.is_zero():
        return A

    a = b = self.zero()
    for c in A.coefficients():
        a = a.gcd(c)
        if a.is_one():
            break
    for c in B.coefficients():
        b = b.gcd(c)
        if b.is_one():
            break

    d = a.gcd(b)

    #d=1
    A = A // a
    B = B // b
    g = h = 1

    delta = A.degree()-B.degree()
    _,R = A.pseudo_quo_rem(B)

    while R.degree() > 0:
        A = B
        B = R // (g*h**delta)
        g = A.leading_coefficient()
        h = h*g**delta // h**delta
        delta = A.degree() - B.degree()
        _, R = A.pseudo_quo_rem(B)
       # print("i am here")


    if R.is_zero():
        b = self.zero()
        for c in B.coefficients():
            b = b.gcd(c)
            if b.is_one():
                break

        return d*B // b

    return d

This calls the following pseudo quo remainder function in polynomial_element.pyx. It is in this function I was able to see that it hangs at R = dR - cB.shift(diffdeg).

def pseudo_quo_rem(self,other):

    if other.is_zero():
        raise ZeroDivisionError("Pseudo-division by zero is not possible")

    # if other is a constant, then R = 0 and Q = self * other^(deg(self))
    if other in self.parent().base_ring():
        return (self * other**(self.degree()), self._parent.zero())

    R = self
    B = other
    Q = self._parent.zero()
    e = self.degree() - other.degree() + 1
    d = B.leading_coefficient()

    while not R.degree() < B.degree():

        c = R.leading_coefficient()

        diffdeg = R.degree() - B.degree()

        Q = d*Q + self.parent()(c).shift(diffdeg)

        R = d*R - c*B.shift(diffdeg)

        e -= 1

    q = d**e
    return (q*Q,q*R)

Subresultant algorithm taking a lot of time for higher degree univariate polynomials with coefficients from fraction fields

I have to compute the gcd of univariate polynomials over the fraction field of $\mathbb{Z}[x,y]$. I wanted to use the subresultant algorithm already implemented for UFDs. I copied the same function to fraction_field.py. The subresultant algorithm calls the psuedo division algorithm which has the following step : R = dR - cB.shift(diffdeg) - this hangs when we consider random polynomials of degree >6 in $Frac(\mathbb{Z}[x,y])[z]$.

(Note: In the current version of sage it uses the regular Euclidean algorithm implemented in rings.py for computing gcd in this case. It is much slower than the subresultant algorithm (hangs for degrees >4) which is why I thought the subresultant algorithm will improve things.)

Sample input: sage: A.<x,y>=ZZ[]

sage: B= Frac(A)

sage: C.<z> = B[]

sage: p = C.random_element(6)

sage: q = C.random_element(6)

sage: gcd(p,q)

The following function is what I copied into fraction_field.py from unique_factorisation_domain.py.

def _gcd_univariate_polynomial(self, f, g):

    if f.degree() < g.degree():
        A,B = g, f
    else:
        A,B = f, g

    if B.is_zero():
        return A

    a = b = self.zero()
    for c in A.coefficients():
        a = a.gcd(c)
        if a.is_one():
            break
    for c in B.coefficients():
        b = b.gcd(c)
        if b.is_one():
            break

    d = a.gcd(b)

    #d=1
    A = A // a
    B = B // b
    g = h = 1

    delta = A.degree()-B.degree()
    _,R = A.pseudo_quo_rem(B)

    while R.degree() > 0:
        A = B
        B = R // (g*h**delta)
        g = A.leading_coefficient()
        h = h*g**delta // h**delta
        delta = A.degree() - B.degree()
        _, R = A.pseudo_quo_rem(B)
       # print("i am here")


    if R.is_zero():
        b = self.zero()
        for c in B.coefficients():
            b = b.gcd(c)
            if b.is_one():
                break

        return d*B // b

    return d

This calls the following pseudo quo remainder function in polynomial_element.pyx. It is in this function I was able to see that it hangs at R = dR - cB.shift(diffdeg).

def pseudo_quo_rem(self,other):

    if other.is_zero():
        raise ZeroDivisionError("Pseudo-division by zero is not possible")

    # if other is a constant, then R = 0 and Q = self * other^(deg(self))
    if other in self.parent().base_ring():
        return (self * other**(self.degree()), self._parent.zero())

    R = self
    B = other
    Q = self._parent.zero()
    e = self.degree() - other.degree() + 1
    d = B.leading_coefficient()

    while not R.degree() < B.degree():

        c = R.leading_coefficient()

        diffdeg = R.degree() - B.degree()

        Q = d*Q + self.parent()(c).shift(diffdeg)

        R = d*R - c*B.shift(diffdeg)

        e -= 1

    q = d**e
    return (q*Q,q*R)