SymmetricReductionStrategy provides a framework for efficient symmetric reduction of Infinite Polynomials, see infinite_polynomial_element.
AUTHORS:
THEORY:
According to M. Aschenbrenner and C. Hillar [AB2007], Symmetric
Reduction of an element of an Infinite Polynomial Ring
by some
other element
means the following:
- Let
and
be the leading terms of
and
.
- Test whether there is a permutation
that does not does not diminish the variable indices occurring in
and preserves their order, so that there is some term
with
. If there is no such permutation, return
.
- Replace
by
and continue with step 1.
When reducing one polynomial with respect to a list
of other
polynomials, there usually is a choice of order on which the
efficiency crucially depends. Also it helps to modify the polynomials
on the list in order to simplify the basic reduction steps.
The preparation of may be expensive. Hence, if the same list is
used many times then it is reasonable to perform the preparation only
once. This is the background of
SymmetricReductionStrategy.
Our current strategy is to keep the number of terms in the polynomials
as small as possible. For this, we sort by increasing number of
terms. If several elements of
allow for a reduction of
, we
chose the one with the smallest number of terms. Later on, it should
be possible to implement further strategies for choice.
When adding a new polynomial to
, we first reduce
with
respect to
. Then, we test heuristically whether it is possible to
reduce the number of terms of the elements of
by reduction modulo
. That way, we see best chances to keep the number of terms in
intermediate reduction steps relatively small.
EXAMPLES:
First, we create an infinite polynomial ring and one of its elements:
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = y[1]*y[3]+y[1]^2*x[3]
We want to symmetrically reduce it by another polynomial. So, we put this other polynomial into a list and create a Symmetric Reduction Strategy object:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*x[1]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
x_1*y_2^2
sage: S.reduce(p)
x_3*y_1^2 + y_3*y_1
The preceding is correct, since any permutation that turns y[2]^2*x[1] into a factor of y[1]^2*x[3] interchanges the variable indices 1 and 2 – which is not allowed in a symmetric reduction. However, reduction by y[1]^2*x[2] works, since one can change variable index 1 into 2 and 2 into 3. So, we add this to S:
sage: S.add_generator(y[1]^2*x[2])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
x_2*y_1^2,
x_1*y_2^2
sage: S.reduce(p)
y_3*y_1
The next example shows that tail reduction is not done, unless it is explicitly advised:
sage: S.reduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1])
x_3 + 2*x_2*y_1^2 + 3*x_1*y_2^2
sage: S.tailreduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1])
x_3
However, it is possible to ask for tailreduction already when the Symmetric Reduction Strategy is created:
sage: S2 = SymmetricReductionStrategy(X, [y[2]^2*x[1],y[1]^2*x[2]], tailreduce=True)
sage: S2
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
x_2*y_1^2,
x_1*y_2^2
with tailreduction
sage: S2.reduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1])
x_3
Bases: object
A framework for efficient symmetric reduction of InfinitePolynomial, see infinite_polynomial_element.
INPUT:
EXAMPLES:
sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]], good_input=True)
sage: S.reduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y_3 + 3*y_2^2*y_1 + 2*y_2*y_1^2
sage: S.tailreduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y_3
Add another polynomial to self.
INPUT:
NOTE:
Previously added polynomials may be modified. All input is prepared in view of an efficient symmetric reduction.
EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X)
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field
sage: S.add_generator(y[3] + y[1]*(x[3]+x[1]))
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
x_3*y_1 + x_1*y_1 + y_3
Note that the first added polynomial will be simplified when adding a suitable second polynomial:
sage: S.add_generator(x[2]+x[1])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
y_3,
x_2 + x_1
By default, reduction is applied to any newly added polynomial. This can be avoided by specifying the optional parameter ‘good_input’:
sage: S.add_generator(y[2]+y[1]*x[2])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
y_3,
x_1*y_1 - y_2,
x_2 + x_1
sage: S.reduce(x[3]+x[2])
-2*x_1
sage: S.add_generator(x[3]+x[2], good_input=True)
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
y_3,
x_3 + x_2,
x_1*y_1 - y_2,
x_2 + x_1
In the previous example, x[3] + x[2] is added without being reduced to zero.
Return the list of Infinite Polynomials modulo which self reduces.
EXAMPLES:
sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
y_2*y_1^2,
y_2^2*y_1
sage: S.gens()
[y_2*y_1^2, y_2^2*y_1]
Symmetric reduction of an infinite polynomial.
INPUT:
OUTPUT:
Reduction of p with respect to self.
NOTE:
If tail reduction shall be forced, use tailreduce().
EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [y[3]], tailreduce=True)
sage: S.reduce(y[4]*x[1] + y[1]*x[4])
x_4*y_1
sage: S.reduce(y[4]*x[1] + y[1]*x[4], notail=True)
x_4*y_1 + x_1*y_4
Last, we demonstrate the ‘report’ option:
sage: S = SymmetricReductionStrategy(X, [x[2]+y[1],x[2]*y[3]+x[1]*y[2]+y[4],y[3]+y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
y_3 + y_2,
x_2 + y_1,
x_1*y_2 + y_4 - y_3*y_1
sage: S.reduce(x[3] + x[1]*y[3] + x[1]*y[1],report=True)
:::>
x_1*y_1 + y_4 - y_3*y_1 - y_1
Each ‘:’ indicates that one reduction of the leading monomial was performed. Eventually, the ‘>’ indicates that the computation is finished.
Remove all polynomials from self.
EXAMPLES:
sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
y_2*y_1^2,
y_2^2*y_1
sage: S.reset()
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field
Define the list of Infinite Polynomials modulo which self reduces.
INPUT:
L – a list of elements of the underlying infinite polynomial ring.
NOTE:
It is not tested if L is a good input. That method simply assigns a copy of L to the generators of self.
EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: R = SymmetricReductionStrategy(X)
sage: R.setgens(S.gens())
sage: R
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
y_2*y_1^2,
y_2^2*y_1
sage: R.gens() is S.gens()
False
sage: R.gens() == S.gens()
True
Symmetric reduction of an infinite polynomial, with forced tail reduction.
INPUT:
OUTPUT:
Reduction (including the non-leading elements) of p with respect to self.
EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [y[3]])
sage: S.reduce(y[4]*x[1] + y[1]*x[4])
x_4*y_1 + x_1*y_4
sage: S.tailreduce(y[4]*x[1] + y[1]*x[4])
x_4*y_1
Last, we demonstrate the ‘report’ option:
sage: S = SymmetricReductionStrategy(X, [x[2]+y[1],x[2]*x[3]+x[1]*y[2]+y[4],y[3]+y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
y_3 + y_2,
x_2 + y_1,
x_1*y_2 + y_4 + y_1^2
sage: S.tailreduce(x[3] + x[1]*y[3] + x[1]*y[1],report=True)
T[3]:::>
T[3]:>
x_1*y_1 - y_2 + y_1^2 - y_1