You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
740 lines
21 KiB
740 lines
21 KiB
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
|
|
|
|
# Additional monomial tools.
|
|
|
|
|
|
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:]))
|
|
|
|
|
|
# The actual distributed modules code.
|
|
|
|
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)
|
|
|
|
|
|
# Conversion
|
|
|
|
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
|
|
|
|
# Algorithms.
|
|
|
|
|
|
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:
|
|
# "phantom" variables with suffix p
|
|
hp = phantom[0]
|
|
Tp = list(phantom[1])
|
|
phantom = True
|
|
else:
|
|
Tp = repeat([])
|
|
phantom = False
|
|
while h:
|
|
# TODO better data structure!!!
|
|
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:
|
|
# "phantom" variables with suffix p
|
|
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.
|
|
"""
|
|
|
|
# The critical pair set.
|
|
# A critical pair is stored as (i, j, s, t) where (i, j) defines the pair
|
|
# (by indexing S), s is the sugar of the pair, and t is the lcm of their
|
|
# leading monomials.
|
|
P = []
|
|
|
|
# The eventual standard basis.
|
|
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)
|
|
# apply the chain criterion
|
|
P = [p for p in P if not removethis(p)]
|
|
|
|
# new-pair set
|
|
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]]
|
|
# TODO apply the product criterion?
|
|
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)
|
|
|
|
# TODO mergesort?
|
|
P.extend(reversed([p for i, p in enumerate(N) if i not in remove]))
|
|
P.sort(key=ourkey, reverse=True)
|
|
# NOTE reverse-sort, because we want to pop from the end
|
|
return P
|
|
|
|
# Figure out the number of generators in the ground ring.
|
|
try:
|
|
# NOTE: we look for the first non-zero vector, take its first monomial
|
|
# the number of generators in the ring is one less than the length
|
|
# (since the zeroth entry is for the module generators)
|
|
numgens = len(next(x[0] for x in G if x)[0]) - 1
|
|
except StopIteration:
|
|
# No non-zero elements in G ...
|
|
if extended:
|
|
return [], []
|
|
return []
|
|
|
|
# This list will store expressions of the elements of S in terms of the
|
|
# initial generators
|
|
coefficients = []
|
|
|
|
# First add all the elements of G to S
|
|
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))
|
|
|
|
# Now carry out the buchberger algorithm.
|
|
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)
|
|
|
|
# Finally interreduce the standard basis.
|
|
# (TODO again, better data structures)
|
|
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
|