9
$\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.

Improve this question
$\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$
    – Daniel Lichtblau
    Commented Nov 5, 2015 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$
    – Daniel Lichtblau
    Commented Nov 5, 2015 at 18:22

1 Answer 1

Reset to default
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.

Improve this answer
$\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 missing motivation ♦
    Commented Nov 4, 2015 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$
    – Daniel Lichtblau
    Commented Nov 4, 2015 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 missing motivation ♦
    Commented Nov 4, 2015 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$
    – Daniel Lichtblau
    Commented Nov 4, 2015 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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