lllint
-- compute an LLL-reduced
basis of a latticelllint(
A)
applies the LLL algorithm to the
columns of the (not necessary square) matrix A
with
integer entries.
lllint(A, All)
lllint(A)
A |
- | a matrix, given as a list of row vectors, each row being a list of integers |
With option All, a list [T, B]
is returned, such that
B = A*T
and the columns of B
form an
LLL-reduced basis of the lattice spanned by the columns of
A
. Both T
and B
are given as
lists of row vectors.
Without option All, lllint
only
returns the transformation matrix T
as a list of row
vectors.
linalg::basis
,
linalg::factorLU
,
linalg::factorQR
,
linalg::gaussElim
,
linalg::hermiteForm
, linalg::orthog
lllint
applies the LLL algorithm to the columns of the
matrix A
. Mathematically, the input matrix can be an
arbitrary matrix with integer entries, possibly non-square, and
possibly without full column rank.
The matrix is passed to lllint
in form of a list of row
vectors, where each row vector is again a list of integers. The number
of entries in each row must be equal. The matrices returned by
lllint
have this form as well.
The computations are done entirely with integers and are both accurate and quite fast.
matrix
to obtain a nicer screen output of the matrices. See example 1.lllint
is a function of the system kernel.We apply the LLL algorithm to a matrix with two rows and three columns:
>> A := [[1, 2, 3], [4, 5, 6]]: [T, B] := lllint(A, All)
[[[-1, 4], [1, -3], [0, 0]], [[1, -2], [1, 1]]]
We use matrix
to print A,T
, and
B
in a nicer form and check that indeed B =
A*T
:
>> matrix(A), matrix(T), matrix(B)
+- -+ +- -+ | -1, 4 | +- -+ | 1, 2, 3 | | | | 1, -2 | | |, | 1, -3 |, | | | 4, 5, 6 | | | | 1, 1 | +- -+ | 0, 0 | +- -+ +- -+
>> matrix(B) = matrix(A)*matrix(T)
+- -+ +- -+ | 1, -2 | | 1, -2 | | | = | | | 1, 1 | | 1, 1 | +- -+ +- -+
The result is to be interpreted as follows: the two column vectors
+- -+ +- -+ | 1 | | -2 | | | and | | | 1 | | 1 | +- -+ +- -+
form an LLL-reduced basis of the integer lattice generated by the three column vectors
+- -+ +- -+ +- -+ | 1 | | 2 | | 3 | | |, | |, and | |. | 4 | | 5 | | 6 | +- -+ +- -+ +- -+
Without the option All, lllint
returns only the transformation matrix T
:
>> matrix(lllint([[1, 2, 3], [4, 5, 6]]))
+- -+ | -1, 4 | | | | 1, -3 | | | | 0, 0 | +- -+
A. K. Lenstra, H. W. Lenstra Jr., and L. Lovasz, Factoring polynomials with rational coefficients. Math. Ann. 261, 1982, pp. 515-534.
Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra. Cambridge University Press, 1999, Chapter 16.
George L. Nemhauser and Laurence A. Wolsey, Integer and Combinatorial Optimization. New York, Wiley, 1988.
A. Schrijver, Theory of Linear and Integer Programming. New York, Wiley, 1986.