Karim Belabas on Fri, 04 Feb 2005 19:44:58 +0100

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

Re: infinite loop using qflllgram on an opteron

* Lars Fischer [2005-01-20 22:58]:
> I am running into trouble using qflllgram on an Opteron machine, while 
> the same calculation on 32-bit AMD-XP and Athlon-64 works without problems.
> I have several thousand 70x70 matrices G_i with integer entries. Each 
> entry is about 100 digits long.
> On an Opteron with pari-2.2.9:
> qflllgram(G_i) takes about 2 minutes for 95 percent of the i's .
> But in 5 percent of my matrices, the calculation runs for hours, without 
> any result.
> Now I tried several things with some of the problem matrices:
> -On a 32 bit Desktop AMD-XP and a Athlon-64 the calculation finished 
> without Problem.
> -I compiled pari without optimizations -O0, no change.
> -Using pari-2.2.8 on the Opteron, some of my problem matrices finished 
> also, but the rest did not.
> I found
> http://pari.math.u-bordeaux.fr/archives/pari-dev-0301/msg00048.html
> It is suggested to increase the memory. I tried it with 130, 230, 330, 
> 500, 800 and 1000 MB. Always the same: an infinite loop. (And for 95 
> percent of the matrices 130 MB was enough.)
> I inserted \gm 2, as also suggested. The output ends like

You should also add \g4. It would show a large number of precision doubling.

> Has anybody noticed the same problem?
> Can you give me advice how to avoid it?

You can always use qflllgram(x, 1) which will be much slower [ generically ]
but is guaranteed to converge.

Can you send me a problematic matrix ? I'll try and see whether the
Opteron (or compiler) is at fault, or my strategy.  [ What's the
compiler by the way ? ]



PS: a new adaptive Schnorr-Euchner scheme for LLL-reduction [with guaranteed
convergence, and still good theoretical complexity] has recently been proposed
by NGuyen & Stehle. It is pending implementation in PARI...
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]