]>
gitweb.michael.orlitzky.com - sage.d.git/blob - polynomial.py
7414bdf16b33e8178c746a3edf5b6fa4dd3f985b
5 Divide the multivariate polynomial ``f`` by the ordered list of
6 polynomials ``gs`` from the same ring.
10 - ``f`` -- A multivariate polynomial, the "numerator," that we try
11 to express as a combination of the ``gs``.
13 - ``gs`` -- An ordered list of multipolynomials, the "denominators,"
14 in the same ring as ``f``.
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]``.
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]``.
31 sage: from mjo.polynomial import multidiv
35 The algorithm from Theorem 3 in Section 2.3 of Cox, Little, and O'Shea
36 is used almost verbatim.
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`.
48 Example 1 in Section 2.3 of Cox, Little, and O'Shea::
50 sage: R = PolynomialRing(QQ, 'x,y', order='lex')
53 sage: gs = [ x*y + 1, y + 1 ]
54 sage: (qs, r) = multidiv(f, gs)
57 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
59 sage: not any( g.lt().divides(m) for m in r.monomials()
63 Example 2 in Section 2.3 of Cox, Little, and O'Shea::
65 sage: R = PolynomialRing(QQ, 'x,y', order='lex')
67 sage: f = x^2*y + x*y^2 + y^2
68 sage: gs = [ x*y - 1, y^2 - 1 ]
69 sage: (qs, r) = multidiv(f, gs)
71 ([x + y, 1], x + y + 1)
72 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
74 sage: not any( g.lt().divides(m) for m in r.monomials()
80 If we get a zero remainder, then the numerator should belong to
81 the ideal generated by the denominators::
83 sage: set_random_seed()
84 sage: R = PolynomialRing(QQ, 'x,y,z')
85 sage: x,y,z = R.gens()
86 sage: s = ZZ.random_element(1,5).abs()
87 sage: gs = [ R.random_element() for idx in range(s) ]
88 sage: f = R.random_element(ZZ.random_element(10).abs())
89 sage: (qs, r) = multidiv(f,gs)
90 sage: r != 0 or f in R.ideal(gs)
93 The numerator is always the sum of the remainder and the quotients
94 times the denominators, and the remainder's monomials aren't divisible
95 by the leading term of any denominator::
97 sage: set_random_seed()
98 sage: R = PolynomialRing(QQ, 'x,y,z')
99 sage: x,y,z = R.gens()
100 sage: s = ZZ.random_element(1,5).abs()
101 sage: gs = [ R.random_element() for idx in range(s) ]
102 sage: f = R.random_element(ZZ.random_element(10).abs())
103 sage: (qs, r) = multidiv(f,gs)
104 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
106 sage: r == 0 or (not any( g.lt().divides(m) for m in r.monomials()
120 division_occurred
= false
122 # If gs[i].lt() divides p.lt(), then this remainder will
123 # be zero and the quotient will be in R (and not the
124 # fraction ring, which is important).
125 (factor
, lt_r
) = p
.lt().quo_rem(gs
[i
].lt())
129 division_occurred
= true
130 # Don't increment "i" here because we want to try
131 # again with this "denominator" g[i]. We might
132 # get another factor out of it, but we know that
133 # we can't get another factor out of an *earlier*
134 # denominator g[i-k] for some k.
138 if not division_occurred
: