next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
LLLBases > LLL

LLL -- compute an LLL basis

Synopsis

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

Ways to use LLL :