Previous Page Next Page Contents

lllint -- compute an LLL-reduced basis of a lattice

Introduction

lllint(A) applies the LLL algorithm to the columns of the (not necessary square) matrix A with integer entries.

Call(s)

lllint(A, All)
lllint(A)

Parameters

A - a matrix, given as a list of row vectors, each row being a list of integers

Returns

Related Functions

linalg::basis, linalg::factorLU, linalg::factorQR, linalg::gaussElim, linalg::hermiteForm, linalg::orthog

Details

Example 1

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  |
                               +-        -+

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000