One Hat Cyber Team
Your IP :
216.73.216.14
Server IP :
194.44.31.54
Server :
Linux zen.imath.kiev.ua 4.18.0-553.77.1.el8_10.x86_64 #1 SMP Fri Oct 3 14:30:23 UTC 2025 x86_64
Server Software :
Apache/2.4.37 (Rocky Linux) OpenSSL/1.1.1k
PHP Version :
5.6.40
Buat File
|
Buat Folder
Eksekusi
Dir :
~
/
usr
/
share
/
doc
/
Macaulay2
/
LLLBases
/
html
/
Edit File:
___L__L__L_lp..._cm__Strategy_eq_gt..._rp.html
<!DOCTYPE html> <html lang="en"> <head> <title>LLL(...,Strategy=>...) -- choose among different algorithms</title> <meta content="text/html; charset=utf-8" http-equiv="Content-Type"> <link type="text/css" rel="stylesheet" href="../../../../Macaulay2/Style/doc.css"> <link rel="stylesheet" href="../../../../Macaulay2/Style/katex/katex.min.css"> <script defer="defer" src="../../../../Macaulay2/Style/katex/katex.min.js"></script> <script defer="defer" src="../../../../Macaulay2/Style/katex/contrib/auto-render.min.js"></script> <script> var macros = { "\\break": "\\\\", "\\ZZ": "\\mathbb{Z}", "\\NN": "\\mathbb{N}", "\\QQ": "\\mathbb{Q}", "\\RR": "\\mathbb{R}", "\\CC": "\\mathbb{C}", "\\PP": "\\mathbb{P}" }, delimiters = [ { left: "$$", right: "$$", display: true}, { left: "\\[", right: "\\]", display: true}, { left: "$", right: "$", display: false}, { left: "\\(", right: "\\)", display: false} ], ignoredTags = [ "kbd", "var", "samp", "script", "noscript", "style", "textarea", "pre", "code", "option" ]; document.addEventListener("DOMContentLoaded", function() { renderMathInElement(document.body, { delimiters: delimiters, macros: macros, ignoredTags: ignoredTags, trust: true }); }); </script> <style>.katex { font-size: 1em; }</style> <script defer="defer" src="../../../../Macaulay2/Style/katex/contrib/copy-tex.min.js"></script> <script defer="defer" src="../../../../Macaulay2/Style/katex/contrib/render-a11y-string.min.js"></script> <script src="../../../../Macaulay2/Style/prism.js"></script> <script>var current_version = '1.25.06';</script> <script src="../../../../Macaulay2/Style/version-select.js"></script> <link type="image/x-icon" rel="icon" href="../../../../Macaulay2/Style/icon.gif"> </head> <body> <div id="buttons"> <div> <a href="https://macaulay2.com/">Macaulay2</a> <span id="version-select-container"></span> » <a title="Macaulay2 documentation" href="../../Macaulay2Doc/html/index.html">Documentation </a> <br><a href="../../Macaulay2Doc/html/_packages_spprovided_spwith_sp__Macaulay2.html">Packages</a> » <span><a title="lattice reduction (Lenstra-Lenstra-Lovasz bases)" href="index.html">LLLBases</a> :: <a title="choose among different algorithms" href="___L__L__L_lp..._cm__Strategy_eq_gt..._rp.html">LLL(...,Strategy=>...)</a></span> </div> <div class="right"> <form method="get" action="https://www.google.com/search"> <input placeholder="Search" type="text" name="q" value=""> <input type="hidden" name="q" value="site:macaulay2.com/doc"> </form> <a href="___N__T__L.html">next</a> | <a href="___L__L__L_lp..._cm__Change__Matrix_eq_gt..._rp.html">previous</a> | <a href="___N__T__L.html">forward</a> | <a href="___L__L__L_lp..._cm__Change__Matrix_eq_gt..._rp.html">backward</a> | up | <a href="master.html">index</a> | <a href="toc.html">toc</a> </div> </div> <hr> <div> <h1>LLL(...,Strategy=>...) -- choose among different algorithms</h1> <ul> <li> <dl class="element"> <dt>Usage: </dt> <dd><code class="language-macaulay2">LLL(...,Strategy=>n)</code></dd> </dl> </li> <li>Inputs: <ul> <li><span>The strategy n can be one of the symbols or lists given below.</span></li> </ul> </li> </ul> <div> <h2>Description</h2> There are several variants of the LLL reduction algorithm implemented. There are three all integer versions: <span class="tt">NTL</span>, <span class="tt">CohenEngine</span>, and <span class="tt">CohenTopLevel</span>. The NTL version (NTL is an excellent package written by Victor shoup) is generally the best, however, the top level version is written in the Macaulay2 language, and so is easily modifiable and can be used to understand the algorithm better. There are also a number of approximate LLL variants implemented in NTL. These use real numbers instead of exact integer arithmetic, and so are often much faster, but only provide approximate answers (i.e. the result might not be an LLL basis, only close to one). Much of the information here about NTL's algorithms comes directly from the NTL documentation (translated to be relevant here). <p></p> Here is the complete list of possible strategies: <ul> <li>LLL(m, Strategy => NTL)</li> <li>LLL(m, Strategy => CohenEngine)</li> <li>LLL(m, Strategy => CohenTopLevel)</li> <li> <hr> </li> <li>LLL(m, Strategy => RealFP)</li> <li>LLL(m, Strategy => RealQP)</li> <li>LLL(m, Strategy => RealXD)</li> <li>LLL(m, Strategy => RealRR)</li> <li> <hr> </li> <li>LLL(m, Strategy => {Givens,RealFP})</li> <li>LLL(m, Strategy => {Givens,RealQP})</li> <li>LLL(m, Strategy => {Givens,RealXD})</li> <li>LLL(m, Strategy => {Givens,RealRR})</li> <li> <hr> </li> <li>LLL(m, Strategy => {BKZ,RealFP})</li> <li>LLL(m, Strategy => {BKZ,RealQP})</li> <li>LLL(m, Strategy => {BKZ,RealQP1})</li> <li>LLL(m, Strategy => {BKZ,RealXD})</li> <li>LLL(m, Strategy => {BKZ,RealRR})</li> <li> <hr> </li> <li>LLL(m, Strategy => {BKZ,Givens,RealFP})</li> <li>LLL(m, Strategy => {BKZ,Givens,RealQP})</li> <li>LLL(m, Strategy => {BKZ,Givens,RealQP1})</li> <li>LLL(m, Strategy => {BKZ,Givens,RealXD})</li> <li>LLL(m, Strategy => {BKZ,Givens,RealRR})</li> </ul> The first three are similar all-integer algorithms, basically the one which appears in H. Cohen's book. The rest of the algorithms are approximate variants, provided by Victor Shoup's NTL package. For these, there are three choices to be made: (1) the reduction condition, (2) the choice of orthogonalization strategy, and (3) the choice of precision. <h2>Reduction condition</h2> <ul> <li>default -- the classical LLL reduction condition</li> <li>BKZ -- Block Korkin-Zolotarev reduction.This is slower, but yields a higher-quality basis, i.e., one with shorter vectors. For a description, see [C. P. Schnorr and M. Euchner, Proc. Fundamentals of Computation Theory, LNCS 529, pp. 68-85, 1991]. This basically generalizes the LLL reduction condition from blocks of size 2 to blocks of larger size.</li> </ul> <h2>Orthogonalization Strategy</h2> <ul> <li>default -- Classical Gram-Schmidt Orthogonalization, This choice uses classical methods for computing the Gram-Schmidt orthogonalization. It is fast but prone to stability problems. This strategy was first proposed by Schnorr and Euchner in the paper mentioned above. The version implemented here is substantially different, improving both stability and performance.</li> <li>Givens -- Givens Orthogonalization, This is a bit slower, but generally much more stable, and is really the preferred orthogonalization strategy. For a nice description of this, see Chapter 5 of [G. Golub and C. van Loan, Matrix Computations, 3rd edition, Johns Hopkins Univ. Press, 1996].</li> </ul> <h2>Precision</h2> <ul> <li>RealFP -- double</li> <li>RealQP -- quad_float (quasi quadruple precision) useful when roundoff errors can cause problems</li> <li>RealQP1 -- only available in the BKZ variant, uses double precision for the search phase of the BKZ reduction, and quad_float for the orthogonalization</li> <li>RealXD -- xdouble (extended exponent doubles) useful when numbers get too big</li> <li>RealRR -- RR (arbitrary precision floating point) useful for large precision and magnitudes</li> </ul> Generally speaking, the choice RealFP will be the fastest, but may be prone to roundoff errors and/or overflow. <h2>Putting it all together</h2> This subsection comes directly from Victor Shoup's LLL documentation <p></p> I think it is safe to say that nobody really understands how the LLL algorithm works. The theoretical analyses are a long way from describing what "really" happens in practice. Choosing the best variant for a certain application ultimately is a matter of trial and error. <p></p> The first thing to try is <span class="tt">Strategy => RealFP</span>. It is the fastest of the routines, and is adequate for many applications. <p></p> If there are precision problems, you will most likely get a warning message, something like "warning--relaxing reduction". If there are overflow problems, you should get an error message saying that the numbers are too big. <p></p> If either of these happens, the next thing to try is <span class="tt">Strategy=>{Givens,RealFP}</span>, which uses the somewhat slower, but more stable, Givens rotations. This approach also has the nice property that the numbers remain smaller, so there is less chance of an overflow. <p></p> If you are still having precision problems try <span class="tt">Strategy=>RealQP</span> or <span class="tt">Strategy=>{Givens,RealQP}</span>, which use quadratic precision. <p></p> If you are still having overflow problems, try <span class="tt">Strategy=>RealXD</span> or <span class="tt">Strategy=>{Givens,RealXD}</span> <p></p> I haven't yet come across a case where one *really* needs the extra precision available in the RealRR variants. <p></p> All of the above discussion applies to the <span class="tt">BKZ</span> variants as well. In addition, if you have a matrix with really big entries, you might try using <span class="tt">Strategy=>{Givens,RealFP}</span> or <span class="tt">Strategy=>RealXD</span> first to reduce the sizes of the numbers, before running one of the <span class="tt">BKZ</span> variants. <p></p> Also, one shouldn't rule out using the "all integer" LLL routines. For some highly structured matrices, this is not necessarily much worse than some of the floating point versions, and can under certain circumstances even be better. <table class="examples"> <tr> <td> <pre><code class="language-macaulay2">i1 : m1 = map(ZZ^50, ZZ^50, (j,i) -> (i+1)^8 * (j+1)^4 + i + j + 2); 50 50 o1 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i2 : m = syz m1; 50 47 o2 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i3 : time LLL m; -- used 0.0110009s (cpu); 0.0105516s (thread); 0s (gc) 50 47 o3 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i4 : time LLL(m, Strategy=>CohenEngine); -- used 0.0369158s (cpu); 0.0377509s (thread); 0s (gc) 50 47 o4 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i5 : time LLL(m, Strategy=>CohenTopLevel); -- used 0.139853s (cpu); 0.140326s (thread); 0s (gc) 50 47 o5 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i6 : time LLL(m, Strategy=>{Givens,RealFP}); -- used 0.0135758s (cpu); 0.014155s (thread); 0s (gc) 50 47 o6 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i7 : time LLL(m, Strategy=>{Givens,RealQP}); -- used 0.0588361s (cpu); 0.0588672s (thread); 0s (gc) 50 47 o7 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i8 : time LLL(m, Strategy=>{Givens,RealXD}); -- used 0.0636931s (cpu); 0.0644357s (thread); 0s (gc) 50 47 o8 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i9 : time LLL(m, Strategy=>{Givens,RealRR}); -- used 0.337675s (cpu); 0.338014s (thread); 0s (gc) 50 47 o9 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> <tr> <td> <pre><code class="language-macaulay2">i10 : time LLL(m, Strategy=>{BKZ,Givens,RealQP}); -- used 0.141719s (cpu); 0.142264s (thread); 0s (gc) 50 47 o10 : Matrix ZZ <-- ZZ</code></pre> </td> </tr> </table> </div> <div> <h2>Caveat</h2> For most of the options, the columns do not need to be linearly independent. The strategies CohenEngine and CohenTopLevel currently require the columns to be linearly independent. </div> <div> <h2>See also</h2> <ul> <li><span><a title="lattice reduction (Lenstra-Lenstra-Lovasz bases)" href="index.html">LLLBases</a> -- lattice reduction (Lenstra-Lenstra-Lovasz bases)</span></li> </ul> </div> <div> <div> <h2>Functions with optional argument named <span class="tt">Strategy</span>:</h2> <ul> <li><span><kbd>addHook(...,Strategy=>...)</kbd> -- see <span><a title="add a hook function to an object for later processing" href="../../Macaulay2Doc/html/_add__Hook.html">addHook</a> -- add a hook function to an object for later processing</span></span></li> <li><span><span class="tt">annihilator(...,Strategy=>...)</span> (missing documentation)<!--tag: [annihilator, Strategy]--> </span></li> <li><span><kbd>basis(...,Strategy=>...)</kbd> -- see <span><a title="basis or generating set of all or part of a ring, ideal or module" href="../../Macaulay2Doc/html/_basis.html">basis</a> -- basis or generating set of all or part of a ring, ideal or module</span></span></li> <li><span><kbd>mingens(...,Strategy=>...)</kbd> -- see <span><a title="a Strategy option value" href="../../Macaulay2Doc/html/___Complement.html">Complement</a> -- a Strategy option value</span></span></li> <li><span><kbd>trim(...,Strategy=>...)</kbd> -- see <span><a title="a Strategy option value" href="../../Macaulay2Doc/html/___Complement.html">Complement</a> -- a Strategy option value</span></span></li> <li><span><kbd>compose(Module,Module,Module,Strategy=>...)</kbd> -- see <span><a title="composition as a pairing on Hom-modules" href="../../Macaulay2Doc/html/_compose.html">compose</a> -- composition as a pairing on Hom-modules</span></span></li> <li><span><a title="choose between Bareiss, Cofactor and Dynamic algorithms" href="../../Macaulay2Doc/html/_determinant_lp..._cm__Strategy_eq_gt..._rp.html">determinant(...,Strategy=>...)</a> -- choose between Bareiss, Cofactor and Dynamic algorithms</span></li> <li><span><kbd>dual(MonomialIdeal,List,Strategy=>...)</kbd> -- see <span><a href="../../Macaulay2Doc/html/_dual_lp__Monomial__Ideal_cm__Strategy_eq_gt..._rp.html">dual(MonomialIdeal,Strategy=>...)</a></span></span></li> <li><span><kbd>dual(MonomialIdeal,RingElement,Strategy=>...)</kbd> -- see <span><a href="../../Macaulay2Doc/html/_dual_lp__Monomial__Ideal_cm__Strategy_eq_gt..._rp.html">dual(MonomialIdeal,Strategy=>...)</a></span></span></li> <li><span><a href="../../Macaulay2Doc/html/_dual_lp__Monomial__Ideal_cm__Strategy_eq_gt..._rp.html">dual(MonomialIdeal,Strategy=>...)</a></span></li> <li><span><kbd>End(...,Strategy=>...)</kbd> -- see <span><a title="module of endomorphisms" href="../../Macaulay2Doc/html/___End.html">End</a> -- module of endomorphisms</span></span></li> <li><span><a title="choose between Bareiss, Cofactor and Dynamic algorithms" href="../../Macaulay2Doc/html/_exterior__Power_lp..._cm__Strategy_eq_gt..._rp.html">exteriorPower(...,Strategy=>...)</a> -- choose between Bareiss, Cofactor and Dynamic algorithms</span></li> <li><span><kbd>gb(...,Strategy=>...)</kbd> -- see <span><a title="compute a Gröbner basis" href="../../Macaulay2Doc/html/_gb.html">gb</a> -- compute a Gröbner basis</span></span></li> <li><span><span class="tt">gcdLLL(...,Strategy=>...)</span> (missing documentation)<!--tag: [gcdLLL, Strategy]--> </span></li> <li><span><kbd>GF(...,Strategy=>...)</kbd> -- see <span><a title="make a finite field" href="../../Macaulay2Doc/html/___G__F.html">GF</a> -- make a finite field</span></span></li> <li><span><kbd>groebnerBasis(...,Strategy=>...)</kbd> -- see <span><a title="Gröbner basis, as a matrix" href="../../Macaulay2Doc/html/_groebner__Basis.html">groebnerBasis</a> -- Gröbner basis, as a matrix</span></span></li> <li><span><span class="tt">hermite(...,Strategy=>...)</span> (missing documentation)<!--tag: [hermite, Strategy]--> </span></li> <li><span><kbd>Hom(...,Strategy=>...)</kbd> -- see <span><a title="module of homomorphisms" href="../../Macaulay2Doc/html/___Hom.html">Hom</a> -- module of homomorphisms</span></span></li> <li><span><kbd>homomorphism'(...,Strategy=>...)</kbd> -- see <span><a title="get the element of Hom from a homomorphism" href="../../Macaulay2Doc/html/_homomorphism_sq.html">homomorphism'</a> -- get the element of Hom from a homomorphism</span></span></li> <li><span><kbd>hooks(...,Strategy=>...)</kbd> -- see <span><a title="list hooks attached to a key" href="../../Macaulay2Doc/html/_hooks.html">hooks</a> -- list hooks attached to a key</span></span></li> <li><span><kbd>intersect(Ideal,Ideal,Strategy=>...)</kbd> -- see <span><a title="compute an intersection of a sequence of ideals or modules" href="../../Macaulay2Doc/html/_intersect_lp__Ideal_cm__Ideal_rp.html">intersect(Ideal,Ideal)</a> -- compute an intersection of a sequence of ideals or modules</span></span></li> <li><span><kbd>intersect(Module,Module,Strategy=>...)</kbd> -- see <span><a title="compute an intersection of a sequence of ideals or modules" href="../../Macaulay2Doc/html/_intersect_lp__Ideal_cm__Ideal_rp.html">intersect(Ideal,Ideal)</a> -- compute an intersection of a sequence of ideals or modules</span></span></li> <li><span><a title="choose among different algorithms" href="___L__L__L_lp..._cm__Strategy_eq_gt..._rp.html">LLL(...,Strategy=>...)</a> -- choose among different algorithms</span></li> <li><span><kbd>match(...,Strategy=>...)</kbd> -- see <span><a title="regular expression matching" href="../../Macaulay2Doc/html/_match.html">match</a> -- regular expression matching</span></span></li> <li><span><a title="choose between Bareiss, Cofactor and Dynamic algorithms" href="../../Macaulay2Doc/html/_minors_lp..._cm__Strategy_eq_gt..._rp.html">minors(...,Strategy=>...)</a> -- choose between Bareiss, Cofactor and Dynamic algorithms</span></li> <li><span><kbd>parallelApply(...,Strategy=>...)</kbd> -- see <span><a title="apply a function to each element in parallel" href="../../Macaulay2Doc/html/_parallel__Apply.html">parallelApply</a> -- apply a function to each element in parallel</span></span></li> <li><span><kbd>pushForward(...,Strategy=>...)</kbd> -- see <span><a title="compute the pushforward of a module along a ring map" href="../../Macaulay2Doc/html/_push__Forward_lp__Ring__Map_cm__Module_rp.html">pushForward(RingMap,Module)</a> -- compute the pushforward of a module along a ring map</span></span></li> <li><span><span class="tt">quotient'(...,Strategy=>...)</span> (missing documentation)<!--tag: [quotient', Strategy]--> </span></li> <li><span><span class="tt">quotient(...,Strategy=>...)</span> (missing documentation)<!--tag: [quotient, Strategy]--> </span></li> <li><span><span class="tt">saturate(...,Strategy=>...)</span> (missing documentation)<!--tag: [saturate, Strategy]--> </span></li> <li><span><kbd>syz(...,Strategy=>...)</kbd> -- see <span><a title="compute the syzygy matrix" href="../../Macaulay2Doc/html/_syz_lp__Matrix_rp.html">syz(Matrix)</a> -- compute the syzygy matrix</span></span></li> </ul> </div> <div> <h2>Further information</h2> <ul> <li><span>Default value: <a title="use the all-integer LLL strategy from NTL library" href="___N__T__L.html">NTL</a></span></li> <li><span>Function: <span><a title="compute an LLL basis" href="___L__L__L.html">LLL</a> -- compute an LLL basis</span></span></li> <li><span>Option key: <span><a title="an optional argument" href="../../Macaulay2Doc/html/___Strategy.html">Strategy</a> -- an optional argument</span></span></li> </ul> </div> <hr> <div class="waystouse"> <p>The source of this document is in <span class="tt">LLLBases.m2:1043:0</span>.</p> </div> </div> </div> </body> </html>
Simpan