<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>LLL -- compute an LLL basis</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_kernel__L__L__L.html">next</a> | <a href="index.html">previous</a> | <a href="_kernel__L__L__L.html">forward</a> | backward | <a href="index.html">up</a> | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<div><a href="index.html" title="lattice reduction (Lenstra-Lenstra-Lovasz bases)">LLLBases</a> > <a href="___L__L__L.html" title="compute an LLL basis">LLL</a></div>
<hr/>
<div><h1>LLL -- compute an LLL basis</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>LLL m</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>m</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span>, or a <a href="../../Macaulay2Doc/html/___Mutable__Matrix.html" title="the class of all mutable matrices">MutableMatrix</a>, over <a href="../../Macaulay2Doc/html/___Z__Z.html" title="the class of all integers">ZZ</a>, whose columns are linearly independent</span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span>A matrix or mutable matrix, respectively, whose columns form an LLL (Lenstra-Lenstra-Lovasz) basis of the image lattice of the matrix</span></li>
</ul>
</div>
</li>
<li><div class="single"><a href="../../Macaulay2Doc/html/_using_spfunctions_spwith_spoptional_spinputs.html">Optional inputs</a>:<ul><li><span><a href="___L__L__L_lp..._cm_sp__Change__Matrix_sp_eq_gt_sp..._rp.html">ChangeMatrix => ...</a>, -- also find change of basis matrix</span></li>
<li><span><tt>Limit => ...</tt> (missing documentation<!-- tag: LLL(..., Limit => ...) -->), </span></li>
<li><span><a href="___L__L__L_lp..._cm_sp__Strategy_sp_eq_gt_sp..._rp.html">Strategy => ...</a>, -- choose among different algorithms</span></li>
<li><span><tt>Threshold => ...</tt> (missing documentation<!-- tag: LLL(..., Threshold => ...) -->), </span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p/>
This function is provided by the package <a href="index.html" title="lattice reduction (Lenstra-Lenstra-Lovasz bases)">LLLBases</a>. If the optional argument <tt>ChangeMatrix=>true</tt> 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.<p/>
In this example, we compute the LLL basis of the nullspace of a matrix. This is an example of Havas et al.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i2 : m = syz m1
o2 = | -3 -15216643 -26282293 -41725081 -62274530 -88660163 -121611503 |
| 8 40577716 70086119 111266892 166065430 236427128 324297381 |
| -7 -35505504 -61325361 -97358544 -145307274 -206873772 -283760259 |
| 2 10144432 17521536 27816734 41516375 59106808 81074382 |
| 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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
It is also possible to get the change of basis matrix from the original basis to the LLL basis. For example,<table class="examples"><tr><td><pre>i4 : (n,c) = LLL(m, Strategy => NTL, ChangeMatrix=>true)
o4 = (| 1 0 1 0 1 1 1 |, | 1383664 3369994 3654103 1870013 -445414
| -1 1 0 1 0 -1 -2 | | -2 -1 1 -1 1
| -1 -1 -1 -2 -2 0 1 | | 1 1 -2 -1 -1
| 0 -1 -1 0 1 -1 1 | | 0 -2 0 0 1
| 2 1 -1 1 -1 1 -2 | | 0 1 -1 2 -1
| -1 -1 2 1 1 0 0 | | 0 0 1 -1 -1
| 0 2 0 0 -1 0 2 | | 0 0 0 0 1
| 0 -1 1 -2 1 -1 -1 |
| 0 0 -1 1 1 2 0 |
| 0 0 0 0 -1 -1 0 |
------------------------------------------------------------------------
2883645 -3085885 |)
-1 2 |
0 0 |
0 -2 |
1 1 |
-2 0 |
1 0 |
o4 : Sequence</pre>
</td></tr>
<tr><td><pre>i5 : m * c == n
o5 = true</pre>
</td></tr>
</table>
</div>
</div>
<div class="single"><h2>Caveat</h2>
<div>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.</div>
</div>
<div class="single"><h2>See also</h2>
<ul><li><span><a href="_is__L__L__L.html" title="is a basis an LLL basis?">isLLL</a> -- is a basis an LLL basis?</span></li>
<li><span><a href="_gcd__L__L__L.html" title="compute the gcd of integers, and small multipliers">gcdLLL</a> -- compute the gcd of integers, and small multipliers</span></li>
<li><span><tt>kernelLLL</tt> (missing documentation<!-- tag: kernelLLL -->)</span></li>
<li><span><tt>hermite</tt> (missing documentation<!-- tag: hermite -->)</span></li>
</ul>
</div>
<div class="waystouse"><h2>Ways to use <tt>LLL</tt> :</h2>
<ul><li>LLL(Matrix)</li>
<li>LLL(MutableMatrix)</li>
</ul>
</div>
</div>
</body>
</html>
