|
r""" |
|
Sparse distributed elements of free modules over multivariate (generalized) |
|
polynomial rings. |
|
|
|
This code and its data structures are very much like the distributed |
|
polynomials, except that the first "exponent" of the monomial is |
|
a module generator index. That is, the multi-exponent ``(i, e_1, ..., e_n)`` |
|
represents the "monomial" `x_1^{e_1} \cdots x_n^{e_n} f_i` of the free module |
|
`F` generated by `f_1, \ldots, f_r` over (a localization of) the ring |
|
`K[x_1, \ldots, x_n]`. A module element is simply stored as a list of terms |
|
ordered by the monomial order. Here a term is a pair of a multi-exponent and a |
|
coefficient. In general, this coefficient should never be zero (since it can |
|
then be omitted). The zero module element is stored as an empty list. |
|
|
|
The main routines are ``sdm_nf_mora`` and ``sdm_groebner`` which can be used |
|
to compute, respectively, weak normal forms and standard bases. They work with |
|
arbitrary (not necessarily global) monomial orders. |
|
|
|
In general, product orders have to be used to construct valid monomial orders |
|
for modules. However, ``lex`` can be used as-is. |
|
|
|
Note that the "level" (number of variables, i.e. parameter u+1 in |
|
distributedpolys.py) is never needed in this code. |
|
|
|
The main reference for this file is [SCA], |
|
"A Singular Introduction to Commutative Algebra". |
|
""" |
|
|
|
|
|
from itertools import permutations |
|
|
|
from sympy.polys.monomials import ( |
|
monomial_mul, monomial_lcm, monomial_div, monomial_deg |
|
) |
|
|
|
from sympy.polys.polytools import Poly |
|
from sympy.polys.polyutils import parallel_dict_from_expr |
|
from sympy.core.singleton import S |
|
from sympy.core.sympify import sympify |
|
|
|
|
|
|
|
|
|
def sdm_monomial_mul(M, X): |
|
""" |
|
Multiply tuple ``X`` representing a monomial of `K[X]` into the tuple |
|
``M`` representing a monomial of `F`. |
|
|
|
Examples |
|
======== |
|
|
|
Multiplying `xy^3` into `x f_1` yields `x^2 y^3 f_1`: |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_monomial_mul |
|
>>> sdm_monomial_mul((1, 1, 0), (1, 3)) |
|
(1, 2, 3) |
|
""" |
|
return (M[0],) + monomial_mul(X, M[1:]) |
|
|
|
|
|
def sdm_monomial_deg(M): |
|
""" |
|
Return the total degree of ``M``. |
|
|
|
Examples |
|
======== |
|
|
|
For example, the total degree of `x^2 y f_5` is 3: |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_monomial_deg |
|
>>> sdm_monomial_deg((5, 2, 1)) |
|
3 |
|
""" |
|
return monomial_deg(M[1:]) |
|
|
|
|
|
def sdm_monomial_lcm(A, B): |
|
r""" |
|
Return the "least common multiple" of ``A`` and ``B``. |
|
|
|
IF `A = M e_j` and `B = N e_j`, where `M` and `N` are polynomial monomials, |
|
this returns `\lcm(M, N) e_j`. Note that ``A`` and ``B`` involve distinct |
|
monomials. |
|
|
|
Otherwise the result is undefined. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_monomial_lcm |
|
>>> sdm_monomial_lcm((1, 2, 3), (1, 0, 5)) |
|
(1, 2, 5) |
|
""" |
|
return (A[0],) + monomial_lcm(A[1:], B[1:]) |
|
|
|
|
|
def sdm_monomial_divides(A, B): |
|
""" |
|
Does there exist a (polynomial) monomial X such that XA = B? |
|
|
|
Examples |
|
======== |
|
|
|
Positive examples: |
|
|
|
In the following examples, the monomial is given in terms of x, y and the |
|
generator(s), f_1, f_2 etc. The tuple form of that monomial is used in |
|
the call to sdm_monomial_divides. |
|
Note: the generator appears last in the expression but first in the tuple |
|
and other factors appear in the same order that they appear in the monomial |
|
expression. |
|
|
|
`A = f_1` divides `B = f_1` |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_monomial_divides |
|
>>> sdm_monomial_divides((1, 0, 0), (1, 0, 0)) |
|
True |
|
|
|
`A = f_1` divides `B = x^2 y f_1` |
|
|
|
>>> sdm_monomial_divides((1, 0, 0), (1, 2, 1)) |
|
True |
|
|
|
`A = xy f_5` divides `B = x^2 y f_5` |
|
|
|
>>> sdm_monomial_divides((5, 1, 1), (5, 2, 1)) |
|
True |
|
|
|
Negative examples: |
|
|
|
`A = f_1` does not divide `B = f_2` |
|
|
|
>>> sdm_monomial_divides((1, 0, 0), (2, 0, 0)) |
|
False |
|
|
|
`A = x f_1` does not divide `B = f_1` |
|
|
|
>>> sdm_monomial_divides((1, 1, 0), (1, 0, 0)) |
|
False |
|
|
|
`A = xy^2 f_5` does not divide `B = y f_5` |
|
|
|
>>> sdm_monomial_divides((5, 1, 2), (5, 0, 1)) |
|
False |
|
""" |
|
return A[0] == B[0] and all(a <= b for a, b in zip(A[1:], B[1:])) |
|
|
|
|
|
|
|
|
|
def sdm_LC(f, K): |
|
"""Returns the leading coefficient of ``f``. """ |
|
if not f: |
|
return K.zero |
|
else: |
|
return f[0][1] |
|
|
|
|
|
def sdm_to_dict(f): |
|
"""Make a dictionary from a distributed polynomial. """ |
|
return dict(f) |
|
|
|
|
|
def sdm_from_dict(d, O): |
|
""" |
|
Create an sdm from a dictionary. |
|
|
|
Here ``O`` is the monomial order to use. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_from_dict |
|
>>> from sympy.polys import QQ, lex |
|
>>> dic = {(1, 1, 0): QQ(1), (1, 0, 0): QQ(2), (0, 1, 0): QQ(0)} |
|
>>> sdm_from_dict(dic, lex) |
|
[((1, 1, 0), 1), ((1, 0, 0), 2)] |
|
""" |
|
return sdm_strip(sdm_sort(list(d.items()), O)) |
|
|
|
|
|
def sdm_sort(f, O): |
|
"""Sort terms in ``f`` using the given monomial order ``O``. """ |
|
return sorted(f, key=lambda term: O(term[0]), reverse=True) |
|
|
|
|
|
def sdm_strip(f): |
|
"""Remove terms with zero coefficients from ``f`` in ``K[X]``. """ |
|
return [ (monom, coeff) for monom, coeff in f if coeff ] |
|
|
|
|
|
def sdm_add(f, g, O, K): |
|
""" |
|
Add two module elements ``f``, ``g``. |
|
|
|
Addition is done over the ground field ``K``, monomials are ordered |
|
according to ``O``. |
|
|
|
Examples |
|
======== |
|
|
|
All examples use lexicographic order. |
|
|
|
`(xy f_1) + (f_2) = f_2 + xy f_1` |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_add |
|
>>> from sympy.polys import lex, QQ |
|
>>> sdm_add([((1, 1, 1), QQ(1))], [((2, 0, 0), QQ(1))], lex, QQ) |
|
[((2, 0, 0), 1), ((1, 1, 1), 1)] |
|
|
|
`(xy f_1) + (-xy f_1)` = 0` |
|
|
|
>>> sdm_add([((1, 1, 1), QQ(1))], [((1, 1, 1), QQ(-1))], lex, QQ) |
|
[] |
|
|
|
`(f_1) + (2f_1) = 3f_1` |
|
|
|
>>> sdm_add([((1, 0, 0), QQ(1))], [((1, 0, 0), QQ(2))], lex, QQ) |
|
[((1, 0, 0), 3)] |
|
|
|
`(yf_1) + (xf_1) = xf_1 + yf_1` |
|
|
|
>>> sdm_add([((1, 0, 1), QQ(1))], [((1, 1, 0), QQ(1))], lex, QQ) |
|
[((1, 1, 0), 1), ((1, 0, 1), 1)] |
|
""" |
|
h = dict(f) |
|
|
|
for monom, c in g: |
|
if monom in h: |
|
coeff = h[monom] + c |
|
|
|
if not coeff: |
|
del h[monom] |
|
else: |
|
h[monom] = coeff |
|
else: |
|
h[monom] = c |
|
|
|
return sdm_from_dict(h, O) |
|
|
|
|
|
def sdm_LM(f): |
|
r""" |
|
Returns the leading monomial of ``f``. |
|
|
|
Only valid if `f \ne 0`. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_LM, sdm_from_dict |
|
>>> from sympy.polys import QQ, lex |
|
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(1), (4, 0, 1): QQ(1)} |
|
>>> sdm_LM(sdm_from_dict(dic, lex)) |
|
(4, 0, 1) |
|
""" |
|
return f[0][0] |
|
|
|
|
|
def sdm_LT(f): |
|
r""" |
|
Returns the leading term of ``f``. |
|
|
|
Only valid if `f \ne 0`. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_LT, sdm_from_dict |
|
>>> from sympy.polys import QQ, lex |
|
>>> dic = {(1, 2, 3): QQ(1), (4, 0, 0): QQ(2), (4, 0, 1): QQ(3)} |
|
>>> sdm_LT(sdm_from_dict(dic, lex)) |
|
((4, 0, 1), 3) |
|
""" |
|
return f[0] |
|
|
|
|
|
def sdm_mul_term(f, term, O, K): |
|
""" |
|
Multiply a distributed module element ``f`` by a (polynomial) term ``term``. |
|
|
|
Multiplication of coefficients is done over the ground field ``K``, and |
|
monomials are ordered according to ``O``. |
|
|
|
Examples |
|
======== |
|
|
|
`0 f_1 = 0` |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_mul_term |
|
>>> from sympy.polys import lex, QQ |
|
>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((0, 0), QQ(0)), lex, QQ) |
|
[] |
|
|
|
`x 0 = 0` |
|
|
|
>>> sdm_mul_term([], ((1, 0), QQ(1)), lex, QQ) |
|
[] |
|
|
|
`(x) (f_1) = xf_1` |
|
|
|
>>> sdm_mul_term([((1, 0, 0), QQ(1))], ((1, 0), QQ(1)), lex, QQ) |
|
[((1, 1, 0), 1)] |
|
|
|
`(2xy) (3x f_1 + 4y f_2) = 8xy^2 f_2 + 6x^2y f_1` |
|
|
|
>>> f = [((2, 0, 1), QQ(4)), ((1, 1, 0), QQ(3))] |
|
>>> sdm_mul_term(f, ((1, 1), QQ(2)), lex, QQ) |
|
[((2, 1, 2), 8), ((1, 2, 1), 6)] |
|
""" |
|
X, c = term |
|
|
|
if not f or not c: |
|
return [] |
|
else: |
|
if K.is_one(c): |
|
return [ (sdm_monomial_mul(f_M, X), f_c) for f_M, f_c in f ] |
|
else: |
|
return [ (sdm_monomial_mul(f_M, X), f_c * c) for f_M, f_c in f ] |
|
|
|
|
|
def sdm_zero(): |
|
"""Return the zero module element.""" |
|
return [] |
|
|
|
|
|
def sdm_deg(f): |
|
""" |
|
Degree of ``f``. |
|
|
|
This is the maximum of the degrees of all its monomials. |
|
Invalid if ``f`` is zero. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_deg |
|
>>> sdm_deg([((1, 2, 3), 1), ((10, 0, 1), 1), ((2, 3, 4), 4)]) |
|
7 |
|
""" |
|
return max(sdm_monomial_deg(M[0]) for M in f) |
|
|
|
|
|
|
|
|
|
def sdm_from_vector(vec, O, K, **opts): |
|
""" |
|
Create an sdm from an iterable of expressions. |
|
|
|
Coefficients are created in the ground field ``K``, and terms are ordered |
|
according to monomial order ``O``. Named arguments are passed on to the |
|
polys conversion code and can be used to specify for example generators. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_from_vector |
|
>>> from sympy.abc import x, y, z |
|
>>> from sympy.polys import QQ, lex |
|
>>> sdm_from_vector([x**2+y**2, 2*z], lex, QQ) |
|
[((1, 0, 0, 1), 2), ((0, 2, 0, 0), 1), ((0, 0, 2, 0), 1)] |
|
""" |
|
dics, gens = parallel_dict_from_expr(sympify(vec), **opts) |
|
dic = {} |
|
for i, d in enumerate(dics): |
|
for k, v in d.items(): |
|
dic[(i,) + k] = K.convert(v) |
|
return sdm_from_dict(dic, O) |
|
|
|
|
|
def sdm_to_vector(f, gens, K, n=None): |
|
""" |
|
Convert sdm ``f`` into a list of polynomial expressions. |
|
|
|
The generators for the polynomial ring are specified via ``gens``. The rank |
|
of the module is guessed, or passed via ``n``. The ground field is assumed |
|
to be ``K``. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_to_vector |
|
>>> from sympy.abc import x, y, z |
|
>>> from sympy.polys import QQ |
|
>>> f = [((1, 0, 0, 1), QQ(2)), ((0, 2, 0, 0), QQ(1)), ((0, 0, 2, 0), QQ(1))] |
|
>>> sdm_to_vector(f, [x, y, z], QQ) |
|
[x**2 + y**2, 2*z] |
|
""" |
|
dic = sdm_to_dict(f) |
|
dics = {} |
|
for k, v in dic.items(): |
|
dics.setdefault(k[0], []).append((k[1:], v)) |
|
n = n or len(dics) |
|
res = [] |
|
for k in range(n): |
|
if k in dics: |
|
res.append(Poly(dict(dics[k]), gens=gens, domain=K).as_expr()) |
|
else: |
|
res.append(S.Zero) |
|
return res |
|
|
|
|
|
|
|
|
|
def sdm_spoly(f, g, O, K, phantom=None): |
|
""" |
|
Compute the generalized s-polynomial of ``f`` and ``g``. |
|
|
|
The ground field is assumed to be ``K``, and monomials ordered according to |
|
``O``. |
|
|
|
This is invalid if either of ``f`` or ``g`` is zero. |
|
|
|
If the leading terms of `f` and `g` involve different basis elements of |
|
`F`, their s-poly is defined to be zero. Otherwise it is a certain linear |
|
combination of `f` and `g` in which the leading terms cancel. |
|
See [SCA, defn 2.3.6] for details. |
|
|
|
If ``phantom`` is not ``None``, it should be a pair of module elements on |
|
which to perform the same operation(s) as on ``f`` and ``g``. The in this |
|
case both results are returned. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_spoly |
|
>>> from sympy.polys import QQ, lex |
|
>>> f = [((2, 1, 1), QQ(1)), ((1, 0, 1), QQ(1))] |
|
>>> g = [((2, 3, 0), QQ(1))] |
|
>>> h = [((1, 2, 3), QQ(1))] |
|
>>> sdm_spoly(f, h, lex, QQ) |
|
[] |
|
>>> sdm_spoly(f, g, lex, QQ) |
|
[((1, 2, 1), 1)] |
|
""" |
|
if not f or not g: |
|
return sdm_zero() |
|
LM1 = sdm_LM(f) |
|
LM2 = sdm_LM(g) |
|
if LM1[0] != LM2[0]: |
|
return sdm_zero() |
|
LM1 = LM1[1:] |
|
LM2 = LM2[1:] |
|
lcm = monomial_lcm(LM1, LM2) |
|
m1 = monomial_div(lcm, LM1) |
|
m2 = monomial_div(lcm, LM2) |
|
c = K.quo(-sdm_LC(f, K), sdm_LC(g, K)) |
|
r1 = sdm_add(sdm_mul_term(f, (m1, K.one), O, K), |
|
sdm_mul_term(g, (m2, c), O, K), O, K) |
|
if phantom is None: |
|
return r1 |
|
r2 = sdm_add(sdm_mul_term(phantom[0], (m1, K.one), O, K), |
|
sdm_mul_term(phantom[1], (m2, c), O, K), O, K) |
|
return r1, r2 |
|
|
|
|
|
def sdm_ecart(f): |
|
""" |
|
Compute the ecart of ``f``. |
|
|
|
This is defined to be the difference of the total degree of `f` and the |
|
total degree of the leading monomial of `f` [SCA, defn 2.3.7]. |
|
|
|
Invalid if f is zero. |
|
|
|
Examples |
|
======== |
|
|
|
>>> from sympy.polys.distributedmodules import sdm_ecart |
|
>>> sdm_ecart([((1, 2, 3), 1), ((1, 0, 1), 1)]) |
|
0 |
|
>>> sdm_ecart([((2, 2, 1), 1), ((1, 5, 1), 1)]) |
|
3 |
|
""" |
|
return sdm_deg(f) - sdm_monomial_deg(sdm_LM(f)) |
|
|
|
|
|
def sdm_nf_mora(f, G, O, K, phantom=None): |
|
r""" |
|
Compute a weak normal form of ``f`` with respect to ``G`` and order ``O``. |
|
|
|
The ground field is assumed to be ``K``, and monomials ordered according to |
|
``O``. |
|
|
|
Weak normal forms are defined in [SCA, defn 2.3.3]. They are not unique. |
|
This function deterministically computes a weak normal form, depending on |
|
the order of `G`. |
|
|
|
The most important property of a weak normal form is the following: if |
|
`R` is the ring associated with the monomial ordering (if the ordering is |
|
global, we just have `R = K[x_1, \ldots, x_n]`, otherwise it is a certain |
|
localization thereof), `I` any ideal of `R` and `G` a standard basis for |
|
`I`, then for any `f \in R`, we have `f \in I` if and only if |
|
`NF(f | G) = 0`. |
|
|
|
This is the generalized Mora algorithm for computing weak normal forms with |
|
respect to arbitrary monomial orders [SCA, algorithm 2.3.9]. |
|
|
|
If ``phantom`` is not ``None``, it should be a pair of "phantom" arguments |
|
on which to perform the same computations as on ``f``, ``G``, both results |
|
are then returned. |
|
""" |
|
from itertools import repeat |
|
h = f |
|
T = list(G) |
|
if phantom is not None: |
|
|
|
hp = phantom[0] |
|
Tp = list(phantom[1]) |
|
phantom = True |
|
else: |
|
Tp = repeat([]) |
|
phantom = False |
|
while h: |
|
|
|
Th = [(g, sdm_ecart(g), gp) for g, gp in zip(T, Tp) |
|
if sdm_monomial_divides(sdm_LM(g), sdm_LM(h))] |
|
if not Th: |
|
break |
|
g, _, gp = min(Th, key=lambda x: x[1]) |
|
if sdm_ecart(g) > sdm_ecart(h): |
|
T.append(h) |
|
if phantom: |
|
Tp.append(hp) |
|
if phantom: |
|
h, hp = sdm_spoly(h, g, O, K, phantom=(hp, gp)) |
|
else: |
|
h = sdm_spoly(h, g, O, K) |
|
if phantom: |
|
return h, hp |
|
return h |
|
|
|
|
|
def sdm_nf_buchberger(f, G, O, K, phantom=None): |
|
r""" |
|
Compute a weak normal form of ``f`` with respect to ``G`` and order ``O``. |
|
|
|
The ground field is assumed to be ``K``, and monomials ordered according to |
|
``O``. |
|
|
|
This is the standard Buchberger algorithm for computing weak normal forms with |
|
respect to *global* monomial orders [SCA, algorithm 1.6.10]. |
|
|
|
If ``phantom`` is not ``None``, it should be a pair of "phantom" arguments |
|
on which to perform the same computations as on ``f``, ``G``, both results |
|
are then returned. |
|
""" |
|
from itertools import repeat |
|
h = f |
|
T = list(G) |
|
if phantom is not None: |
|
|
|
hp = phantom[0] |
|
Tp = list(phantom[1]) |
|
phantom = True |
|
else: |
|
Tp = repeat([]) |
|
phantom = False |
|
while h: |
|
try: |
|
g, gp = next((g, gp) for g, gp in zip(T, Tp) |
|
if sdm_monomial_divides(sdm_LM(g), sdm_LM(h))) |
|
except StopIteration: |
|
break |
|
if phantom: |
|
h, hp = sdm_spoly(h, g, O, K, phantom=(hp, gp)) |
|
else: |
|
h = sdm_spoly(h, g, O, K) |
|
if phantom: |
|
return h, hp |
|
return h |
|
|
|
|
|
def sdm_nf_buchberger_reduced(f, G, O, K): |
|
r""" |
|
Compute a reduced normal form of ``f`` with respect to ``G`` and order ``O``. |
|
|
|
The ground field is assumed to be ``K``, and monomials ordered according to |
|
``O``. |
|
|
|
In contrast to weak normal forms, reduced normal forms *are* unique, but |
|
their computation is more expensive. |
|
|
|
This is the standard Buchberger algorithm for computing reduced normal forms |
|
with respect to *global* monomial orders [SCA, algorithm 1.6.11]. |
|
|
|
The ``pantom`` option is not supported, so this normal form cannot be used |
|
as a normal form for the "extended" groebner algorithm. |
|
""" |
|
h = sdm_zero() |
|
g = f |
|
while g: |
|
g = sdm_nf_buchberger(g, G, O, K) |
|
if g: |
|
h = sdm_add(h, [sdm_LT(g)], O, K) |
|
g = g[1:] |
|
return h |
|
|
|
|
|
def sdm_groebner(G, NF, O, K, extended=False): |
|
""" |
|
Compute a minimal standard basis of ``G`` with respect to order ``O``. |
|
|
|
The algorithm uses a normal form ``NF``, for example ``sdm_nf_mora``. |
|
The ground field is assumed to be ``K``, and monomials ordered according |
|
to ``O``. |
|
|
|
Let `N` denote the submodule generated by elements of `G`. A standard |
|
basis for `N` is a subset `S` of `N`, such that `in(S) = in(N)`, where for |
|
any subset `X` of `F`, `in(X)` denotes the submodule generated by the |
|
initial forms of elements of `X`. [SCA, defn 2.3.2] |
|
|
|
A standard basis is called minimal if no subset of it is a standard basis. |
|
|
|
One may show that standard bases are always generating sets. |
|
|
|
Minimal standard bases are not unique. This algorithm computes a |
|
deterministic result, depending on the particular order of `G`. |
|
|
|
If ``extended=True``, also compute the transition matrix from the initial |
|
generators to the groebner basis. That is, return a list of coefficient |
|
vectors, expressing the elements of the groebner basis in terms of the |
|
elements of ``G``. |
|
|
|
This functions implements the "sugar" strategy, see |
|
|
|
Giovini et al: "One sugar cube, please" OR Selection strategies in |
|
Buchberger algorithm. |
|
""" |
|
|
|
|
|
|
|
|
|
|
|
P = [] |
|
|
|
|
|
S = [] |
|
Sugars = [] |
|
|
|
def Ssugar(i, j): |
|
"""Compute the sugar of the S-poly corresponding to (i, j).""" |
|
LMi = sdm_LM(S[i]) |
|
LMj = sdm_LM(S[j]) |
|
return max(Sugars[i] - sdm_monomial_deg(LMi), |
|
Sugars[j] - sdm_monomial_deg(LMj)) \ |
|
+ sdm_monomial_deg(sdm_monomial_lcm(LMi, LMj)) |
|
|
|
ourkey = lambda p: (p[2], O(p[3]), p[1]) |
|
|
|
def update(f, sugar, P): |
|
"""Add f with sugar ``sugar`` to S, update P.""" |
|
if not f: |
|
return P |
|
k = len(S) |
|
S.append(f) |
|
Sugars.append(sugar) |
|
|
|
LMf = sdm_LM(f) |
|
|
|
def removethis(pair): |
|
i, j, s, t = pair |
|
if LMf[0] != t[0]: |
|
return False |
|
tik = sdm_monomial_lcm(LMf, sdm_LM(S[i])) |
|
tjk = sdm_monomial_lcm(LMf, sdm_LM(S[j])) |
|
return tik != t and tjk != t and sdm_monomial_divides(tik, t) and \ |
|
sdm_monomial_divides(tjk, t) |
|
|
|
P = [p for p in P if not removethis(p)] |
|
|
|
|
|
N = [(i, k, Ssugar(i, k), sdm_monomial_lcm(LMf, sdm_LM(S[i]))) |
|
for i in range(k) if LMf[0] == sdm_LM(S[i])[0]] |
|
|
|
N.sort(key=ourkey) |
|
remove = set() |
|
for i, p in enumerate(N): |
|
for j in range(i + 1, len(N)): |
|
if sdm_monomial_divides(p[3], N[j][3]): |
|
remove.add(j) |
|
|
|
|
|
P.extend(reversed([p for i, p in enumerate(N) if i not in remove])) |
|
P.sort(key=ourkey, reverse=True) |
|
|
|
return P |
|
|
|
|
|
try: |
|
|
|
|
|
|
|
numgens = len(next(x[0] for x in G if x)[0]) - 1 |
|
except StopIteration: |
|
|
|
if extended: |
|
return [], [] |
|
return [] |
|
|
|
|
|
|
|
coefficients = [] |
|
|
|
|
|
for i, f in enumerate(G): |
|
P = update(f, sdm_deg(f), P) |
|
if extended and f: |
|
coefficients.append(sdm_from_dict({(i,) + (0,)*numgens: K(1)}, O)) |
|
|
|
|
|
while P: |
|
i, j, s, t = P.pop() |
|
f, g = S[i], S[j] |
|
if extended: |
|
sp, coeff = sdm_spoly(f, g, O, K, |
|
phantom=(coefficients[i], coefficients[j])) |
|
h, hcoeff = NF(sp, S, O, K, phantom=(coeff, coefficients)) |
|
if h: |
|
coefficients.append(hcoeff) |
|
else: |
|
h = NF(sdm_spoly(f, g, O, K), S, O, K) |
|
P = update(h, Ssugar(i, j), P) |
|
|
|
|
|
|
|
S = {(tuple(f), i) for i, f in enumerate(S)} |
|
for (a, ai), (b, bi) in permutations(S, 2): |
|
A = sdm_LM(a) |
|
B = sdm_LM(b) |
|
if sdm_monomial_divides(A, B) and (b, bi) in S and (a, ai) in S: |
|
S.remove((b, bi)) |
|
|
|
L = sorted(((list(f), i) for f, i in S), key=lambda p: O(sdm_LM(p[0])), |
|
reverse=True) |
|
res = [x[0] for x in L] |
|
if extended: |
|
return res, [coefficients[i] for _, i in L] |
|
return res |
|
|