Definition of stage of LLL; Removing integer linear dependency with LLL

Question

In the BKZ algorithm presented in the image below, I don't understand what it is supposed to mean LLL($*$,$\mu$) at stage $j$.

Take for example line 6.

We insert the new vector into the described position, and then we do what?

Thanks in advance.

Answer 1

This seems to refer to the Lenstra-Lenstra-Lovász lattice basis reduction algorithm .

---

For example in line 6, the basis $({\bf b}_1,\ldots,{\bf b}_n)$ is already LLL-reduced, either by line 1 or by an earlier visit to lines 6 or 8. Hence the basis $$({\bf b}_1,\ldots,\textstyle\sum_{i=j}^kv_i{\bf b}_i,{\bf b}_j,\ldots,{\bf b}_h),$$ to which you're applying the LLL-algorithm in line 6, already has its first $j-1$ vectors LLL-reduced. So you can skip the first $j-1$ stages of the LLL-algorithm, and start at stage $j$.