Re: polredabs failure

[Igor Schein <igor@txc.com>]

On Fri, Oct 10, 2003 at 05:46:04PM +0200, Karim BELABAS wrote:
> On Thu, 9 Oct 2003, Igor Schein wrote:
> > Now, continuing the same topic:
> >
> > %1 = x^16 - 4*x^15 + 8*x^14 - 8*x^13 + 6*x^12 - 16*x^11 + 40*x^10 - 32*x^9 - 50*x^8 + 160*x^7 - 176*x^6 + 40*x^5 + 140*x^4 - 192*x^3 + 112*x^2 - 32*x + 4
> > ? polredabs(%)
> > %2 = x^16 - 4*x^15 + 12*x^14 - 36*x^13 + 88*x^12 - 164*x^11 + 252*x^10 - 324*x^9 + 354*x^8 - 324*x^7 + 252*x^6 - 164*x^5 + 88*x^4 - 36*x^3 + 12*x^2 - 4*x + 1
> > ? polredabs(%)
> > %3 = x^16 - 8*x^15 + 36*x^14 - 108*x^13 + 244*x^12 - 436*x^11 + 636*x^10 - 780*x^9 + 831*x^8 - 780*x^7 + 636*x^6 - 436*x^5 + 244*x^4 - 108*x^3 + 36*x^2 - 8*x + 1
> > \\ Takes 2 iterations to stabilize
> 
> These polynomials have the same norm. All are valid results, and there's no
> guarantee that iterating polredabs as above stabilizes at all.

But now, after the change mentioned below, it indeed *stabilizes*
after 1 interation.  And I suspect it won't be easy to find another
example of behavior above - I couldn't so far.

> 
> > Also...
> > ? #polredabs(%1,4)
> > %4 = 13
> > ? #polredabs(%2,4)
> > %5 = 22
> > ? #polredabs(%3,4)
> > %6 = 24
> >
> > What is causing discrepancy between the last 3 results, precision
> > issues or probabilistic nature of algorithm?
> 
> The algorithm is not probabilistic, but changing the input yields a priori
> different behaviour. What exactly occurs is that a fixed number of vectors of
> minimal norm are stored, the rest being discarded. Since many of them have
> the same characteristic polynomial, it may occur that some polynomial is not
> represented in the end.
> 
> This does not follow the documented behaviour of the (,4) flag, and is rather
> pointless. I have made the above buffersize dynamic, so that no minimal vector
> should ever be discarded [ in polredabs. It's too dangerous in a general
> situation... ]

I have another regression caused by this change:

? polredabs(x^32+12*x^30+72*x^28-1812*x^26+13982*x^24-46404*x^22+78120*x^20-5868*x^18-71487*x^16+11736*x^14+312480*x^12+371232*x^10+223712*x^8+57984*x^6+4608*x^4-1536*x^2+256)
  ***   bug in GP (Segmentation Fault), please report

Thanks

Igor