Talk:Lenstra–Lenstra–Lovász lattice basis reduction algorithm

Update Pseudocode Formatting=

I've re-written the LLL pseudo-code for this page. Should it be swapped in?

INPUT
    a lattice basis $\mathbf {b} _{0},\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {Z} ^{m}$
    a parameter $\delta$ with ${\tfrac {1}{4}}<\delta <1$, most commonly $\delta ={\tfrac {3}{4}}$

PROCEDURE
    $\mathbf {B^{\ast }} \gets {\rm {GramSchmidt}}(\{\mathbf {b} _{0},\ldots ,\mathbf {b} _{n}\})=\{\mathbf {b} _{0}^{\ast },\ldots ,\mathbf {b} _{n}^{\ast }\};$  and do not normalize
    $\mu _{i,j}\gets {\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{\ast }\rangle }{\langle \mathbf {b} _{j}^{\ast },\mathbf {b} _{j}^{\ast }\rangle }};$   using the most current values of $\mathbf {b} _{i}$ and $\mathbf {b} _{j}^{\ast }$
    $k\gets 1;$
    while $k\leq n$ do
        for $j$ from $k-1$ to $0$ do
            if $|\mu _{k,j}|>{\tfrac {1}{2}}$ then
                $\mathbf {b} _{k}\gets \mathbf {b} _{k}-\lfloor \mu _{k,j}\rfloor \mathbf {b} _{j};$
               Update $\mathbf {B^{\ast }}$ and the related $\mu _{i,j}$'s as needed.
               (The naive method is to recompoute $\mathbf {B^{\ast }}$ whenever $\mathbf {b} _{i}$ changes:
                $\mathbf {B^{\ast }} \gets {\rm {GramSchmidt}}(\{\mathbf {b} _{0},\ldots ,\mathbf {b} _{n}\})=\{\mathbf {b} _{0}^{\ast },\ldots ,\mathbf {b} _{n}^{\ast }\};$)
            end if
        end for
        if $\langle \mathbf {b} _{k}^{\ast },\mathbf {b} _{k}^{\ast }\rangle \geq \left(\delta -\mu _{k,k-1}^{2}\right)\langle \mathbf {b} _{k-1}^{\ast },\mathbf {b} _{k-1}^{\ast }\rangle$ then
            $k\gets k+1;$
        else
            Swap $(\mathbf {b} _{k},\mathbf {b} _{k-1})$ and  $(\mathbf {b} _{k-1},\mathbf {b} _{k});$
            Update $\mathbf {B^{\ast }}$ and the related $\mu _{i,j}$'s as needed.
            $k\gets \max(k-1,1);$
        end if
    end while

Requested move

• Lenstra-Lenstra-Lovász lattice reduction algorithm → Lenstra-Lenstra-Lovász lattice basis reduction algorithm … Rationale: The basis is reduced, not the lattice. … Please share your opinion at Talk:Lenstra-Lenstra-Lovász lattice reduction algorithm. Nuesken 17:24, 18 May 2006 (UTC)

2nd shortest not equal 2nd successive minimum

I attempted to clarify text related to some issues:

• There is not 'the' shortest vector, since there are always at least two of them
• One has to be very careful about stuff like "2nd shortest vectors", as such talk is often incorrect for dimension >= 5. For example, consider the parity lattice defined by $\{(x_{i})\mid x_{i}\sim x_{j}\mod 2\forall i,j\}$. It has $n$ linearly independent vectors of length 1, yet its last successive minimum $\lambda _{n}={\sqrt {n}}>1$ (once the dimension n is >= 5). 131.234.72.252 (talk) 13:52, 16 June 2008 (UTC)
• I apologize, what I wrote yesterday in a hurry is obviously incorrect. The parity lattice has a full set of linearly independent vectors of length 2 (not 1), and there are no shorter nonzero vectors in the lattice (for dimension >= 5). However, those vectors do not form a lattice basis, because the vectors of odd parity cannot be written as integer linear combinations of vectors of even parity. 89.245.87.65 (talk) 06:24, 17 June 2008 (UTC)

Description of the algorithm

It seems to me that a description of the actual algorithm (at least in high-level pseudocode) is needed in order for this article to be in accord with its title. —Preceding unsigned comment added by 84.97.180.156 (talk) 23:09, 22 November 2009 (UTC)

Lattice algorithms in general

I agree that more needs to be said about what the algorithm does. Moreover, I fail to see how a lattice, which is a partial ordering on a set of points, can have a basis in the first place.

Grandfather Gauss saw everything mathematical as embedded in some numerical space. As far as I kmow he only ever gave credit to another mathematician once in his lifetime - Bernhard Reimann.

He definitely did not expect the consequences of finite permutation groups (polynomials >=5) as outlined by Galois. But even to this day everyone embeds finite problems in larger spaces.

This simply is not discrete mathematics, and it addresses lattice traversal in a roundabout way. Reply: j.heyden@bigpond.com — Preceding unsigned comment added by 120.145.16.125 (talk) 08:41, 22 August 2011 (UTC)

The lattices that are partial orderings are not the same things as the lattices described here, which are regularly spaced sets of points in a Euclidean space. The fact that two such unrelated mathematical objects have the same name is unfortunate but true. —David Eppstein (talk) 17:08, 22 August 2011 (UTC)

The article's lead should be more explicit about the kind of lattice that is being talked about here. True, the word 'lattice' points to lattice (group), but I don't think that's sufficient. I've taken a stab. --Macrakis (talk) 23:44, 16 January 2015 (UTC)

Contradiction between algorithm description and example

There's a contradiction between the description of the algorithm and the example given. The description indicates the first loop is completed in its entirety before the reduction steps are executed for any basis vector. However, the example shows that the reduction condition is evaluated for the second basis vector before the third basis vector is ever initialized. It doesn't seem like the two steps are independent, so I would think that the order matters. Which is correct? --Prestidigitator (talk) 18:24, 4 February 2013 (UTC)

I agree, I tried to walk through the example following the algorithm, and I came to the same conclusion. Moreover, I think the pseudocode for the algorithm lacks some rigour. E.g., after the Gram-Schmidt is performed and k is initialized to 2, the algorithm says to check if $|\mu _{i,j}|>{\frac {1}{2}}$ then execute subroutine RED(k, k-1). This seeams weird as i=n and j=n-1 after the end of the Gram-Schmidt orthogonalization, and it is my impression that, really, we should be looking at $|\mu _{2,1}|$ at this point. At least that is also what is done in the example, although that is done in the middle of the GS process.

In the example, I also see something, which does not seem to be consistent. In step 6.1.i the vector b3 is reduced. OK, makes sense. Then the step 6.1.i is repeated with another $\mu _{i,j}$ (makes sense), where the reduction factor $r=1$ is found (OK), and then used to reduce $b_{3}=b_{3}-b_{2}$ (OK), but when the vectors are inserted, it is the original vector $b_{3}$, and not the one, which was just reduced by five times $b_{1}$ above. I find that confusing. Is that not an error? --Slaunger (talk) 20:43, 29 January 2014 (UTC)