Proper implementation of quotients of g-algebras and polynomial rings

[simon-king-jena]

The wrapper at #4539 originally tried to use Singular for computations in quotients of g-algebras. But for some reasons it did not work, and thus it was decided to temporarily use generic quotient rings, so that the ticket can be merged.

The purpose here is to use rings constructed by Singular from a "ring list", which should provide a more efficient implementation.

There should also be a proper implementation for the commutative case as well. Currently, generic code is used:

sage: P.<x,y,z> = QQ[]
sage: I = [x^2+x*y*z,y^2-z^3*y,z^3+y^5*x*z]*P
sage: Q = P.quotient(I)
sage: type(Q)
<class 'sage.rings.quotient_ring.QuotientRing_generic_with_category'>

Depends on #4539

CC: @burcin @saliola @mwhansen @alexanderdreyer @sagetrac-OleksandrMotsak @sagetrac-PolyBoRi @malb

Component: algebra

Keywords: g-algebra Singular quotient

Issue created by migration from https://trac.sagemath.org/ticket/11878

[simon-king-jena]

comment:1

It turns out that the code for the quotients from #4539 did not work properly, because comparison of elements of g-algebras did not take into account the relations.

[simon-king-jena]

comment:2

I have a question, and probably Oleksandr knows the answer:

Assume we are in a quotient ring Q (not sca) in Singular. As we know, the normal form of a polynomial p with respect to the defining ideal of the quotient ring is not automatically computed. But it can be obtained by NF(p,std(0)).

I tried to create a Gröbner strategy object G for the zero ideal in Q. However, G.normal_form(p) did not reduce p. G.normal_form relies on the function redNF, I guess from Singular's kstd2.cc.

Is redNF the wrong thing to use in quotient rings? I see that redNF accepts several arguments, that seem to be undocumented (like many functions in Singular). Do I simply have to choose other arguments? Is it possible to obtain reduction with respect to the defining ideal of a quotient ring by using a Gröbner strategy object, or is that the wrong approach?

I found another function kNF2 in kstd2.cc, which seems to have an argument for the defining ideal of a quotient ring; should I use this? Would the result be tail reduced? I am afraid it would be less efficient than using a fixed Gröbner strategy, but perhaps that's the only way.

Or, positively asked: What Singular function called from NF is responsible for the reduction of quotient ring elements?

[simon-king-jena]

comment:3

I think I start to understand. The function initS initialises a Gröbner strategy in Singular, and in principle it can take an argument for the defining ideal of a quotient ring. However, it is currently used in the form initS(i, NULL, self._strat), hence, the defining ideal is NULL. So, that's where the fix should happen.

[simon-king-jena]

comment:4

I broadened the purpose of the ticket: Implementing quotients of multivariate polynomial rings via Singular should be just as easy as implementing quotients of g-algebras via Plural.

There is a design problem for the elements, though. I see three approaches:

1. Have a single class of elements for quotients and non-quotients. Do a reduction with respect to the modulus (if there is any) when comparing, hashing or printing elements.
2. Have two separate classes, essentially copying the old MPolynomial_libsingular class for creating a NCPolynomial_plural class. The change would mainly amount to replacing the strings MP and _libsingular by NCP and _plural, respectively.
3. Have two separate classes, but avoid code-duplication. For this to work, one needs to modify the arithmetic methods of MPolynomial_libsingular, such that for example left._add_(right) does not return a new instance of MPolynomial_libsingular, but a new instance of left.__class__.

All three approaches have disadvantages: The first approach may slow down the arithmetic of polynomials, since any call to hash, repr and cmp would involve a test whether the parent is a quotient ring. The second would imply a massive code duplication. The third may, again, slow down arithmetic, since (as in the first approach) arithmetic is spoiled by additional tests.

Modern editors are capable to copy-and-paste, and I prefer speed. Thus, I'll go for the second approach, unless one of you objects.

[simon-king-jena]

comment:5

If one goes for the second approach, one should use the occasion and refactor the code of sage.rings.polynomial.plural, so that g-algebras and their elements will be defined in separate modules.

[sagetrac-PolyBoRi]

comment:6

using
Singulars reduce generated by singular_function
should automatically deal with the quotients and still sufficiently fast (for generation of rings). Of course, similarly to the usual case where we attach the GB to an ideal as strategy,
we can attach the quotient ideal here to the ring.
Do not ask me about any internal Singular details at the moment.
I suggest repairing things in a most clean way (and do a performant patch later).
In fact using the later patch, we might be again be faster than Singular itself (as we can eliminate the repeated initialization of the strat object).