[fricas-devel] addition of ExtendedPolynomialReduction

[Ralf Hemmecke]

Hello,

I'm currently preparing an article that involves Gröbner basis
computation and then finding the representation of some polynomial in
terms of that Gröbner basis. Doing this in FriCAS, is, of course, easy,
but I was unable to find that such an extended reduction is already
implemented in FriCAS.

What about the following?

https://github.com/hemmecke/fricas/commit/1ea2f36f0a2bf8dd251cbb0fb6ab810b734d2c88.patch

The new domain can be used like this.

(1) -> Z ==> Integer
(2) -> vl := [x,y,z]

(2) [x, y, z]
(3) -> E ==> DirectProduct(3, NNI)
(4) -> P ==> GeneralDistributedMultivariatePolynomial(vl, Z, E)
(5) -> G: List P := [x^5-x^4*y^3+2*z, y^4-z^3]

5 4 3 4 3
(5) [x - x y + 2 z, y - z ]
(6) -> p: P := x^7

7
(6) x
(7) -> z := reduce(p, G)$ExtendedPolynomialReduction(Z, E, P)

(7)
4 6 2 3 2 4
[poly = - x y z + 2 x z + 2 x y z + 2 y z ,
2 3 6 4 5 4 3 2
repr = [- x - x y - y , - x y - x y z + 2 y z], mult = - 1]
(8) -> z.mult * p - (z.poly + z.repr.1 * G.1 + z.repr.2 * G.2)

(8) 0

May I commit?

Ralf

[Waldek Hebisch]

Post by Ralf Hemmecke
Hello,
I'm currently preparing an article that involves GrĂśbner basis
computation and then finding the representation of some polynomial in
terms of that GrĂśbner basis. Doing this in FriCAS, is, of course, easy,
but I was unable to find that such an extended reduction is already
implemented in FriCAS.
What about the following?
https://github.com/hemmecke/fricas/commit/1ea2f36f0a2bf8dd251cbb0fb6ab810b734d2c88.patch

Looks good. However, comment:

-- Reduce the non-leading terms of x (which is assumed to be non-zero).
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

looks strange: I see no check preventing zero and no mathematical
reason for zero (AFAICS one use 'reduce' to get representation of ideal
members, in such case polynomial part of x is 0). Probably
'tailReduce' needs quick exit for 0.

Post by Ralf Hemmecke
The new domain can be used like this.
(1) -> Z ==> Integer
(2) -> vl := [x,y,z]
(2) [x, y, z]
(3) -> E ==> DirectProduct(3, NNI)
(4) -> P ==> GeneralDistributedMultivariatePolynomial(vl, Z, E)
(5) -> G: List P := [x^5-x^4*y^3+2*z, y^4-z^3]
5 4 3 4 3
(5) [x - x y + 2 z, y - z ]
(6) -> p: P := x^7
7
(6) x
(7) -> z := reduce(p, G)$ExtendedPolynomialReduction(Z, E, P)
(7)
4 6 2 3 2 4
[poly = - x y z + 2 x z + 2 x y z + 2 y z ,
2 3 6 4 5 4 3 2
repr = [- x - x y - y , - x y - x y z + 2 y z], mult = - 1]
(8) -> z.mult * p - (z.poly + z.repr.1 * G.1 + z.repr.2 * G.2)
(8) 0
May I commit?

OK (after you look at the issue).

[Ralf Hemmecke]

Post by Waldek Hebisch

Post by Ralf Hemmecke
https://github.com/hemmecke/fricas/commit/1ea2f36f0a2bf8dd251cbb0fb6ab810b734d2c88.patch

-- Reduce the non-leading terms of x (which is assumed to be non-zero).
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
looks strange: I see no check preventing zero and no mathematical
reason for zero (AFAICS one use 'reduce' to get representation of ideal
members, in such case polynomial part of x is 0). Probably
'tailReduce' needs quick exit for 0.

Indeed that comment looks strange. I've removed it and also added the
zero test.

However, the code was not wrong, because the loop in tailReduce runs
with the condition zero?(p). There was only a "leadingMonomial(0)" and
"reductum(0)". But both of them yield 0 according to the specification
in FiniteAbelianMonoidRing

http://fricas.github.io/api/AbelianMonoidRing.html#l-abelian-monoid-ring-reductum

Oh... I just now see that for leadingMonomial the specification is not
so explicit, but at least the implementation of PolynomialRing is fine.

http://fricas.github.io/api/AbelianMonoidRing.html#l-abelian-monoid-ring-leading-monomial

https://github.com/hemmecke/fricas/blob/master-hemmecke/src/algebra/poly.spad#L348

but at least the implementation of PolynomialRing is fine.

Actually, I don't think that code should rely on leadingMonomial(0)=0 or
reductum(0)=0. Waldek, what's your opinion on that?

Ralf

[Ralf Hemmecke]

Now thinking about the "reductum(0)=0" assumption.
I can easily remove it from my code (see below).

tailReduce(x: X, basis: List X): X ==
empty? basis => x
p: R := polynomial x
-- We iterate over the non-leading terms of polynomial(x).
r: R := 0
v: V := representation x
m: C := multiplier x
-- We keep the representation part attached to p and hand it
-- over to denominatorFreeTopReduce. Thus we get the representation
-- from the reduced polynomial.
while not zero? p repeat
r := r + leadingMonomial p
p := reductum p
x := denominatorFreeTopReduce([p, v, 1], basis)
v := representation x
p := polynomial x
m := multiplier(x) * m
r := multiplier(x) * r
[r, v, m]


and compare with
https://github.com/fricas/fricas/commit/a4c3af045560d631f06c68ca542676b84cd227d2#diff-ebde1584f365f97c30d05da63bb4ba4bR117

Waldek, would you prefer this new code in another commit? (I think I
should have done that rewrite before. Sorry.)

I just had a quick check. I modified
GeneralDistributedMultivariatePolynomial in such a way that it gives an
error on reductum(0). Then my test code does not even reach
reduce$ExtendedPolynomialReduction, because groebner stops with the
reductum(0) error.

Ralf