Possible bug when computing polynomial gcd

[Valentin Hirschi]

Dear Fricas developers,

I am playing around benchmarking CAS for the computation of polynomial GCDs with tests similar as those given in this paper: https://arxiv.org/pdf/2304.13418.pdf.

More specifically I am using the following test using `Symbolica` Python API:

```python

a = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)^7 - 1').to_rational_polynomial()
b = Expression.parse('(1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)^7 + 1').to_rational_polynomial()
g = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)^7 + 3').to_rational_polynomial()
ag = a * g
bg = b * g
print(g.gcd(bg) - g)

```

Which runs in about 7 seconds on my laptop and prints out the expected 0.

Then with `FriCAS`, I am doing:
```

a := (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)^7 - 1;

b := (1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)^7 + 1;

g := (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)^7 + 3;

ag := a * g;

bg := b * g;

gcd(ag, bg) -g

```

which runs in about 25 seconds on my laptop but *does not evaluate to zero*!

My question is thus two-fold:

a) Is this non-zero result expected? What is the proper way to get the correct GCD?

b) Is my usage of `gcd` above the fastest way to compute polynomial GCDs and therefore a fair comparison with other CAS?

Thank you for your help,

--

Valentin

[Ralf Hemmecke]

Have you tried

gcd(ag, bg) + g

?

Note that -1 is a unit.

It also runs 20 sec on my laptop.

RalfHave you tried

gcd(ag, bg) + g

?

Note that -1 is a unit.

It also runs 20 sec on my laptop.

Ralf

[Waldek Hebisch]

Dnia Thu, Sep 14, 2023 at 09:02:38PM +0200, Valentin Hirschi napisał(a):
> Dear Fricas developers,
>
> I am playing around benchmarking CAS for the computation of polynomial GCDs
> with tests similar as those given in this paper:
> https://arxiv.org/pdf/2304.13418.pdf.
>
> More specifically I am using the following test using `Symbolica

> <https://symbolica.io/>` Python API:

>
> ```python
> a = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 +
> 15*x7)^7 - 1').to_rational_polynomial()
> b = Expression.parse('(1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 +
> 15*x7)^7 + 1').to_rational_polynomial()
> g = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 -
> 15*x7)^7 + 3').to_rational_polynomial()
> ag = a * g
> bg = b * g
> print(g.gcd(bg) - g)
> ```
>
> Which runs in about 7 seconds on my laptop and prints out the expected 0.
>
> Then with `FriCAS`, I am doing:
> ```
>
> a := (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)^7 - 1;
>
> b := (1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)^7 + 1;
>
> g := (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)^7 + 3;
>
> ag := a * g;
>
> bg := b * g;
>
> gcd(ag, bg) -g
> ```
>

> which runs in about 25 seconds on my laptop but **does not evaluate to zero*
> *!

>
> My question is thus two-fold:
>
> a) Is this non-zero result expected? What is the proper way to get the
> correct GCD?

As Ralf wrote, gcd is not unique and FriCAS produces correct gcd, but
different to what you expect. In FriCAS appropriate test is:

(6) -> gg := gcd(ag, bg);

Type: Polynomial(Integer)
Time: 0 (IN) + 13.30 (EV) + 0.01 (OT) = 13.31 sec
(7) -> gg exquo g

(7) - 1
Type: Union(Polynomial(Integer),...)
Time: 0 (IN) + 0 (EV) + 0.00 (OT) = 0.00 sec

> b) Is my usage of `gcd` above the fastest way to compute polynomial GCDs
> and therefore a fair comparison with other CAS?

gcd command is supposed to use fastest method so this is fair. There
is one method to make things faster (if you did not do this already).
Namely, compile FriCAS yourself passing to configure additional
option '--enable-algebra-optimization="((speed 3) (safety 0))"'.

On fast machine using FriCAS build without this option gcd need
17.09s. Build with that option needs 13.31s.

--
Waldek Hebisch