Extended LLL versus ordinary LLL

Computing the transformation matrix does not come for free, especially when there are many relations between the original generators. To be specific, let us take a 60 by 120 matrix of random integers in GP/PARI 2.0.1. Like this:

(The reason to use more than one 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()
With 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).

Wilberd van der Kallen