Row Moves Involving Three or Four Vectors

As initially described in [38], Seysen's basis reduction algorithm only considers row moves involving two basis vectors. That is, we only consider moves of the form:

$$\bold{b_j} \leftarrow \bold{b_j} + \lambda \bold{b_i}.$$ (2.13)

(These moves, of course, correspond to the set of transformation matrices $T_{i,j}^\lambda$.) However, there is no real theoretical reason to restrict ourselves to row moves of the form given in Equation 2.16. We consider here possibilities for row moves of the form
$$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \lambda \bold{b_{i_1}} + \kap... ...mbda \bold{b_{i_1}} + \kappa \bold{b_{i_2}} + \mu \bold{b_{i_3}}, \end{align*}$$
and their dual basis counterparts
$$\begin{align*}\bold{b_j^*} & \leftarrow \bold{b_j^*} + \lambda \bold{b_{i_1}^*} ... ...bold{b_{i_1}^*} + \kappa \bold{b_{i_2}^*} + \mu \bold{b_{i_3}^*}. \end{align*}$$
Before we begin, it should be noted that there are practical reasons for not considering row moves involving more than two vectors at any given time. First, if we are using a greedy selection method to choose the vectors upon which to operate, more work is required to choose the correct n-tuple. (If we use a lazy implementation this is less of a concern). Second, 2-moves^2.3 exhibit a symmetry between the prime and dual lattice which is lost when we consider n-moves with n > 2. When we perform a $T_{i,j}^\lambda$ transformation, $\bold{b_j} \leftarrow \bold{b_j} + \lambda\bold{b_i}$ and $\bold{b_i^*} \leftarrow \bold{b_i^*} - \lambda\bold{b_j^*}$. Thus we need not explicitly consider operations on the dual lattice, since every dual lattice transformation has an equivalent transformation in the prime lattice (with i,j swapped and $\lambda$ multiplied by -1). For n-moves with n > 2, however, this duality is lost. The 3-move

$$\bold{b_j} \leftarrow \bold{b_j} + \lambda \bold{b_{i_1}} + \kappa \bold{b_{i_2}},$$

for example, has the following effects in the dual basis:
$$\begin{align*}\bold{b_{i_1}^*} & \leftarrow \bold{b_{i_1}^*} - \lambda \bold{b_j... ...ld{b_{i_2}^*} & \leftarrow \bold{b_{i_2}^*} - \kappa \bold{b_j^*}. \end{align*}$$
Thus, even if we use a lazy approach to choose which vectors to use in a row operation, there are many more candidate operations which must be considered since there is no longer any overlap between moves in the primal and dual lattices. Calculating the best possible values of $\lambda, \kappa, \mu,\ldots{}$ for a given set of basis vectors is also more complicated as the number of vectors involved in the move increases. As an example, let us consider the computation required to choose $\lambda$ and $\kappa$ for the 3-move
$$\begin{align*}\bold{b_j} & \leftarrow \bold{b_j} + \lambda \bold{b_{i_1}} + \kap... ...ld{b_{i_2}^*} & \leftarrow \bold{b_{i_2}^*} - \kappa \bold{b_j^*}. \end{align*}$$
We assume without loss of generality that i₁ < i₂ < j. Then we may represent this transformation by a $T_{i_1,i_2,j}^{\lambda,\kappa}$ transformation matrix, where:

$$T_{i_1,i_2,j}^{\lambda,\kappa} = I_n + \lambda U_{i_1,j} + \kappa U_{i_2,j}.$$

Similar to Section 2.1.4 above, let us define

$$\begin{split} \Delta(i_1,i_2,j,\lambda,\kappa) & = S((T_{i_... ...+ 2 a_{i_1,i_1} a_{j,j}^* \lambda^2 \end{split} \end{split}$$

Now, we compute the partial derivatives of $\Delta(i_1,i_2,j,\lambda,\kappa)$ with respect to $\kappa$ and $\lambda$,
$$\begin{align*}\frac{\partial}{\partial \kappa} \Delta(i_1,i_2,j,\lambda,\kappa) ... ...2 a_{i_1,i_2} a_{j,j}^* \kappa + 4 a_{i_1,i_1} a_{j,j}^* \lambda, \end{align*}$$
set them equal to 0, and solve for $\kappa$ and $\lambda$:
$$\begin{gather*}\frac{\partial \Delta}{\partial \kappa} = 0, \frac{\partial \Delt... ...2})^2 (a_{j,j}^*)^2 - 16 a_{i_1,i_1} a_{i_2,i_2} (a_{j,j}^*)^2}. \end{gather*}$$
If we wish to implement a version of Seysen's algorithm which allows 3-moves in general, we must calculate six sets of ( $\lambda,\kappa$) values; one set for each of
 
Clearly including the six possible 3-moves and the eight possible 4-moves in Seysen's algorithm is computationally expensive. However, there are reasons for wishing to do so. When Seysen's algorithm reaches a local minimum of S(A) for some lattice L it is reducing, it has reached a point where any single row move increases S(A). By allowing the algorithm to look at 3-moves when it has run out of 2-moves to perform, we increase the number of configurations Seysen's algorithm must investigate before it gives up. It is quite possible that one or more configurations which are 3-move attainable but not 2-move attainable will have Seysen measure smaller than S(A). These reduced lattices would then permit the algorithm to move out of the local minimum and continue its reduction steps. We added routines to our implementation of Seysen's basis reductions algorithm to implement three- and four-vector row operations. In all cases one vector was designated the ``target'' vector and integer multiples of the other two or three vectors were added to the target. We did not notice any significant improvement in the performance of the algorithm on random integer lattices of determinant 1 when these additional moves were allowed to occur on any iteration of the algorithm. In some cases, the greedy selection scheme actually performed worse when allowed to use 3-moves and 4-moves; usually this decrease in performance occurred because the algorithm ``jumped ahead'' too quickly by using the 3-move and would have done better by using a sequence of 2-moves. Three- and four-vector operations were helpful, however, when a lattice reduction reached a local minimum. In many of these cases a few 3-moves (or 4-moves, if considered) existed which would carry the lattice out of the local minimum and allow the algorithm to resume processing. Given these experiences and the increased complexity required to operation on more than two vectors at a time, we would suggest using n-moves when n > 2 only to move the lattice being reduced out of a local minimum.