Igor Schein on Fri, 10 Oct 2003 13:30:18 -0400 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs failure |
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