8
$\begingroup$

The Lenstra–Lenstra–Lovász algorithm has a parameter $\delta$ with $1/4 < \delta < 1$, where roughly speaking the closer $\delta$ is to 1 the longer it takes, but the better basis reduction you get. Options[LatticeReduce] returns {}, so what value of $\delta$ is LatticeReduce using? Is there any way to tell it which $\delta$ you want LLL executed with?


If Mathematica is using Nguyen-Stehle, then there is a second parameter $\eta$ with $1/2 < \eta < \sqrt{\delta}$. What is the default for that in LatticeReduce, and how can I change $\eta$?

Thank you for your prompt and informative reply.

$\endgroup$
2
  • 1
    $\begingroup$ That other parameter is fixed to .51 and only changed for too-small $\delta$ (or maybe we change $\delta$, I forget). In any case it is not configurable. $\endgroup$ Nov 5 '15 at 17:50
  • $\begingroup$ I should clarify: .51 is actually what they refer to as $\overline{\eta}$ rather than $\eta$. Computations are done with the former whereas results are guaranteed in terms of the latter. $\endgroup$ Nov 5 '15 at 18:22
8
$\begingroup$

In this comment, it is noted that LatticeReduce[] is now using the Nguyen-Stehle variant of LLL, so any results you might see from LatticeReduce[] can be different from a "classical" implementation of LLL.

Having said this, LatticeReduce[] does take options, but through a not too transparent interface:

SetSystemOptions["LatticeReduceOptions" ->
                 {"LatticeReduceRatioParameter" -> .75}];

The list of default option settings is accessible through SystemOptions["LatticeReduceOptions"]; the default setting of Automatic for "LatticeReduceRatioParameter" indicates that the choice is made internally, depending on the input matrix.

$\endgroup$
4
  • $\begingroup$ (I should hasten to add that I picked all of this from Daniel Lichtblau. Maybe he'll have more to say when he sees this.) $\endgroup$
    – J. M.'s torpor
    Nov 4 '15 at 9:56
  • 4
    $\begingroup$ All correct. The Automatic setting is due to the fact that .75 is used for integer/rational input (the usual case) whereas .8 is used for Gaussian integer/rational input. The 3/4 default predates me and the 4/5 for Gaussians was from when I extended LatticeReduce to handle those (more than 20 years ago, from what I can see in the commit logs). $\endgroup$ Nov 4 '15 at 16:22
  • $\begingroup$ @Daniel, I didn't know a different setting was needed for Gaussian integers! Do you know a reference for this? (The 0.75 setting was already in the original LLL paper, IIRC.) $\endgroup$
    – J. M.'s torpor
    Nov 4 '15 at 17:14
  • 4
    $\begingroup$ For Gaussians it need not be .8 but it is required to be larger than 1/2 if I remember correctly. You are correct that .75 is used in LLL (the paper). Here is a reference that I think is relevant: Huguette Napias. A generalization of the LLL-algorithm over Euclidean rings or orders. Journal de Theorie des Nombres de Bordeaux 8(2):387-396. 1996. There must be older knowledge though, since I implemented the Gaussian case a couple of years before that. $\endgroup$ Nov 4 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.