[GiNaC-list] factor() hangs on a simple expression, randomly

[Vitaly Magerya]

On 12/22/2017 10:09 AM, Richard B. Kreckel wrote:
> On 11/30/2017 05:16 PM, Vitaly Magerya wrote:
>>     > factor((2*x-l)^2*(-1+6*x-l)*(-1+3*x-l)*(-2+4*x-l)*(1+4*x-l)*(4*x-l)*(2+4*x-l));
>>
>> At this point ginsh either hangs (80% of cases), or gives the correct
>> result (20% of cases).
> 
> How did you find this polynomial which makes Hensel lifting keep
> failing?

I'm currently writing a particular tool related to high energy physics
with GiNaC, and that polynomial is a charpoly of one of the matrices I'm
working with.

> How many of them are there?

As many as you want, but not as many as you'd think: most of similar
polynomials are factor()ized easily, and yet you can construct enough of
hanging examples too. E.g.:

    (7+4*x+l)*(-5+2*x-l)*(-6+6*x+l)*l*(10+2*x+l)
    (8+6*x-l)*(-5+4*x-l)*(-5+6*x+l)*(-2+2*x-l)*(2+4*x+l)
    (-9+7*x+l)*(-5+6*x+l)*(4+2*x+l)*(5+2*x-l)*(7+9*x-l)*(8+6*x-l)

I haven't looked into the factorization algorithm to know what makes
these particular polys special.

> Are they always multivariate?

Seems that way. I only really care for the bivariate case though, so who
knows.

> Do they always fail sometimes, work at other times?

Seems so, yes.

> If the answer to the last two questions is yes, then we might add a stop
> condition and when that has been reached, try factorizing with an
> alternative permutation of symbols.

This may be a reasonable workaround (if it doesn't affect the
non-hanging cases), but I'd personally be wary of treating a symptom
without understanding the underlying cause.