random()in the argument of
myrandomis that the random algorithm in pari is too repetitive mod powers of two.) In GP/PARI 2.1.4 this has become
qflll(m,1)one computes a reduced basis of the lattice spanned by the columns of
min 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.
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
By the way, we have not found any example where
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
matkerint(m), which produces worse intermediate generators
for the kernel (even faster).