next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 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 264648963742163  -5720194896614938149  196290847034331948723461 
     | 8  -705730569979100 15253853057639806247  -523442258758217541061987
     | -7 617514248731710  -13347121425434776433 458011976413438494260267 
     | 2  -176432642494772 3813463264409886720   -130860564689552160194102
     | 0  -1               21616                 -741761955               
     | 0  0                -1                    34317                    
     | 0  0                0                     -1                       
     | 0  0                0                     0                        
     | 0  0                0                     0                        
     | 0  0                0                     0                        
     ------------------------------------------------------------------------
     -10053331640015906467212478543 733064576943136582501759958326999  
     26808884373375699932906739118  -1954838871848360526997313580179474
     -23457773826703642477234348613 1710484012867308536573627860523869 
     6702221093343811022840899589   -488709717962081822034202577795737 
     37990456734120                 -2770172027631443820               
     -1757596888                    128159705187668                    
     51218                          -3734692423                        
     -1                             72919                              
     0                              -1                                 
     0                              0                                  
     ------------------------------------------------------------------------
     -73320113471254325003809576801404806297  |
     195520302590011163973959639684930937765  |
     -171080264766259075893319671817970920665 |
     48880075647501959867181120921053624538   |
     277068806472403333000800                 |
     -12818357921462101920                    |
     373538813424120                          |
     -7293258360                              |
     100020                                   |
     -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  |, | -24064763942356 -58611163497565
      | -1 1  0  1  0  -1 -2 |  | 21614           4199           
      | -1 -1 -1 -2 -2 0  1  |  | 1               -17415         
      | 0  -1 -1 0  1  -1 1  |  | 0               51216          
      | 2  1  -1 1  -1 1  -2 |  | 0               1              
      | -1 -1 2  1  1  0  0  |  | 0               0              
      | 0  2  0  0  -1 0  2  |  | 0               0              
      | 0  -1 1  -2 1  -1 -1 |
      | 0  0  -1 1  1  2  0  |
      | 0  0  0  0  -1 -1 0  |
     ------------------------------------------------------------------------
     -63552405302952 -32523380442305 7746682944537 -50152546997616
     -21530          7900            -11415        5399           
     21699           29516           10199         5400           
     21701           29517           -24116        5400           
     72918           -72917          27100         -45817         
     1               -1              100019        100018         
     0               0               1             1              
     ------------------------------------------------------------------------
     53669921692178 |)
     -17414         |
     -17416         |
     51216          |
     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 :