mjo/polynomial.py

   1 from sage.all import *
   2
   3 def multidiv(f, gs):
   4     r"""
   5     Divide the multivariate polynomial ``f`` by the ordered list of
   6     polynomials ``gs`` from the same ring.
   7
   8     INPUT:
   9
  10     - ``f`` -- A multivariate polynomial, the "numerator," that we try
  11       to express as a combination of the ``gs``.
  12
  13     - ``gs`` -- An ordered list of multipolynomials, the "denominators,"
  14       in the same ring as ``f``.
  15
  16     OUTPUT:
  17
  18     A pair, the first component of which is the list of "quotients," and
  19     the second of which is the remainder. All quotients and the
  20     remainder will live in the same ring as ``f`` and the ``gs``. If the
  21     ordered list of "quotients" is ``qs``, then ``f`` is the remainder
  22     plus the sum of all ``qs[i]*gs[i]``.
  23
  24     The remainder is either zero, or a linear combination of monomials
  25     none of which are divisible by any of the leading terms of the ``gs``.
  26     Moreover if ``qs[i]*gs[i]`` is nonzero, then the multidegree of ``f``
  27     is greater than or equal to the multidegree of ``qs[i]*gs[i]``.
  28
  29     SETUP::
  30
  31         sage: from mjo.polynomial import multidiv
  32
  33     ALGORITHM:
  34
  35     The algorithm from Theorem 3 in  Section 2.3 of Cox, Little, and O'Shea
  36     is used almost verbatim.
  37
  38     REFERENCES:
  39
  40     - David A. Cox, John Little, Donal O'Shea. Ideals, Varieties, and
  41       Algorithms: An Introduction to Computational Algebraic Geometry
  42       and Commutative Algebra (Fourth Edition). Springer Undergraduate
  43       Texts in Mathematics. Springer International Publishing, Switzerland,
  44       2015. :doi:`10.1007/978-3-319-16721-3`.
  45
  46     EXAMPLES:
  47
  48     Example 1 in Section 2.3 of Cox, Little, and O'Shea::
  49
  50         sage: R = PolynomialRing(QQ, 'x,y', order='lex')
  51         sage: x,y = R.gens()
  52         sage: f = x*y^2 + 1
  53         sage: gs = [ x*y + 1, y + 1 ]
  54         sage: multidiv(f, gs)
  55         ([y, -1], 2)
  56
  57     Example 2 in Section 2.3 of Cox, Little, and O'Shea::
  58
  59         sage: R = PolynomialRing(QQ, 'x,y', order='lex')
  60         sage: x,y = R.gens()
  61         sage: f = x^2*y + x*y^2 + y^2
  62         sage: gs = [ x*y - 1, y^2 - 1 ]
  63         sage: multidiv(f, gs)
  64         ([x + y, 1], x + y + 1)
  65
  66     TESTS:
  67
  68     Derp.
  69
  70     """
  71     R = f.parent()
  72     s = len(gs)
  73
  74     p = f
  75     r = R.zero()
  76     qs = [R.zero()]*s
  77
  78     while p != R.zero():
  79         for i in range(0,s):
  80             division_occurred = false
  81             # If gs[i].lt() divides p.lt(), then this remainder will
  82             # be zero and the quotient will be in R (and not the
  83             # fraction ring, which is important).
  84             (factor, lt_r) = p.lt().quo_rem(gs[i].lt())
  85             if lt_r.is_zero():
  86                 qs[i] += factor
  87                 p -= factor*gs[i]
  88                 division_occurred = true
  89                 break
  90
  91         if not division_occurred:
  92             r += p.lt()
  93             p -= p.lt()
  94
  95     return (qs,r)