Karim Belabas on Wed, 12 May 2004 11:25:33 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: round4 performance

* Bill Allombert [2004-05-08 19:32]:
> On Wed, May 05, 2004 at 08:35:40PM +0200, Xavier-François Roblot wrote:
> > Well, I have modified update_alpha (after Karim pointed out a strange
> > behavior in this function) and that kind of miraculously speed up
> > dramatically that example!... As you will see, the computing time is now
> > very reasonable and it runs with a small stack too (I hope the result is
> > still correct though, I haven't checked yet). Igor, Karim and I still
> > have some ideas for improvements for nilord but you need some new bad
> > polynomials to test them. Please send me your worst examples!
> Well, I have retested and now this is much faster, also respm was
> improved, so galoisinit() is a bit faster also.
> Igor example needs 41s and 16MB of RAM.

Can you update and test again ? I have cleaned up my respm() improvements
and may have introduced regressions.

The main idea is to replace plain hnfmodid() by
-- hnfmodidpart() [ don't clean up upper triangular matrix once diagonal 
is known ] 

-- hnfmodidraw() [ reduce mod d * Id, but don't append d * Id ].

I have checked carefully each use of the function to see which of the above
applied, but I may have made a mistake. [ Currently, plain hnfmodid() is
not used anymore. ]


Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/ 
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]