Source code for sympy.polys.densetools

"""Advanced tools for dense recursive polynomials in ``K[x]`` or ``K[X]``. """

from sympy.polys.densebasic import (
    dup_strip, dmp_strip,
    dup_convert, dmp_convert,
    dup_degree, dmp_degree,
    dmp_to_dict,
    dmp_from_dict,
    dup_LC, dmp_LC, dmp_ground_LC,
    dup_TC, dmp_TC,
    dmp_zero, dmp_ground,
    dmp_zero_p,
    dup_to_raw_dict, dup_from_raw_dict,
    dmp_zeros
)

from sympy.polys.densearith import (
    dup_add_term, dmp_add_term,
    dup_lshift,
    dup_add, dmp_add,
    dup_sub, dmp_sub,
    dup_mul, dmp_mul,
    dup_sqr,
    dup_div,
    dup_rem, dmp_rem,
    dmp_expand,
    dup_mul_ground, dmp_mul_ground,
    dup_quo_ground, dmp_quo_ground,
    dup_exquo_ground, dmp_exquo_ground,
)

from sympy.polys.polyerrors import (
    MultivariatePolynomialError,
    DomainError
)

from sympy.utilities import (
    cythonized, variations
)

from math import ceil as _ceil, log as _log

@cythonized("m,n,i,j")
def dup_integrate(f, m, K):
    """
    Computes indefinite integral of ``f`` in ``K[x]``.

    Examples
    ========

    >>> from sympy.polys.domains import QQ
    >>> from sympy.polys.densetools import dup_integrate

    >>> dup_integrate([QQ(1), QQ(2), QQ(0)], 1, QQ)
    [1/3, 1/1, 0/1, 0/1]
    >>> dup_integrate([QQ(1), QQ(2), QQ(0)], 2, QQ)
    [1/12, 1/3, 0/1, 0/1, 0/1]

    """
    if m <= 0 or not f:
        return f

    g = [K.zero]*m

    for i, c in enumerate(reversed(f)):
        n = i+1

        for j in xrange(1, m):
            n *= i+j+1

        g.insert(0, K.quo(c, K(n)))

    return g

@cythonized("m,u,v,n,i,j")
[docs]def dmp_integrate(f, m, u, K): """ Computes indefinite integral of ``f`` in ``x_0`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import QQ >>> from sympy.polys.densetools import dmp_integrate >>> dmp_integrate([[QQ(1)], [QQ(2), QQ(0)]], 1, 1, QQ) [[1/2], [2/1, 0/1], []] >>> dmp_integrate([[QQ(1)], [QQ(2), QQ(0)]], 2, 1, QQ) [[1/6], [1/1, 0/1], [], []] """ if not u: return dup_integrate(f, m, K) if m <= 0 or dmp_zero_p(f, u): return f g, v = dmp_zeros(m, u-1, K), u-1 for i, c in enumerate(reversed(f)): n = i+1 for j in xrange(1, m): n *= i+j+1 g.insert(0, dmp_quo_ground(c, K(n), v, K)) return g
@cythonized("m,v,w,i,j") def _rec_integrate_in(g, m, v, i, j, K): """Recursive helper for :func:`dmp_integrate_in`.""" if i == j: return dmp_integrate(g, m, v, K) w, i = v-1, i+1 return dmp_strip([ _rec_integrate_in(c, m, w, i, j, K) for c in g ], v) @cythonized("m,j,u")
[docs]def dmp_integrate_in(f, m, j, u, K): """ Computes indefinite integral of ``f`` in ``x_j`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import QQ >>> from sympy.polys.densetools import dmp_integrate_in >>> dmp_integrate_in([[QQ(1)], [QQ(2), QQ(0)]], 1, 0, 1, QQ) [[1/2], [2/1, 0/1], []] >>> dmp_integrate_in([[QQ(1)], [QQ(2), QQ(0)]], 1, 1, 1, QQ) [[1/1, 0/1], [1/1, 0/1, 0/1]] """ if j < 0 or j > u: raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j)) return _rec_integrate_in(f, m, u, 0, j, K)
@cythonized("m,n,k,i") def dup_diff(f, m, K): """ ``m``-th order derivative of a polynomial in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_diff >>> dup_diff([ZZ(1), ZZ(2), ZZ(3), ZZ(4)], 1, ZZ) [3, 4, 3] >>> dup_diff([ZZ(1), ZZ(2), ZZ(3), ZZ(4)], 2, ZZ) [6, 4] """ if m <= 0: return f n = dup_degree(f) if n < m: return [] deriv = [] if m == 1: for coeff in f[:-m]: deriv.append(K(n)*coeff) n -= 1 else: for coeff in f[:-m]: k = n for i in xrange(n-1, n-m, -1): k *= i deriv.append(K(k)*coeff) n -= 1 return dup_strip(deriv) @cythonized("u,v,m,n,k,i")
[docs]def dmp_diff(f, m, u, K): """ ``m``-th order derivative in ``x_0`` of a polynomial in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_diff >>> f = ZZ.map([[1, 2, 3], [2, 3, 1]]) >>> dmp_diff(f, 1, 1, ZZ) [[1, 2, 3]] >>> dmp_diff(f, 2, 1, ZZ) [[]] """ if not u: return dup_diff(f, m, K) if m <= 0: return f n = dmp_degree(f, u) if n < m: return dmp_zero(u) deriv, v = [], u-1 if m == 1: for coeff in f[:-m]: deriv.append(dmp_mul_ground(coeff, K(n), v, K)) n -= 1 else: for coeff in f[:-m]: k = n for i in xrange(n-1, n-m, -1): k *= i deriv.append(dmp_mul_ground(coeff, K(k), v, K)) n -= 1 return dmp_strip(deriv, u)
@cythonized("m,v,w,i,j") def _rec_diff_in(g, m, v, i, j, K): """Recursive helper for :func:`dmp_diff_in`.""" if i == j: return dmp_diff(g, m, v, K) w, i = v-1, i+1 return dmp_strip([ _rec_diff_in(c, m, w, i, j, K) for c in g ], v) @cythonized("m,j,u")
[docs]def dmp_diff_in(f, m, j, u, K): """ ``m``-th order derivative in ``x_j`` of a polynomial in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_diff_in >>> f = ZZ.map([[1, 2, 3], [2, 3, 1]]) >>> dmp_diff_in(f, 1, 0, 1, ZZ) [[1, 2, 3]] >>> dmp_diff_in(f, 1, 1, 1, ZZ) [[2, 2], [4, 3]] """ if j < 0 or j > u: raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j)) return _rec_diff_in(f, m, u, 0, j, K)
def dup_eval(f, a, K): """ Evaluate a polynomial at ``x = a`` in ``K[x]`` using Horner scheme. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_eval >>> dup_eval([ZZ(1), ZZ(2), ZZ(3)], 2, ZZ) 11 """ if not a: return dup_TC(f, K) result = K.zero for c in f: result *= a result += c return result @cythonized("u,v")
[docs]def dmp_eval(f, a, u, K): """ Evaluate a polynomial at ``x_0 = a`` in ``K[X]`` using the Horner scheme. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_eval >>> f = ZZ.map([[2, 3], [1, 2]]) >>> dmp_eval(f, 2, 1, ZZ) [5, 8] """ if not u: return dup_eval(f, a, K) if not a: return dmp_TC(f, K) result, v = dmp_LC(f, K), u-1 for coeff in f[1:]: result = dmp_mul_ground(result, a, v, K) result = dmp_add(result, coeff, v, K) return result
@cythonized("v,i,j") def _rec_eval_in(g, a, v, i, j, K): """Recursive helper for :func:`dmp_eval_in`.""" if i == j: return dmp_eval(g, a, v, K) v, i = v-1, i+1 return dmp_strip([ _rec_eval_in(c, a, v, i, j, K) for c in g ], v) @cythonized("u")
[docs]def dmp_eval_in(f, a, j, u, K): """ Evaluate a polynomial at ``x_j = a`` in ``K[X]`` using the Horner scheme. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_eval_in >>> f = ZZ.map([[2, 3], [1, 2]]) >>> dmp_eval_in(f, 2, 0, 1, ZZ) [5, 8] >>> dmp_eval_in(f, 2, 1, 1, ZZ) [7, 4] """ if j < 0 or j > u: raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j)) return _rec_eval_in(f, a, u, 0, j, K)
@cythonized("i,u") def _rec_eval_tail(g, i, A, u, K): """Recursive helper for :func:`dmp_eval_tail`.""" if i == u: return dup_eval(g, A[-1], K) else: h = [ _rec_eval_tail(c, i+1, A, u, K) for c in g ] if i < u - len(A) + 1: return h else: return dup_eval(h, A[-u+i-1], K) @cythonized("u")
[docs]def dmp_eval_tail(f, A, u, K): """ Evaluate a polynomial at ``x_j = a_j, ...`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_eval_tail >>> f = ZZ.map([[2, 3], [1, 2]]) >>> dmp_eval_tail(f, (2, 2), 1, ZZ) 18 >>> dmp_eval_tail(f, (2,), 1, ZZ) [7, 4] """ if not A: return f if dmp_zero_p(f, u): return dmp_zero(u - len(A)) e = _rec_eval_tail(f, 0, A, u, K) if u == len(A)-1: return e else: return dmp_strip(e, u - len(A))
@cythonized("m,v,i,j") def _rec_diff_eval(g, m, a, v, i, j, K): """Recursive helper for :func:`dmp_diff_eval`.""" if i == j: return dmp_eval(dmp_diff(g, m, v, K), a, v, K) v, i = v-1, i+1 return dmp_strip([ _rec_diff_eval(c, m, a, v, i, j, K) for c in g ], v) @cythonized("m,j,u")
[docs]def dmp_diff_eval_in(f, m, a, j, u, K): """ Differentiate and evaluate a polynomial in ``x_j`` at ``a`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_diff_eval_in >>> f = ZZ.map([[1, 2, 3], [2, 3, 1]]) >>> dmp_diff_eval_in(f, 1, 2, 0, 1, ZZ) [1, 2, 3] >>> dmp_diff_eval_in(f, 1, 2, 1, 1, ZZ) [6, 11] """ if j > u: raise IndexError("-%s <= j < %s expected, got %s" % (u, u, j)) if not j: return dmp_eval(dmp_diff(f, m, u, K), a, u, K) return _rec_diff_eval(f, m, a, u, 0, j, K)
def dup_trunc(f, p, K): """ Reduce ``K[x]`` polynomial modulo a constant ``p`` in ``K``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_trunc >>> f = ZZ.map([2, 3, 5, 7]) >>> dup_trunc(f, ZZ(3), ZZ) [-1, 0, -1, 1] """ if K.is_ZZ: g = [] for c in f: c = c % p if c > p // 2: g.append(c - p) else: g.append(c) else: g = [ c % p for c in f ] return dup_strip(g) @cythonized("u")
[docs]def dmp_trunc(f, p, u, K): """ Reduce ``K[X]`` polynomial modulo a polynomial ``p`` in ``K[Y]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_trunc >>> f = ZZ.map([[3, 8], [5, 6], [2, 3]]) >>> g = ZZ.map([1, -1]) >>> dmp_trunc(f, g, 1, ZZ) [[11], [11], [5]] """ return dmp_strip([ dmp_rem(c, p, u-1, K) for c in f ], u)
@cythonized("u,v")
[docs]def dmp_ground_trunc(f, p, u, K): """ Reduce ``K[X]`` polynomial modulo a constant ``p`` in ``K``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_ground_trunc >>> f = ZZ.map([[3, 8], [5, 6], [2, 3]]) >>> dmp_ground_trunc(f, ZZ(3), 1, ZZ) [[-1], [-1, 0], [-1, 0]] """ if not u: return dup_trunc(f, p, K) v = u-1 return dmp_strip([ dmp_ground_trunc(c, p, v, K) for c in f ], u)
[docs]def dup_monic(f, K): """ Divides all coefficients by ``LC(f)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dup_monic >>> dup_monic([ZZ(3), ZZ(6), ZZ(9)], ZZ) [1, 2, 3] >>> dup_monic([QQ(3), QQ(4), QQ(2)], QQ) [1/1, 4/3, 2/3] """ if not f: return f lc = dup_LC(f, K) if K.is_one(lc): return f else: return dup_exquo_ground(f, lc, K)
@cythonized("u")
[docs]def dmp_ground_monic(f, u, K): """ Divides all coefficients by ``LC(f)`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dmp_ground_monic >>> f = ZZ.map([[3, 6], [3, 0], [9, 3]]) >>> g = QQ.map([[3, 8], [5, 6], [2, 3]]) >>> dmp_ground_monic(f, 1, ZZ) [[1, 2], [1, 0], [3, 1]] >>> dmp_ground_monic(g, 1, QQ) [[1/1, 8/3], [5/3, 2/1], [2/3, 1/1]] """ if not u: return dup_monic(f, K) if dmp_zero_p(f, u): return f lc = dmp_ground_LC(f, u, K) if K.is_one(lc): return f else: return dmp_exquo_ground(f, lc, u, K)
[docs]def dup_content(f, K): """ Compute the GCD of coefficients of ``f`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dup_content >>> f = ZZ.map([6, 8, 12]) >>> g = QQ.map([6, 8, 12]) >>> dup_content(f, ZZ) 2 >>> dup_content(g, QQ) 2/1 """ from sympy.polys.domains import QQ if not f: return K.zero cont = K.zero if K == QQ: for c in f: cont = K.gcd(cont, c) else: for c in f: cont = K.gcd(cont, c) if K.is_one(cont): break return cont
@cythonized("u,v")
[docs]def dmp_ground_content(f, u, K): """ Compute the GCD of coefficients of ``f`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dmp_ground_content >>> f = ZZ.map([[2, 6], [4, 12]]) >>> g = QQ.map([[2, 6], [4, 12]]) >>> dmp_ground_content(f, 1, ZZ) 2 >>> dmp_ground_content(g, 1, QQ) 2/1 """ from sympy.polys.domains import QQ if not u: return dup_content(f, K) if dmp_zero_p(f, u): return K.zero cont, v = K.zero, u - 1 if K == QQ: for c in f: cont = K.gcd(cont, dmp_ground_content(c, v, K)) else: for c in f: cont = K.gcd(cont, dmp_ground_content(c, v, K)) if K.is_one(cont): break return cont
[docs]def dup_primitive(f, K): """ Compute content and the primitive form of ``f`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dup_primitive >>> f = ZZ.map([6, 8, 12]) >>> g = QQ.map([6, 8, 12]) >>> dup_primitive(f, ZZ) (2, [3, 4, 6]) >>> dup_primitive(g, QQ) (2/1, [3/1, 4/1, 6/1]) """ if not f: return K.zero, f cont = dup_content(f, K) if K.is_one(cont): return cont, f else: return cont, dup_quo_ground(f, cont, K)
@cythonized("u")
[docs]def dmp_ground_primitive(f, u, K): """ Compute content and the primitive form of ``f`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ, QQ >>> from sympy.polys.densetools import dmp_ground_primitive >>> f = ZZ.map([[2, 6], [4, 12]]) >>> g = QQ.map([[2, 6], [4, 12]]) >>> dmp_ground_primitive(f, 1, ZZ) (2, [[1, 3], [2, 6]]) >>> dmp_ground_primitive(g, 1, QQ) (2/1, [[1/1, 3/1], [2/1, 6/1]]) """ if not u: return dup_primitive(f, K) if dmp_zero_p(f, u): return K.zero, f cont = dmp_ground_content(f, u, K) if K.is_one(cont): return cont, f else: return cont, dmp_quo_ground(f, cont, u, K)
[docs]def dup_extract(f, g, K): """ Extract common content from a pair of polynomials in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_extract >>> f = ZZ.map([6, 12, 18]) >>> g = ZZ.map([4, 8, 12]) >>> dup_extract(f, g, ZZ) (2, [3, 6, 9], [2, 4, 6]) """ fc = dup_content(f, K) gc = dup_content(g, K) gcd = K.gcd(fc, gc) if not K.is_one(gcd): f = dup_quo_ground(f, gcd, K) g = dup_quo_ground(g, gcd, K) return gcd, f, g
@cythonized("u")
[docs]def dmp_ground_extract(f, g, u, K): """ Extract common content from a pair of polynomials in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_ground_extract >>> f = ZZ.map([[6, 12], [18]]) >>> g = ZZ.map([[4, 8], [12]]) >>> dmp_ground_extract(f, g, 1, ZZ) (2, [[3, 6], [9]], [[2, 4], [6]]) """ fc = dmp_ground_content(f, u, K) gc = dmp_ground_content(g, u, K) gcd = K.gcd(fc, gc) if not K.is_one(gcd): f = dmp_quo_ground(f, gcd, u, K) g = dmp_quo_ground(g, gcd, u, K) return gcd, f, g
[docs]def dup_real_imag(f, K): """ Return bivariate polynomials ``f1`` and ``f2``, such that ``f = f1 + f2*I``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_real_imag >>> dup_real_imag([ZZ(1), ZZ(1), ZZ(1), ZZ(1)], ZZ) ([[1], [1], [-3, 0, 1], [-1, 0, 1]], [[3, 0], [2, 0], [-1, 0, 1, 0]]) """ if not K.is_ZZ and not K.is_QQ: raise DomainError("computing real and imaginary parts is not supported over %s" % K) f1 = dmp_zero(1) f2 = dmp_zero(1) if not f: return f1, f2 g = [[[K.one, K.zero]], [[K.one], []]] h = dmp_ground(f[0], 2) for c in f[1:]: h = dmp_mul(h, g, 2, K) h = dmp_add_term(h, dmp_ground(c, 1), 0, 2, K) H = dup_to_raw_dict(h) for k, h in H.iteritems(): m = k % 4 if not m: f1 = dmp_add(f1, h, 1, K) elif m == 1: f2 = dmp_add(f2, h, 1, K) elif m == 2: f1 = dmp_sub(f1, h, 1, K) else: f2 = dmp_sub(f2, h, 1, K) return f1, f2
@cythonized('i,n')
[docs]def dup_mirror(f, K): """ Evaluate efficiently the composition ``f(-x)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_mirror >>> dup_mirror([ZZ(1), ZZ(2), -ZZ(4), ZZ(2)], ZZ) [-1, 2, 4, 2] """ f, n, a = list(f), dup_degree(f), -K.one for i in xrange(n-1, -1, -1): f[i], a = a*f[i], -a return f
@cythonized('i,n')
[docs]def dup_scale(f, a, K): """ Evaluate efficiently composition ``f(a*x)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_scale >>> dup_scale([ZZ(1), -ZZ(2), ZZ(1)], ZZ(2), ZZ) [4, -4, 1] """ f, n, b = list(f), dup_degree(f), a for i in xrange(n-1, -1, -1): f[i], b = b*f[i], b*a return f
@cythonized('i,j,n')
[docs]def dup_shift(f, a, K): """ Evaluate efficiently Taylor shift ``f(x + a)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_shift >>> dup_shift([ZZ(1), -ZZ(2), ZZ(1)], ZZ(2), ZZ) [1, 2, 1] """ f, n = list(f), dup_degree(f) for i in xrange(n, 0, -1): for j in xrange(0, i): f[j+1] += a*f[j] return f
@cythonized('i,n')
[docs]def dup_transform(f, p, q, K): """ Evaluate functional transformation ``q**n * f(p/q)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_transform >>> f = ZZ.map([1, -2, 1]) >>> p = ZZ.map([1, 0, 1]) >>> q = ZZ.map([1, -1]) >>> dup_transform(f, p, q, ZZ) [1, -2, 5, -4, 4] """ if not f: return [] n = dup_degree(f) h, Q = [f[0]], [[K.one]] for i in xrange(0, n): Q.append(dup_mul(Q[-1], q, K)) for c, q in zip(f[1:], Q[1:]): h = dup_mul(h, p, K) q = dup_mul_ground(q, c, K) h = dup_add(h, q, K) return h
def dup_compose(f, g, K): """ Evaluate functional composition ``f(g)`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_compose >>> f = ZZ.map([1, 1, 0]) >>> g = ZZ.map([1, -1]) >>> dup_compose(f, g, ZZ) [1, -1, 0] """ if len(g) <= 1: return dup_strip([dup_eval(f, dup_LC(g, K), K)]) if not f: return [] h = [f[0]] for c in f[1:]: h = dup_mul(h, g, K) h = dup_add_term(h, c, 0, K) return h @cythonized("u")
[docs]def dmp_compose(f, g, u, K): """ Evaluate functional composition ``f(g)`` in ``K[X]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dmp_compose >>> f = ZZ.map([[1, 2], [1, 0]]) >>> g = ZZ.map([[1, 0]]) >>> dmp_compose(f, g, 1, ZZ) [[1, 3, 0]] """ if not u: return dup_compose(f, g, K) if dmp_zero_p(f, u): return f h = [f[0]] for c in f[1:]: h = dmp_mul(h, g, u, K) h = dmp_add_term(h, c, 0, u, K) return h
@cythonized("s,n,r,i,j") def _dup_right_decompose(f, s, K): """Helper function for :func:`_dup_decompose`.""" n = dup_degree(f) lc = dup_LC(f, K) f = dup_to_raw_dict(f) g = { s : K.one } r = n // s for i in xrange(1, s): coeff = K.zero for j in xrange(0, i): if not n+j-i in f: continue if not s-j in g: continue fc, gc = f[n+j-i], g[s-j] coeff += (i - r*j)*fc*gc g[s-i] = K.quo(coeff, i*r*lc) return dup_from_raw_dict(g, K) @cythonized("i") def _dup_left_decompose(f, h, K): """Helper function for :func:`_dup_decompose`.""" g, i = {}, 0 while f: q, r = dup_div(f, h, K) if dup_degree(r) > 0: return None else: g[i] = dup_LC(r, K) f, i = q, i + 1 return dup_from_raw_dict(g, K) @cythonized("df,s") def _dup_decompose(f, K): """Helper function for :func:`dup_decompose`.""" df = dup_degree(f) for s in xrange(2, df): if df % s != 0: continue h = _dup_right_decompose(f, s, K) if h is not None: g = _dup_left_decompose(f, h, K) if g is not None: return g, h return None
[docs]def dup_decompose(f, K): """ Computes functional decomposition of ``f`` in ``K[x]``. Given a univariate polynomial ``f`` with coefficients in a field of characteristic zero, returns list ``[f_1, f_2, ..., f_n]``, where:: f = f_1 o f_2 o ... f_n = f_1(f_2(... f_n)) and ``f_2, ..., f_n`` are monic and homogeneous polynomials of at least second degree. Unlike factorization, complete functional decompositions of polynomials are not unique, consider examples: 1. ``f o g = f(x + b) o (g - b)`` 2. ``x**n o x**m = x**m o x**n`` 3. ``T_n o T_m = T_m o T_n`` where ``T_n`` and ``T_m`` are Chebyshev polynomials. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_decompose >>> f = ZZ.map([1, -2, 1, 0, 0]) >>> dup_decompose(f, ZZ) [[1, 0, 0], [1, -1, 0]] References ========== 1. [Kozen89]_ """ F = [] while True: result = _dup_decompose(f, K) if result is not None: f, h = result F = [h] + F else: break return [f] + F
@cythonized("u")
[docs]def dmp_lift(f, u, K): """ Convert algebraic coefficients to integers in ``K[X]``. Examples ======== >>> from sympy import I >>> from sympy.polys.domains import QQ >>> from sympy.polys.densetools import dmp_lift >>> K = QQ.algebraic_field(I) >>> f = [K(1), K([QQ(1), QQ(0)]), K([QQ(2), QQ(0)])] >>> dmp_lift(f, 0, K) [1/1, 0/1, 2/1, 0/1, 9/1, 0/1, -8/1, 0/1, 16/1] """ if not K.is_Algebraic: raise DomainError('computation can be done only in an algebraic domain') F, monoms, polys = dmp_to_dict(f, u), [], [] for monom, coeff in F.iteritems(): if not coeff.is_ground: monoms.append(monom) perms = variations([-1, 1], len(monoms), repetition=True) for perm in perms: G = dict(F) for sign, monom in zip(perm, monoms): if sign == -1: G[monom] = -G[monom] polys.append(dmp_from_dict(G, u, K)) return dmp_convert(dmp_expand(polys, u, K), u, K, K.dom)
[docs]def dup_sign_variations(f, K): """ Compute the number of sign variations of ``f`` in ``K[x]``. Examples ======== >>> from sympy.polys.domains import ZZ >>> from sympy.polys.densetools import dup_sign_variations >>> f = ZZ.map([1, 0, -1, -1, 1]) >>> dup_sign_variations(f, ZZ) 2 """ prev, k = K.zero, 0 for coeff in f: if K.is_negative(coeff*prev): k += 1 if coeff: prev = coeff return k
def dup_clear_denoms(f, K0, K1=None, convert=False): """ Clear denominators, i.e. transform ``K_0`` to ``K_1``. Examples ======== >>> from sympy.polys.domains import QQ, ZZ >>> from sympy.polys.densetools import dup_clear_denoms >>> f = [QQ(1,2), QQ(1,3)] >>> dup_clear_denoms(f, QQ, convert=False) (6, [3/1, 2/1]) >>> f = [QQ(1,2), QQ(1,3)] >>> dup_clear_denoms(f, QQ, convert=True) (6, [3, 2]) """ if K1 is None: K1 = K0.get_ring() common = K1.one for c in f: common = K1.lcm(common, K0.denom(c)) if not K1.is_one(common): f = dup_mul_ground(f, common, K0) if not convert: return common, f else: return common, dup_convert(f, K0, K1) @cythonized("v,w") def _rec_clear_denoms(g, v, K0, K1): """Recursive helper for :func:`dmp_clear_denoms`.""" common = K1.one if not v: for c in g: common = K1.lcm(common, K0.denom(c)) else: w = v-1 for c in g: common = K1.lcm(common, _rec_clear_denoms(c, w, K0, K1)) return common @cythonized("u")
[docs]def dmp_clear_denoms(f, u, K0, K1=None, convert=False): """ Clear denominators, i.e. transform ``K_0`` to ``K_1``. Examples ======== >>> from sympy.polys.domains import QQ, ZZ >>> from sympy.polys.densetools import dmp_clear_denoms >>> f = [[QQ(1,2)], [QQ(1,3), QQ(1)]] >>> dmp_clear_denoms(f, 1, QQ, convert=False) (6, [[3/1], [2/1, 6/1]]) >>> f = [[QQ(1,2)], [QQ(1,3), QQ(1)]] >>> dmp_clear_denoms(f, 1, QQ, convert=True) (6, [[3], [2, 6]]) """ if not u: return dup_clear_denoms(f, K0, K1, convert=convert) if K1 is None: K1 = K0.get_ring() common = _rec_clear_denoms(f, u, K0, K1) if not K1.is_one(common): f = dmp_mul_ground(f, common, u, K0) if not convert: return common, f else: return common, dmp_convert(f, u, K0, K1)
@cythonized('i,n') def dup_revert(f, n, K): """ Compute ``f**(-1)`` mod ``x**n`` using Newton iteration. This function computes first ``2**n`` terms of a polynomial that is a result of inversion of a polynomial modulo ``x**n``. This is useful to efficiently compute series expansion of ``1/f``. Examples ======== >>> from sympy.polys.domains import QQ >>> from sympy.polys.densetools import dup_revert >>> f = [-QQ(1,720), QQ(0), QQ(1,24), QQ(0), -QQ(1,2), QQ(0), QQ(1)] >>> dup_revert(f, 8, QQ) [61/720, 0/1, 5/24, 0/1, 1/2, 0/1, 1/1] """ g = [K.revert(dup_TC(f, K))] h = [K.one, K.zero, K.zero] N = int(_ceil(_log(n, 2))) for i in xrange(1, N + 1): a = dup_mul_ground(g, K(2), K) b = dup_mul(f, dup_sqr(g, K), K) g = dup_rem(dup_sub(a, b, K), h, K) h = dup_lshift(h, dup_degree(h), K) return g
[docs]def dmp_revert(f, g, u, K): """ Compute ``f**(-1)`` mod ``x**n`` using Newton iteration. Examples ======== >>> from sympy.polys.domains import QQ >>> from sympy.polys.densetools import dmp_revert """ if not u: return dup_revert(f, g, K) else: raise MultivariatePolynomialError(f, g)