Alternate Selection Criteria

Seysen's original implementation of his basis reduction algorithm used a ``lazy'' approach for choosing pairs of basis vectors to reduce. Pairs of integers $(i,j), 1 \leq i,j \leq n$ were searched in lexicographic order until a suitable row move involving $\bold{b_i}$ and $\bold{b_j}$ was found. We have presented above empirical evidence which favors a ``greedy'' approach, even when the extra computation time required to implement the ``greedy'' method is considered. Selection methods other than the ``greedy'' and ``lazy'' approaches were not considered in our experiments, but are certainly possible. For example, in addition to taking into account the reduction in S(A) which will result from a row move, we might also wish to consider the other row moves which will be blocked by performing this move. That is, if $\lambda \bold{b_j}$ is added to $\bold{b_i}$, the potential S(A) reductions of all other row moves which involve either $\bold{b_i}$ or $\bold{b_j}$ will be modified. Perhaps we should choose row moves so that the moves they block have minimum S(A) reduction potential. We could combine this idea with the ``greedy'' method; selecting a row move with the greatest difference between the amount it reduces S(A) and the average S(A) reduction of all the moves it blocks.