myrandom()=random()>>16+random();
n=60;m=matrix(n,2*n,X,Y,myrandom());
random() in the argument
of myrandom is that the random algorithm in pari is too
repetitive mod powers of two.)
In GP/PARI 2.1.4 this has become
myrandom()=shift(random(),-16)+random() qflll(m,1) one computes a reduced basis of the lattice
spanned by the columns of m in time = 10h, 3mn on
my SPARC. (Guess what the lattice is!) (This is some years ago.)
This is an extended LLL algorithm, although my complexity analysis
does not apply to it. But with a not extended LLL as in this
C source
it takes only 6h, 28mn. See the
GP/Pari version if you prefer it readable.
Even better is the following strategy. First do a not extended LLL with the low quality ratio 1/3. (time = 53mn, 17,261 ms.). Then do a not extended LLL on the result of that with the high quality ratio 99/100 which is customary in GP/PARI. (time = 3mn, 43,433 ms.) Together this takes less than an hour, compared with the original 10h, 3mn.
The algorithm extendedlll,
to which the complexity
analysis does apply, takes time = 12h, 37mn, 18,752 ms. This is when we use the
mode in which it does not make part of the transformation matrix
LLL reduced, but just keeps it within known bounds.
That is the analogue of qflll(m,1).
By the way, we have not found any example where qflll(m,1)
produces a transformation matrix that misbehaves.
We simply don't know what it may do.
Another useful mode of extendedlll is where
it does not try to get anything LLL reduced, but just separates out the
dependencies between the generators. It thus quickly produces
generators for kernel and image of m as a map between
free modules. One can then reduce the generators
of kernel and image separately, if desired. This gives a good alternative
to matkerint(m), which produces worse intermediate generators
for the kernel (even faster).