Lazy vs. Greedy Selection Methods

In Section 2.1.2 above we outlined the differences between lazy and greedy methods for selecting a row move to perform on each iteration of the Seysen while loop. In this section we describe the results of test lattice reductions on small-dimension lattices using both the lazy and greedy approaches. All experimental tests were performed on random integer lattices of determinant one. Integer lattice bases were generated as follows. Let B be an $n \times n$ integer matrix where the $i^{\text{th}}$ column of B corresponds to basis vector $\bold{b_i}$. The elements of matrix B are:

$$B = \left[ b_{i,j} \right]_{1 \leq i,j \leq n} = \begin{cases... ...tfrac{1}{2}x \right\rfloor & \text{if $i < j$ .} \end{cases}$$

The function $\operatorname{rand}(x)$ generates a random number chosen uniformly from the interval [0,x]; in these experiments x = 4. Notice that $\det(B) = 1$ since B is upper-triangular and all diagonal entries b_i,i = 1. To generate a random, dense lattice which is not upper-triangular yet still has determinant equal to 1, we perform random row moves on matrix B to generate matrix B'. We choose n² pairs of integers (i,j) with $1 \leq i,j \leq n$ and $i \neq j$. For each such pair, $\lambda$ is chosen to be +1 or -1 with equal probability. Then, the current $\bold{b_i}$ is scaled by $\lambda$ and added to $\bold{b_j}$. (That is, we set $B = B \;T_{i,j}^\lambda$.) The result of these n² random row moves is matrix B', which is a basis for our test lattice L. Since $T_{i,j}^\lambda$ transformations preserve the determinant of the lattice, we know that $\det(L) = 1$. We may thus measure the performance of Seysen's algorithm on lattice L by how close reduced lattice L' is to I_n.

 

Table 2.1: Comparison of Lazy and Greedy Selection Methods

n	Avg. # Steps (Lazy)	Avg. # Steps (Greedy)	Ratio (Lazy/Greedy)
20	2079.90	758.50	2.74
25	4096.40	1624.25	2.52
30	7444.80	3279.45	2.27
35	8787.35	3094.25	2.84

Table 2.1 summarizes the results of tests comparing the performance of lazy and greedy selection methods. Twenty test lattices were generated for each dimension $n \in \{20,25,30,35\}$. In all cases where $n \leq 30$, both lazy and greedy algorithms were able to completely reduce all test lattices to I_n. The table shows the average number of row moves required by the lazy and greedy methods to reduce a lattice to I_n. On average, the lazy selection scheme required over twice as many row reductions as the greedy scheme did to reduce a given test lattice. At n = 35 the lazy algorithm was able to reduce to I_n only two of the twenty attempted lattices; the remaining problems all encountered local minima during the reduction, thus halting Seysen's algorithm. The greedy implementation was unable to completely reduce any of the n = 35 test lattices. The two versions of the algorithm performed about equally well if we look at the Seysen measure of the reduced n = 35 test lattices. These experimental results tell us two things concerning the relative merits of lazy and greedy selection schemes. First, when both lazy and greedy methods are likely to produce lattice bases with similar Seysen measures, the greedy selection methods will save at least a factor of two in the number of reduction steps. Second, based on the n = 35 data, using greedy instead of lazy does not appear to significantly reduce the performance of the algorithm as a whole. For our test lattices neither method performed significantly better than the other in terms of the Seysen measure of the S₂-reduced lattice bases. One might argue that it is not reasonable to compare only the number of reduction steps required to reduce lattices using greedy and lazy selection methods, since that measure fails to take into account the cost of selecting the two basis vectors to reduce. A naive implementation of the greedy algorithm might require O(n²) time, as there are $\tfrac{1}{2}n(n-1)$ possible pairs of basis vectors $(\bold{b_i},\bold{b_j}), i \neq j$ which must be considered. However, it turns out that, after an initial O(n²) precomputation phase, only O(n) time is required to greedily select the next row move. Assume that we have computed $\Delta(i,j,\lambda(i,j))$ values for all pairs of integer $(i,j), 1 \leq i,j \leq n$. Now, after a specific row move involving basis vectors i' and j' is performed, the only previously computed values of $\Delta$ which need to be updated are those for which i = i', i = j', j = i' or j = j'. (If you consider $\Delta$ to be an array of values, the $(i')^{\text{th}}$ and $(j')^{\text{th}}$ rows and columns of $\Delta$ are all that need to be recomputed.) Thus, this recomputation can be performed in O(n) time. Storing $\Delta$ values can reduce the cost of a greedy selection method from O(n²) to O(n). However, even O(n) cost would be prohibitive if the actual amount of computation required to select a pair of vectors was comparable to the cost of performing a row move. This is not the case; performing a row move requires O(n) multiprecision math operations, whereas the stored $\Delta$ values need only be stored as single- or double-precision floating point numbers. (The values are generally different enough that 32 or 64 bits will provide more than enough precision.) Since multiprecision operations take significantly more time than double-precision operations, and since each row-move requires O(n) operations, it seems reasonable to discount the added cost of performing the greedy selection as noise when compared to the cost of implementing the main portion of the algorithm. Based on these experimental results, we chose to use a greedy selection strategy in all subsequent implementations of Seysen's basis reduction algorithm. For lattices where we know that Seysen's algorithm will be able to perform a significant amount of basis reduction, such as the sparse lattices associated with subset sum problems (see Chapter 3), the greedy selection method and its expected reduced execution time are preferred.