Igor Schein on Tue, 4 Feb 2003 20:39:24 -0500 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs() observation |
On Tue, Feb 04, 2003 at 09:33:08PM +0100, Karim BELABAS wrote: > On Fri, 31 Jan 2003, Igor Schein wrote: > > > On Tue, Jan 28, 2003 at 10:09:08AM -0500, Igor Schein wrote: > >> polredabs() on the following polynomial is much slower in latest CVS compared to stable: > >> > >> x^16-224*x^14+19520*x^12-843488*x^10+19172700*x^8-223732800*x^6+1177835136*x^4-1779647552*x^2+171662404 > > > > Actually, here's the very recent change that made polredabs() > > considerably slower in many cases: > > > > \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ > > revision 1.627 > > date: 2003/01/04 19:00:43; author: karim; state: Exp; lines: +2 -0 > > 48- simplified fincke_pohst() [don't recompute gram_matrix] > > \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ > > > > And here's a smaller yet even more drastic example: > > > > polredabs(x^4+51976*x^3+837697192*x^2+4716826989696*x+5560701377110272); > > Typo: the smallvectors() bound was the square of what it should have been... > I was confused by the terse comment [ due to me, from code > reverse-engineering ] at the header of sqred1(), and didn't check which > "Cholesky form" it was about. It turned out it was not the standard one:-(. > > Both fixed. It's still pretty much broken. Consider the following trivial cases: polredabs(x^4+10^80*x^2+1,16) precision issue, takes years polredabs(x^8+10^80*x^4+1,16) too many vectors, also takes years Both used to finish in no time. Thanks Igor