This is LLLBases.info, produced by Macaulay2, version 1.21

LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)
************************************************************

Description
===========

LLLBases is a package implementing several variants of LLL bases. Some of these
are implemented in the Macaulay2 engine, some by Victor Shoup's NTL package,
and some are implemented at top level.

A matrix over ZZ determines a lattice: this is the ZZ-module generated by the
columns.  It also determines a generating set. See the book: [H. Cohen, ...]
for the definition and the basic algorithms for computing LLL bases.

LLL bases have nice theoretical properties, but the main benefit of LLL bases
is that the entries of the resulting matrix often have dramatically small size,
even smaller than theory would imply.

This package implements the following functions.

Author
======

  * Michael E. Stillman (see http://www.math.cornell.edu/~mike/ )
    <mike@math.cornell.edu>

Version
=======

This documentation describes version 1.1 of LLLBases.

Source code
===========

The source code from which this documentation is derived is in the file
LLLBases.m2 (see common/share/Macaulay2/LLLBases.m2 ).

Exports
=======

  * Functions and commands
      * gcdLLL -- compute the gcd of integers, and small
        multipliers
      * gramm (missing documentation)
      * hermite (missing documentation)
      * isLLL -- is a basis an LLL basis?
      * kernelLLL (missing documentation)
      * LLL -- compute an LLL basis
  * Methods
      * "gcdLLL(List)" -- see gcdLLL, -- compute the gcd of
        integers, and small multipliers
      * "isLLL(Matrix)" -- see isLLL, -- is a basis an LLL basis?
      * "LLL(Matrix)" -- see LLL, -- compute an LLL basis
      * "LLL(MutableMatrix)" -- see LLL, -- compute an LLL basis
  * Symbols
      * BKZ -- compute BKZ reduced basis instead of an LLL reduced
        basis
      * CohenEngine -- use the original Macaulay2 LLL
        algorithm
      * CohenTopLevel -- use the Macaulay2 language LLL
        algorithm
      * fpLLL (missing documentation)
      * Givens -- use Givens rotations instead of Gram-Schmidt
        during LLL
      * Hermite (missing documentation)
      * NTL -- use the all-integer LLL strategy from NTL library
      * RealFP -- use double precision real numbers
      * RealQP -- use quadruple precision real numbers
      * RealQP1 -- use a combination of double precision and
        quad precision real numbers
      * RealRR -- use arbitrary precision real numbers
      * RealXD -- use extended exponent real numbers
      * Threshold -- the LLL threshold, in interval (1/4,1]

For the programmer
==================

The object LLLBases, is a package (Macaulay2Doc).

main LLL algorithm

applications and variants

support routines that are occasionally useful

LLL -- compute an LLL basis
***************************

Synopsis
========

  * Usage:
        LLL m
  * Inputs:
      * m, a matrix (Macaulay2Doc), or a MutableMatrix (Macaulay2Doc),
        over ZZ (Macaulay2Doc), whose
        columns are linearly independent
  * Optional inputs (Macaulay2Doc),:
      * ChangeMatrix, =>
        ..., default value false, also find change of basis matrix
      * Limit (missing documentation) => ..., default value infinity, null
      * Strategy, => ...,
        default value NTL, choose among different algorithms
      * Threshold (missing documentation) => ..., default value null, null
  * Outputs:
      * A matrix or mutable matrix, respectively, whose columns form an LLL
        (Lenstra-Lenstra-Lovasz) basis of the image lattice of the matrix

Description
===========

This function is provided by the package LLLBases.  If the optional
argument ChangeMatrix=>true is given, then the output is a pair of matrices:
the first is the LLL matrix as above, and the second is the change of basis
matrix from the original basis to the new basis.

In this example, we compute the LLL basis of the nullspace of a matrix.  This
is an example of Havas et al.
+---------------------------------------------------------------------+
|i1 : m1 = map(ZZ^10, ZZ^10, (j,i) -> (i+1)^3 * (j+1)^2 + i + j + 2)  |
|                                                                     |
|o1 = | 3   11  31   69   131   223   351   521   739   1011   |      |
|     | 7   36  113  262  507   872   1381  2058  2927  4012   |      |
|     | 13  77  249  583  1133  1953  3097  4619  6573  9013   |      |
|     | 21  134 439  1032 2009  3466  5499  8204  11677 16014  |      |
|     | 31  207 683  1609 3135  5411  8587  12813 18239 25015  |      |
|     | 43  296 981  2314 4511  7788  12361 18446 26259 36016  |      |
|     | 57  401 1333 3147 6137  10597 16821 25103 35737 49017  |      |
|     | 73  522 1739 4108 8013  13838 21967 32784 46673 64018  |      |
|     | 91  659 2199 5197 10139 17511 27799 41489 59067 81019  |      |
|     | 111 812 2713 6414 12515 21616 34317 51218 72919 100020 |      |
|                                                                     |
|              10        10                                           |
|o1 : Matrix ZZ   <--- ZZ                                             |
+---------------------------------------------------------------------+
|i2 : m = syz m1                                                      |
|                                                                     |
|o2 = | -3 -1632481 -2819632 -4476373  -6680969  -9511685  -13046786 ||
|     | 8  4353284  7519023  11937004  17815934  25364520  34791469  ||
|     | -7 -3809126 -6579152 -10444892 -15588965 -22193990 -30442586 ||
|     | 2  1088324  1879762  2984262   4454001   6341156   8697904   ||
|     | 0  -1       0        0         0         0         0         ||
|     | 0  0        -1       0         0         0         0         ||
|     | 0  0        0        -1        0         0         0         ||
|     | 0  0        0        0         -1        0         0         ||
|     | 0  0        0        0         0         -1        0         ||
|     | 0  0        0        0         0         0         -1        ||
|                                                                     |
|              10        7                                            |
|o2 : Matrix ZZ   <--- ZZ                                             |
+---------------------------------------------------------------------+
|i3 : LLL m                                                           |
|                                                                     |
|o3 = | 1  0  1  0  1  1  1  |                                        |
|     | -1 1  0  1  0  -1 -2 |                                        |
|     | -1 -1 -1 -2 -2 0  1  |                                        |
|     | 0  -1 -1 0  1  -1 1  |                                        |
|     | 2  1  -1 1  -1 1  -2 |                                        |
|     | -1 -1 2  1  1  0  0  |                                        |
|     | 0  2  0  0  -1 0  2  |                                        |
|     | 0  -1 1  -2 1  -1 -1 |                                        |
|     | 0  0  -1 1  1  2  0  |                                        |
|     | 0  0  0  0  -1 -1 0  |                                        |
|                                                                     |
|              10        7                                            |
|o3 : Matrix ZZ   <--- ZZ                                             |
+---------------------------------------------------------------------+
It is also possible to get the change of basis matrix from the original basis
to the LLL basis.  For example,
+-----------------------------------------------------------------------------+
|i4 : (n,c) = LLL(m, Strategy => NTL, ChangeMatrix=>true)                     |
|                                                                             |
|o4 = (| 1  0  1  0  1  1  1  |, | 148443 361542 392022 200620 -47785 309365  |
|      | -1 1  0  1  0  -1 -2 |  | -2     -1     1      -1     1      -1      |
|      | -1 -1 -1 -2 -2 0  1  |  | 1      1      -2     -1     -1     0       |
|      | 0  -1 -1 0  1  -1 1  |  | 0      -2     0      0      1      0       |
|      | 2  1  -1 1  -1 1  -2 |  | 0      1      -1     2      -1     1       |
|      | -1 -1 2  1  1  0  0  |  | 0      0      1      -1     -1     -2      |
|      | 0  2  0  0  -1 0  2  |  | 0      0      0      0      1      1       |
|      | 0  -1 1  -2 1  -1 -1 |                                               |
|      | 0  0  -1 1  1  2  0  |                                               |
|      | 0  0  0  0  -1 -1 0  |                                               |
|     ------------------------------------------------------------------------|
|     -331062 |)                                                              |
|     2       |                                                               |
|     0       |                                                               |
|     -2      |                                                               |
|     1       |                                                               |
|     0       |                                                               |
|     0       |                                                               |
|                                                                             |
|o4 : Sequence                                                                |
+-----------------------------------------------------------------------------+
|i5 : m * c == n                                                              |
|                                                                             |
|o5 = true                                                                    |
+-----------------------------------------------------------------------------+

Caveat
======

If the strategy given is not an NTL strategy, then the columns of the matrix m
must be linearly independent.In any case, the matrix must be defined over the
ring ZZ.

See also
========

  * isLLL -- is a basis an LLL basis?
  * gcdLLL -- compute the gcd of integers, and small multipliers
  * kernelLLL (missing documentation)
  * hermite (missing documentation)

Ways to use LLL :
=================

  * "LLL(Matrix)"
  * "LLL(MutableMatrix)"

For the programmer
==================

The object LLL, is a method function with options (Macaulay2Doc).

kernelLLL
*********

Ways to use kernelLLL :
=======================

  * kernelLLL(Matrix) (missing documentation)

For the programmer
==================

The object kernelLLL (missing documentation) is a method function with options (Macaulay2Doc).

gcdLLL -- compute the gcd of integers, and small multipliers
************************************************************

Synopsis
========

  * Usage:
        (g,z) = gcdLLL m
  * Inputs:
      * m, a list (Macaulay2Doc), of integers
  * Optional inputs (Macaulay2Doc),:
      * Strategy (missing documentation) => ..., default value null, null
      * Threshold (missing documentation) => ..., default value 3/4, null
  * Outputs:
      * g, an integer (Macaulay2Doc), the gcd of the integers in the
        list s
      * z, a matrix (Macaulay2Doc),  of integers

Description
===========

This function is provided by the package LLLBases.

The first n-1 columns of the matrix z form a basis of the kernel of the n
integers of the list s, and the dot product of the last column of z and s is
the gcd g.

The method used is described in the paper:

Havas, Majewski, Matthews, Extended GCD and Hermite Normal Form Algorithms via
Lattice Basis Reduction, Experimental Mathematics 7:2 p. 125 (1998).

For an example,
+------------------------------------------------------------+
|i1 : s = apply(5,i->372*(random 1000000))                   |
|                                                            |
|o1 = {306370272, 229247604, 135272220, 220821804, 229345440}|
|                                                            |
|o1 : List                                                   |
+------------------------------------------------------------+
|i2 : (g,z) = gcdLLL s                                       |
|                                                            |
|o2 = (372, | 1   -2  11  48  -20 |)                         |
|           | -5  -24 -2  -19 7   |                          |
|           | -12 15  -15 -7  7   |                          |
|           | 7   5   -31 0   11  |                          |
|           | 4   13  26  -41 5   |                          |
|                                                            |
|o2 : Sequence                                               |
+------------------------------------------------------------+
|i3 : matrix{s} * z                                          |
|                                                            |
|o3 = | 0 0 0 0 372 |                                        |
|                                                            |
|              1        5                                    |
|o3 : Matrix ZZ  <--- ZZ                                     |
+------------------------------------------------------------+

See also
========

  * LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)
  * LLL -- compute an LLL basis
  * kernelLLL (missing documentation)
  * hermite (missing documentation)

Ways to use gcdLLL :
====================

  * "gcdLLL(List)"

For the programmer
==================

The object gcdLLL, is a method function with options (Macaulay2Doc).

hermite
*******

Ways to use hermite :
=====================

  * hermite(Matrix) (missing documentation)

For the programmer
==================

The object hermite (missing documentation) is a method function with options (Macaulay2Doc).

gramm
*****

Ways to use gramm :
===================

  * gramm(Matrix) (missing documentation)

For the programmer
==================

The object gramm (missing documentation) is a method function (Macaulay2Doc).

isLLL -- is a basis an LLL basis?
*********************************

Synopsis
========

  * Usage:
        isLLL m
  * Inputs:
      * m, a matrix (Macaulay2Doc), over ZZ (Macaulay2Doc),
        whose columns are linearly independent
  * Optional inputs (Macaulay2Doc),:
      * Threshold (missing documentation) => ..., default value 3/4, null
  * Outputs:
      * a Boolean value (Macaulay2Doc), Whether the columns of
        the matrix form an LLL basis with respect to the Threshold (which has
        default 3/4)

Description
===========

This function is provided by the package LLLBases.

If the matrix is not in LLL reduced form, then the offending conditions are
displayed.  For example,
+------------------------------------------------+
|i1 : m = matrix {{1, 0}, {1, 1}, {1, 2}, {1, 3}}|
|                                                |
|o1 = | 1 0 |                                    |
|     | 1 1 |                                    |
|     | 1 2 |                                    |
|     | 1 3 |                                    |
|                                                |
|              4        2                        |
|o1 : Matrix ZZ  <--- ZZ                         |
+------------------------------------------------+
|i2 : isLLL m                                    |
|LLL size failure 1,0: 1.5                       |
|LLL Lovasz failure 1: -.833333                  |
|                                                |
|o2 = false                                      |
+------------------------------------------------+
|i3 : n = LLL m                                  |
|                                                |
|o3 = | 1 -1 |                                   |
|     | 1 0  |                                   |
|     | 1 1  |                                   |
|     | 1 2  |                                   |
|                                                |
|              4        2                        |
|o3 : Matrix ZZ  <--- ZZ                         |
+------------------------------------------------+
|i4 : isLLL n                                    |
|                                                |
|o4 = true                                       |
+------------------------------------------------+
If the optional argument Threshold is given, the conditions are checked using
that value.
+------------------------------------------------+
|i5 : m = matrix {{1, 0}, {1, 1}, {1, 2}, {1, 3}}|
|                                                |
|o5 = | 1 0 |                                    |
|     | 1 1 |                                    |
|     | 1 2 |                                    |
|     | 1 3 |                                    |
|                                                |
|              4        2                        |
|o5 : Matrix ZZ  <--- ZZ                         |
+------------------------------------------------+
|i6 : isLLL(m, Threshold=>1)                     |
|LLL size failure 1,0: 1.5                       |
|LLL Lovasz failure 1: -1                        |
|                                                |
|o6 = false                                      |
+------------------------------------------------+

Caveat
======

A Gram-Schmidt reduction is done over QQ, so this can be computationally
intensive for larger matrix sizes. It is usually easier and faster to see if
LLL returns the same matrix.  This routine was used to debug and test the LLL
routines here, and is provided as an alternate check of correctness.The matrix
must be defined over the ring ZZ.  It should be possible to allow real and
rational matrices too, but this is not yet implemented.

See also
========

  * LLL -- compute an LLL basis
  * gcdLLL -- compute the gcd of integers, and small multipliers
  * kernelLLL (missing documentation)
  * hermite (missing documentation)

Ways to use isLLL :
===================

  * "isLLL(Matrix)"

For the programmer
==================

The object isLLL, is a method function with options (Macaulay2Doc).

BKZ -- compute BKZ reduced basis instead of an LLL reduced basis
****************************************************************

Description
===========

BKZ -- a strategy value for LLL(...,Strategy=>...),
used to specify that a BKZ basis (see
LLL(...,Strategy=>...), for
references) should be constructed rather than an (approximate) LLL basis.
Apparently produces higher quality bases, but can be slower.

For the programmer
==================

The object BKZ, is a symbol (Macaulay2Doc).

CohenEngine -- use the original Macaulay2 LLL algorithm
*******************************************************

Description
===========

CohenEngine -- a strategy value for LLL(...,Strategy=>...),
used to specify that the all-integer
LLL algorithm from H.Cohen's book (with improvements by Euchner and Schnorr)
should be used.  This is basically the same algorithm as Strategy=>NTL, but is
often outperformed by that algorithm.

For the programmer
==================

The object CohenEngine, is a symbol (Macaulay2Doc).

CohenTopLevel -- use the Macaulay2 language LLL algorithm
*********************************************************

Description
===========

CohenTopLevel -- a strategy value for LLL(...,Strategy=>...),
used to specify that the all-integer
LLL algorithm from H.Cohen's book (with improvements by Euchner and Schnorr)
should be used, as coded in the front-end of Macaulay2. This is basically the
same algorithm as Strategy=>CohenEngine, but is written at top level, so that
it is relatively easy to adapt the code to other situations.

For the programmer
==================

The object CohenTopLevel, is a symbol (Macaulay2Doc).

fpLLL
*****

For the programmer
==================

The object fpLLL (missing documentation) is a symbol (Macaulay2Doc).

Givens -- use Givens rotations instead of Gram-Schmidt during LLL
*****************************************************************

Description
===========

Givens -- a strategy value for LLL(...,Strategy=>...),
used to specify that Givens rotations
should be used instead of the usual (but inferior) Gram-Schmidt
orthogonalization.  Only valid for approximate LLL computations.

For the programmer
==================

The object Givens, is a symbol (Macaulay2Doc).

Hermite
*******

For the programmer
==================

The object Hermite (missing documentation) is a symbol (Macaulay2Doc).

LLL(...,ChangeMatrix=>...) -- also find change of basis matrix
**************************************************************

Synopsis
========

  * Usage:
        (B,U) = LLL(A,ChangeMatrix=>true)
  * Inputs:
      * A, a matrix (Macaulay2Doc), over the integers, of size d
        by n
  * Outputs:
      * B, a matrix (Macaulay2Doc), the LLL matrix (also having d
        rows)
      * U, a matrix (Macaulay2Doc), the n by n invertible
        transform matrix
  * Consequences:
      * The routine returns a pair of matrices, rather than just one

Description
===========

Constructs the change of basis matrix U from the basis A to the basis B. This
is an invertible matrix U such that$AU = B$.
+-----------------------------------------------------------------------------+
|i1 : A = matrix randomMutableMatrix(10,10,.5,100000)                         |
|                                                                             |
|o1 = | -8031  0      0      0      88379  -94929 0      0      0      0      |
|     | 55574  20182  70070  0      0      -13982 -94602 0      -40555 -9613  |
|     | -74322 -33228 0      -40828 -68991 0      0      -67902 65046  74210  |
|     | 89120  -17794 59911  0      0      0      -28590 -89433 0      4549   |
|     | 55425  -90574 0      0      0      -54423 -61026 30061  25364  0      |
|     | 0      0      0      0      0      -27571 -55134 0      31782  74516  |
|     | 0      0      0      0      0      83366  95253  0      -38577 0      |
|     | -59640 -23833 0      0      0      -82072 70952  0      0      0      |
|     | 0      0      0      0      0      -34637 -36361 0      0      -14763 |
|     | 0      80627  -71921 0      0      0      0      -68183 80908  0      |
|     ------------------------------------------------------------------------|
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|     |                                                                       |
|                                                                             |
|              10        10                                                   |
|o1 : Matrix ZZ   <--- ZZ                                                     |
+-----------------------------------------------------------------------------+
|i2 : (B,U) = LLL(A, ChangeMatrix=>true)                                      |
|                                                                             |
|o2 = (| 0      -9512  88379 -9512  0      1481   1481   8031   1481   1481   |
|      | 0      11582  0     50710  -9613  28602  -24651 -9242  -21095 -913   |
|      | -40828 -8307  12665 -17471 -7446  17529  587    -58    12785  20385  |
|      | 0      -12939 0     42423  4549   -3369  -13214 20857  43947  26153  |
|      | 0      18370  0     43734  0      -3695  -13673 -40039 31454  -59120 |
|      | 0      15171  0     -27563 74516  -6741  -4219  34304  -38523 -38523 |
|      | 0      50464  0     11887  0      -32365 26690  20478  6212   6212   |
|      | 0      9911   0     9911   0      -22432 -69551 12521  1401   -22432 |
|      | 0      -16487 0     -1724  -14763 -19874 1724   21598  -19874 -19874 |
|      | 0      3457   0     12444  0      -41222 -21431 -43143 -62653 17974  |
|     ------------------------------------------------------------------------|
|     |, | 0 2  0  2  0 -1 -1 -1 -1 -1 |)                                     |
|     |  | 0 1  0  1  0 0  -1 -1 -1 0  |                                      |
|     |  | 0 -1 0  0  0 3  -1 -2 2  2  |                                      |
|     |  | 1 -4 -2 -4 2 1  1  3  2  1  |                                      |
|     |  | 0 -1 1  -1 0 1  1  0  1  1  |                                      |
|     |  | 0 -1 0  -1 0 1  1  0  1  1  |                                      |
|     |  | 0 1  0  1  0 0  -1 -1 0  0  |                                      |
|     |  | 0 1  0  1  0 1  -1 -2 0  0  |                                      |
|     |  | 0 -1 0  0  0 3  -1 -3 2  2  |                                      |
|     |  | 0 1  0  0  1 -1 0  1  -1 -1 |                                      |
|                                                                             |
|o2 : Sequence                                                                |
+-----------------------------------------------------------------------------+
|i3 : B == A*U                                                                |
|                                                                             |
|o3 = true                                                                    |
+-----------------------------------------------------------------------------+

Further information
===================

  * Default value: false (Macaulay2Doc),
  * Function: LLL, -- compute an LLL basis
  * Option key: ChangeMatrix (Macaulay2Doc), -- an optional
    argument

See also
========

  * LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)

Functions with optional argument named ChangeMatrix :
=====================================================

  * forceGB(...,ChangeMatrix=>...) (Macaulay2Doc)
    -- inform
    Macaulay2 about the change of basis matrix from GB to generators
  * "gb(...,ChangeMatrix=>...)" -- see gb (Macaulay2Doc), -- compute a
    Gröbner basis
  * hermite(...,ChangeMatrix=>...) (missing documentation)
  * LLL(...,ChangeMatrix=>...)
    -- also find change of basis
    matrix
  * "markedGB(...,ChangeMatrix=>...)" -- see markedGB(Matrix,Matrix) (Macaulay2Doc),
    -- make a marked Gröbner basis
  * "smithNormalForm(...,ChangeMatrix=>...)" -- see
    smithNormalForm(Matrix) (Macaulay2Doc), --
    smith normal form for a matrix over ZZ or a PID

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.0215124 seconds                                      |
|                                                                    |
|              50        47                                          |
|o3 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i4 : time LLL(m, Strategy=>CohenEngine);                            |
|     -- used 0.0757876 seconds                                      |
|                                                                    |
|              50        47                                          |
|o4 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i5 : time LLL(m, Strategy=>CohenTopLevel);                          |
|     -- used 0.447695 seconds                                       |
|                                                                    |
|              50        47                                          |
|o5 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i6 : time LLL(m, Strategy=>{Givens,RealFP});                        |
|     -- used 0.0335092 seconds                                      |
|                                                                    |
|              50        47                                          |
|o6 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i7 : time LLL(m, Strategy=>{Givens,RealQP});                        |
|     -- used 0.124773 seconds                                       |
|                                                                    |
|              50        47                                          |
|o7 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i8 : time LLL(m, Strategy=>{Givens,RealXD});                        |
|     -- used 0.112373 seconds                                       |
|                                                                    |
|              50        47                                          |
|o8 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i9 : time LLL(m, Strategy=>{Givens,RealRR});                        |
|     -- used 0.653845 seconds                                       |
|                                                                    |
|              50        47                                          |
|o9 : Matrix ZZ   <--- ZZ                                            |
+--------------------------------------------------------------------+
|i10 : time LLL(m, Strategy=>{BKZ,Givens,RealQP});                   |
|     -- used 0.279263 seconds                                       |
|                                                                    |
|               50        47                                         |
|o10 : Matrix ZZ   <--- ZZ                                           |
+--------------------------------------------------------------------+

Further information
===================

  * Default value: NTL,
  * Function: LLL, -- compute an LLL basis
  * Option key: Strategy (Macaulay2Doc), -- 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.

See also
========

  * LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)

Functions with optional argument named Strategy :
=================================================

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

NTL -- use the all-integer LLL strategy from NTL library
********************************************************

Description
===========

NTL -- the default strategy value for LLL(...,Strategy=>...),
used to specify that the all-integer
LLL algorithm from Victor Shoup's NTL library should be used. Overall, the
performance of this algorithm is very good in many situations.

For the programmer
==================

The object NTL, is a symbol (Macaulay2Doc).

RealFP -- use double precision real numbers
*******************************************

Description
===========

RealFP -- a strategy value for LLL(...,Strategy=>...),
used to specify that an approximate
LLL basis will be constructed, using double precision.

For the programmer
==================

The object RealFP, is a symbol (Macaulay2Doc).

RealQP -- use quadruple precision real numbers
**********************************************

Description
===========

RealQP -- a strategy value for LLL(...,Strategy=>...),
used to specify that an approximate
LLL basis will be constructed, using double precision.

For the programmer
==================

The object RealQP, is a symbol (Macaulay2Doc).

RealQP1 -- use a combination of double precision and quad precision real numbers
********************************************************************************

Description
===========

RealQP1 -- a strategy value for LLL(...,Strategy=>...),
used to specify that an approximate
LLL basis will be constructed, using double precision.  Only valid for the BKZ
reduction condition.

For the programmer
==================

The object RealQP1, is a symbol (Macaulay2Doc).

RealRR -- use arbitrary precision real numbers
**********************************************

Description
===========

RealRR -- a strategy value for LLL(...,Strategy=>...),
used to specify that an approximate
LLL basis will be constructed, using arbitrary precision real numbers.

For the programmer
==================

The object RealRR, is a symbol (Macaulay2Doc).

RealXD -- use extended exponent real numbers
********************************************

Description
===========

RealXD -- a strategy value for LLL(...,Strategy=>...),
used to specify that an approximate
LLL basis will be constructed, using extended exponent real numbers.  Useful if
the integer entries are very large.

For the programmer
==================

The object RealXD, is a symbol (Macaulay2Doc).

Threshold -- the LLL threshold, in interval (1/4,1]
***************************************************

Description
===========

Threshold -- an optional value to LLL, used to specify the threshold
value, see LLL(...,Threshold=>...) (missing documentation).

Functions with optional argument named Threshold :
==================================================

  * gcdLLL(...,Threshold=>...) (missing documentation)
  * hermite(...,Threshold=>...) (missing documentation)
  * isLLL(...,Threshold=>...) (missing documentation)
  * LLL(...,Threshold=>...) (missing documentation)

For the programmer
==================

The object Threshold, is a symbol (Macaulay2Doc).