LLL(...,Strategy=>...) -- choose among different algorithms

Synopsis

Usage:

LLL(...,Strategy=>n)
Inputs:
- The strategy n can be one of the symbols or lists given below.

Description

There are several variants of the LLL reduction algorithm implemented. There are three all integer versions: NTL, CohenEngine, and CohenTopLevel. The NTL version (NTL is an excellent package written by Victor shoup) is generally the best, however, the top level version is written in the Macaulay2 language, and so is easily modifiable and can be used to understand the algorithm better. There are also a number of approximate LLL variants implemented in NTL. These use real numbers instead of exact integer arithmetic, and so are often much faster, but only provide approximate answers (i.e. the result might not be an LLL basis, only close to one). Much of the information here about NTL's algorithms comes directly from the NTL documentation (translated to be relevant here).

Here is the complete list of possible strategies:

LLL(m, Strategy => NTL)
LLL(m, Strategy => CohenEngine)
LLL(m, Strategy => CohenTopLevel)
LLL(m, Strategy => RealFP)
LLL(m, Strategy => RealQP)
LLL(m, Strategy => RealXD)
LLL(m, Strategy => RealRR)
LLL(m, Strategy => {Givens,RealFP})
LLL(m, Strategy => {Givens,RealQP})
LLL(m, Strategy => {Givens,RealXD})
LLL(m, Strategy => {Givens,RealRR})
LLL(m, Strategy => {BKZ,RealFP})
LLL(m, Strategy => {BKZ,RealQP})
LLL(m, Strategy => {BKZ,RealQP1})
LLL(m, Strategy => {BKZ,RealXD})
LLL(m, Strategy => {BKZ,RealRR})
LLL(m, Strategy => {BKZ,Givens,RealFP})
LLL(m, Strategy => {BKZ,Givens,RealQP})
LLL(m, Strategy => {BKZ,Givens,RealQP1})
LLL(m, Strategy => {BKZ,Givens,RealXD})
LLL(m, Strategy => {BKZ,Givens,RealRR})

The first three are similar all-integer algorithms, basically the one which appears in H. Cohen's book. The rest of the algorithms are approximate variants, provided by Victor Shoup's NTL package. For these, there are three choices to be made: (1) the reduction condition, (2) the choice of orthogonalization strategy, and (3) the choice of precision.

Reduction condition

default -- the classical LLL reduction condition
BKZ -- Block Korkin-Zolotarev reduction.This is slower, but yields a higher-quality basis, i.e., one with shorter vectors. For a description, see [C. P. Schnorr and M. Euchner, Proc. Fundamentals of Computation Theory, LNCS 529, pp. 68-85, 1991]. This basically generalizes the LLL reduction condition from blocks of size 2 to blocks of larger size.

Orthogonalization Strategy

default -- Classical Gramm-Schmidt Orthogonalization, This choice uses classical methods for computing the Gramm-Schmidt othogonalization. It is fast but prone to stability problems. This strategy was first proposed by Schnorr and Euchner in the paper mentioned above. The version implemented here is substantially different, improving both stability and performance.
Givens -- Givens Orthogonalization, This is a bit slower, but generally much more stable, and is really the preferred orthogonalization strategy. For a nice description of this, see Chapter 5 of [G. Golub and C. van Loan, Matrix Computations, 3rd edition, Johns Hopkins Univ. Press, 1996].

Precision

RealFP -- double
RealQP -- quad_float (quasi quadruple precision) useful when roundoff errors can cause problems
RealQP1 -- only available in the BKZ variant, uses double precision for the search phase of the BKZ reduction, and quad_float for the orthogonalization
RealXD -- xdouble (extended exponent doubles) useful when numbers get too big
RealRR -- RR (arbitrary precision floating point) useful for large precision and magnitudes

Generally speaking, the choice RealFP will be the fastest, but may be prone to roundoff errors and/or overflow.

Putting it all together

This subsection comes directly from Victor Shoup's LLL documentation

I think it is safe to say that nobody really understands how the LLL algorithm works. The theoretical analyses are a long way from describing what "really" happens in practice. Choosing the best variant for a certain application ultimately is a matter of trial and error.

The first thing to try is Strategy => RealFP. It is the fastest of the routines, and is adequate for many applications.

If there are precision problems, you will most likely get a warning message, something like "warning--relaxing reduction". If there are overflow problems, you should get an error message saying that the numbers are too big.

If either of these happens, the next thing to try is Strategy=>{Givens,RealFP}, which uses the somewhat slower, but more stable, Givens rotations. This approach also has the nice property that the numbers remain smaller, so there is less chance of an overflow.

If you are still having precision problems try Strategy=>RealQP or Strategy=>{Givens,RealQP}, which use quadratic precision.

If you are still having overflow problems, try Strategy=>RealXD or Strategy=>{Givens,RealXD}

I haven't yet come across a case where one *really* needs the extra precision available in the RealRR variants.

All of the above discussion applies to the BKZ variants as well. In addition, if you have a matrix with really big entries, you might try using Strategy=>{Givens,RealFP} or Strategy=>RealXD first to reduce the sizes of the numbers, before running one of the BKZ variants.

Also, one shouldn't rule out using the "all integer" LLL routines. For some highly structured matrices, this is not necessarily much worse than some of the floating point versions, and can under certain circumstances even be better.

i1 : m1 = map(ZZ^50, ZZ^50, (j,i) -> (i+1)^8 * (j+1)^4 + i + j + 2);

              50       50
o1 : Matrix ZZ   <-- ZZ

i2 : m = syz m1;

              50       47
o2 : Matrix ZZ   <-- ZZ

i3 : time LLL m;
     -- used 0.00706759 seconds

              50       47
o3 : Matrix ZZ   <-- ZZ

i4 : time LLL(m, Strategy=>CohenEngine);
     -- used 0.0372689 seconds

              50       47
o4 : Matrix ZZ   <-- ZZ

i5 : time LLL(m, Strategy=>CohenTopLevel);
     -- used 0.107082 seconds

              50       47
o5 : Matrix ZZ   <-- ZZ

i6 : time LLL(m, Strategy=>{Givens,RealFP});
     -- used 0.0101139 seconds

              50       47
o6 : Matrix ZZ   <-- ZZ

i7 : time LLL(m, Strategy=>{Givens,RealQP});
     -- used 0.0399651 seconds

              50       47
o7 : Matrix ZZ   <-- ZZ

i8 : time LLL(m, Strategy=>{Givens,RealXD});
     -- used 0.0436042 seconds

              50       47
o8 : Matrix ZZ   <-- ZZ

i9 : time LLL(m, Strategy=>{Givens,RealRR});
     -- used 0.247071 seconds

              50       47
o9 : Matrix ZZ   <-- ZZ

i10 : time LLL(m, Strategy=>{BKZ,Givens,RealQP});
     -- used 0.0935986 seconds

               50       47
o10 : Matrix ZZ   <-- ZZ

Further information

Default value: NTL
Function: LLL -- compute an LLL basis
Option key: Strategy -- an optional argument

Caveat

For most of the options, the columns do not need to be linearly independent. The strategies CohenEngine and CohenTopLevel currently require the columns to be linearly independent.

Functions with optional argument named Strategy :

addHook(...,Strategy=>...) -- see addHook -- add a hook function to an object for later processing
adjoint(...,Strategy=>...) (missing documentation)
annihilator(...,Strategy=>...) -- see annihilator -- the annihilator ideal
associatedPrimes(...,Strategy=>...) -- see associatedPrimes -- find associated primes
basis(...,Strategy=>...) -- see basis -- basis or generating set of all or part of a ring, ideal or module
canonicalBundle(...,Strategy=>...) (missing documentation)
mingens(...,Strategy=>...) -- see Complement -- a Strategy option value
trim(...,Strategy=>...) -- see Complement -- a Strategy option value
compose(Module,Module,Module,Strategy=>...) -- see compose -- composition as a pairing on Hom-modules
cotangentSheaf(...,Strategy=>...) (missing documentation)
determinant(...,Strategy=>...) -- choose between Bareiss, Cofactor and Dynamic algorithms
dual(ChainComplex,Strategy=>...) (missing documentation)
dual(Matrix,Strategy=>...) (missing documentation)
dual(MonomialIdeal,List,Strategy=>...) -- see dual(MonomialIdeal,Strategy=>...)
dual(MonomialIdeal,RingElement,Strategy=>...) -- see dual(MonomialIdeal,Strategy=>...)
dual(MonomialIdeal,Strategy=>...)
dual(SheafMap,Strategy=>...) (missing documentation)
End(...,Strategy=>...) -- see End -- module of endomorphisms
exteriorPower(...,Strategy=>...) -- choose between Bareiss, Cofactor and Dynamic algorithms
gb(...,Strategy=>...) -- see gb -- compute a Gröbner basis
gcdLLL(...,Strategy=>...) (missing documentation)
GF(...,Strategy=>...) -- see GF -- make a finite field
groebnerBasis(...,Strategy=>...) -- see groebnerBasis -- Gröbner basis, as a matrix
hermite(...,Strategy=>...) (missing documentation)
Hom(...,Strategy=>...) -- see Hom -- module of homomorphisms
homomorphism'(...,Strategy=>...) -- see homomorphism' -- get the element of Hom from a homomorphism
hooks(...,Strategy=>...) -- see hooks -- list hooks attached to a key
idealizer(...,Strategy=>...) -- see idealizer -- compute Hom(I,I) as a quotient ring
integralClosure(...,Strategy=>...) -- control the algorithm used
intersect(Ideal,Ideal,Strategy=>...) -- see intersect(Ideal,Ideal) -- compute an intersection of a sequence of ideals or modules
intersect(Module,Module,Strategy=>...) -- see intersect(Ideal,Ideal) -- compute an intersection of a sequence of ideals or modules
intersectInP(...,Strategy=>...) -- see intersectInP(...,BasisElementLimit=>...) -- Option for intersectInP
isPrimary(...,Strategy=>...) -- see isPrimary -- determine whether a submodule is primary
isPrime(Ideal,Strategy=>...) -- see isPrime(Ideal) -- whether an ideal is prime
LLL(...,Strategy=>...) -- choose among different algorithms
localize(...,Strategy=>...) -- see localize -- localize an ideal at a prime ideal
match(...,Strategy=>...) -- see match -- regular expression matching
decompose(Ideal,Strategy=>...) -- see minimalPrimes -- minimal primes of an ideal
minimalPrimes(...,Strategy=>...) -- see minimalPrimes -- minimal primes of an ideal
minors(...,Strategy=>...) -- choose between Bareiss, Cofactor and Dynamic algorithms
primaryComponent(...,Strategy=>...) -- see primaryComponent -- find a primary component corresponding to an associated prime
pushForward(...,Strategy=>...) (missing documentation)
quotient(...,Strategy=>...)
radical(...,Strategy=>...) -- see radical -- the radical of an ideal
radicalContainment(...,Strategy=>...) -- see radicalContainment -- whether an element is contained in the radical of an ideal
analyticSpread(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
distinguished(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
isLinearType(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
isReduction(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
minimalReduction(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
multiplicity(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
normalCone(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
reesAlgebra(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
specialFiber(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
specialFiberIdeal(...,Strategy=>...) -- see reesIdeal(...,Strategy=>...) -- Choose a strategy for the saturation step
regSeqInIdeal(...,Strategy=>...) -- see regSeqInIdeal -- a regular sequence contained in an ideal
resolution(...,Strategy=>...)
saturate(...,Strategy=>...)
sheafHom(...,Strategy=>...) (missing documentation)
primaryDecomposition(...,Strategy=>...) -- see strategies for computing primary decomposition
syz(...,Strategy=>...) -- see syz(Matrix) -- compute the syzygy matrix
tangentCone(...,Strategy=>...) -- see tangentCone(Ideal)
tangentSheaf(...,Strategy=>...) (missing documentation)