Karim BELABAS on Tue, 18 Mar 2003 00:38:42 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: QX_caract |
On Mon, 17 Mar 2003, Bill Allombert wrote: > On Sat, Mar 15, 2003 at 03:29:46PM +0100, Karim BELABAS wrote: > > On Wed, 5 Mar 2003, Bill Allombert wrote: > > > Why not use the modular algorithm of ZX_caract directly in QX_caract > > > instead of removing the content and calling ZX_caract ? [...] > > OK, this is implemented in CVS. The modulus bound is rigorous (~ Hadamard > > bound + floating point computation if bound is huge). > > Thanks ! I have tried it and polred seems to be much faster on my degree > 72 polynomials. > > At least it use a bound of 2^16000 instead of 2^3000000 (72 times...). > Of course this is still much too large or else polred is a complete > failure (we expect polred to give small polynomial after all), but at > least this is bearable. (it take 9 minutes instead of 7 hours.) Note that the polred final phase is quite inefficient in any case. The way polredabs does it is to use floating point approximations for the roots (which need to be computed in any case for the LLL reduction), then round. Actually, the first phase of polredabs [ polredabs + fincke_pohst excluding smallvectors ] _is_ a polred, and should be much faster when LLL takes negligible time. How does it fare in your example ? Try at \g4 for instance, and stop it when you see the "smallvectors looking for..." message. It should already print subfield information (overkill in degree 72 where we have no chance of completing the enumeration anyway) and reduced generators (the _same_ that polred would print). Note that due to the LLL code reorganization, polred is mostly an empty wrapper now (we have common LLL driver routines for nfinit/polred/polredabs): the "tough" part is handled by nfbasic_init(x, flag, fa, &T); if (T.lead) err(impl,"polred for non-monic polynomial"); set_LLL_basis(&T, &ro); which are also the first steps of polredabs(), and includes the maximal order computation and LLL reduction. Then there is the inefficient QX_caract loop to compute the characteristic polynomials. polredabs() + skip almost everything in fincke_pohst() + early exit should replace it some day. Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]