Empirical Tests Using Algorithm SL

We now present the results of our experimental attempts to solve subset sum problems using Algorithm SL as describes in Section 3.4 above. Following the tabulated results of Radziszowski and Kreher, we attempted to solve random subset sum problems of size n, where:

$$n \in \{42, 50, 58, 66, 74, 82, 90, 98, 106\}.$$

For each value of n, a set of b values (representing the number of bits in the binary representation of the weights a_i) was chosen. Algorithm SL was then run on a number of randomly generated subset sum problems for each pair (n,b). Where possible, values of b were chosen to coincide with values used in [26,33]. Algorithm SL was implemented in FORTRAN and utilized Bailey's multiprecision floating-point package [4]. The Seysen reduction algorithm stored all lattice bases in multiprecision floating point and used both multiprecision and double-precision floating point operations. The size of the multiprecision floating-point representation was changed for each value of n so that b was at most one-half the size of the representation in bits. In many cases significantly more bits were available in the representation to help reduce rounding error. The LLL portion of Algorithm SL was also implemented in FORTRAN but used only integer and double precision operations. One advantage of the Seysen-LLL structure of Algorithm SL is that by the time the LLL stage is reached, the lattice basis to be reduced contains only relatively small integers. In all cases investigated, the input lattice basis to the LLL phase of the algorithm did not contain any single coefficient larger than 2¹⁶. This meant that we could safely store the basis vector coefficients as 32-bit integers, and we could use integer and double-precision floating point to carry out all calculations necessary to run LLL. Avoiding multiprecision row moves during the LLL phase greatly decreases the execution time of Algorithm SL. For values of n < 90, these implementations of the Seysen and LLL algorithms were sufficient for our purposes. However, for $n \in \{90, 98, 106\}$, rounding error started to significantly alter the operation of the algorithm. Recall that the LLL algorithm stores the values of the $\mu_{i,j}$ coefficients as rational numbers; our implementation of LLL used double-precision floating point approximations to decrease the running time of the algorithm. Since such an approximation will introduce error, code was included to detect and attempt to correct errors resulting from rounding in double-precision calculations. In addition, while not changing the operation of the LLL algorithm, we performed a change of variables to reduce the rounding error which is necessarily introduced. LLL as defined in [27] uses two arrays of variables to hold information about the lattice being reduced:
$$\begin{align*}\mu_{i,j} & = \frac{(\bold{b_i},\bold{b_j^*})}{(\bold{b_i},\bold{b... ...\\ B_i & = \Vert\bold{b_i^*}\Vert = (\bold{b_i^*},\bold{b_i^*}). \end{align*}$$
(Note that the $\bold{b_i^*}$ are orthogonalized versions of the $\bold{b_i}$ in LLL, not the basis vectors of the dual lattice as in Seysen's reduction algorithm.) Our version of LLL used three arrays of variables to maintain the same information:

It is not difficult to transform the LLL relations between values of $\mu_{i,j}$ and B_i into equations involving m_i,j, c_i and bb_i. The advantage gained is that:
$$\begin{align*}m_{i,j} & = \frac{(\bold{b_i},\bold{b_j^*})}{\Vert\bold{b_i}\Vert ... ...old{b_i}\Vert \cdot \Vert\bold{b_j^*}\Vert}, \\ & = \cos \alpha, \end{align*}$$
where $\alpha$ is the angle between the vectors $\bold{b_i}$ and $\bold{b_j^*}$. In the original version of LLL,

$$\mu_{i,j} = \frac{\Vert\bold{b_i}\Vert}{\Vert\bold{b_j^*}\Vert} m_{i,j},$$

and thus could take on a wide range of values, depending on the ratio of the lengths of $\bold{b_i}$ and $\bold{b_j^*}$. Limiting $m_{i,j} \in [-1,1]$ and keeping the length information separate in c_i and bb_i reduces the error introduced by double-precision arithmetic operations. (Notice that bb_i values are integers and can be regenerated at will from the integer basis vectors.) Of course, with sufficient multiprecision representation for all variables there is no need for this transformation. It is simply an implementation-specific modification which allowed us to use a fast, double-precision version of LLL to reduce the lattices which arose while solving 106-element subset sum problems.

 

Table 3.1: Test Results Using Algorithm SL for $42 \leq n \leq 58$

n	b	d = n/b	$RM_{\text{S}}$	$RM_{\text{LLL}}$	TL	$\text{S}_5 (\text{S}_1)$	% Solved	Average Time
20 trials for each length b for each n
42	42	1.000	36907	420357	21	20 (19)	1.00	98.39
42	44	0.955	38955	276031	20	20 (20)	1.00	94.67
42	46	0.913	40264	362848	21	20 (19)	1.00	99.88
42	48	0.875	42288	234513	20	20 (20)	1.00	97.65
42	50	0.840	43826	222350	20	20 (20)	1.00	99.67
42	52	0.808	45144	178153	20	20 (20)	1.00	100.29
42	54	0.778	46405	209717	20	20 (20)	1.00	102.56
50	50	1.000	55122	3206204	42	20 ( 9)	1.00	283.93
50	52	0.962	56243	2672637	36	19 (10)	0.95	262.24
50	54	0.926	58249	2112480	31	20 (14)	1.00	243.22
50	56	0.893	59721	1596051	26	20 (16)	1.00	224.80
50	58	0.862	61594	1098460	21	20 (19)	1.00	208.40
50	60	0.833	63604	1220857	22	20 (18)	1.00	217.68
50	62	0.806	65563	978497	21	20 (19)	1.00	210.71
58	58	1.000	73587	15664277	83	7 ( 1)	0.35	808.68
58	60	0.967	77371	13477268	70	10 ( 5)	0.50	744.32
58	63	0.921	80574	13869151	74	13 ( 2)	0.65	837.96
58	66	0.879	82284	12949088	67	12 ( 5)	0.60	803.07
58	69	0.841	87569	7581281	43	19 (10)	0.95	594.55
58	72	0.806	90773	6234735	38	20 (10)	1.00	548.75
58	75	0.773	93896	4408841	29	20 (14)	1.00	480.70
58	78	0.744	98289	3411933	23	20 (18)	1.00	450.66
58	81	0.716	101104	3572104	25	20 (15)	1.00	463.48
58	84	0.690	105325	2090306	20	20 (20)	1.00	412.65
58	87	0.667	107711	1792670	20	20 (20)	1.00	406.44

Tables 3.1 through 3.3 show the results of experiments performed on random subset sum problems with $n \leq 106$. For $n \leq 74$ twenty subset sum problems were attempted per b value. Only ten such problems were attempted per b value for $82 \leq n \leq 106$. For each problem, $\tfrac{1}{2}n$ elements were chosen from among the weights $a_1,\ldots{},a_n$ to be in the subset. During the LLL phase of the algorithm, parameter $\pi_1 = 5$ and $\pi_2 = 8$. Six distinct values of y were used for n < 90; nine were used for $n \geq 90$. All tests were run on Silicon Graphics 4D-220 workstations with four or eight MIPS Computers, Inc., R3000 processors per workstation. Each workstation was equipped with ( $32\text{Mbytes} \cdot \text{ \char93 processors}$) of main memory. As Algorithm SL requires significantly less than $32\text{Mbytes}$ of memory per process, all processors in a given workstation could be used simultaneously to work on different subset sum problems. The majority of the R3000 processors ran at 33MHz; the remainder operated with a clock frequency of 25MHz. All running times reported in Tables 3.1 through 3.3 have been adjusted to reflect the running time on a 33MHz processor. The columns in Tables 3.1 through 3.3 show the value of the following variables for each (n,b) pair:

• n: The number of elements in the set of weights $(a_1,\ldots{},a_n)$. Exactly one-half of these elements were chosen to form the subset sum s.
• b: The number of bits in the binary representation of the a_i's. Each a_i was generated randomly by choosing b random 0-1 variables and concatenating the bits.
• d: The density of this class of subset sum problems. d = n/b.
• $RM_{\text{S}}$: The number of row moves performed by the Seysen phase of Algorithm SL on all trials.
• $RM_{\text{LLL}}$: The number of row moves perform by the LLL phase of Algorithm SL on all trials.
• TL: The total number of lattices reduced by LLL during all attempted trials, where we consider each randomization of the input lattice to be a new lattice. Thus, for 20 trials, $20 \leq TL \leq 20\pi_1 = 100$.
• $\text{S}_5$: The number of subset sum problems successfully solved with $\pi_1 = 5$.
• $\text{S}_1$: The number of subset sum problems successfully solved with $\pi_1 = 1$. This number is useful when comparing the results of Algorithm SL to the Radziszowski-Kreher method.
• % Solved: The success rate for $\pi_1 = 5$ measured as a fraction of the number of attempted problems.
• Average Time: The average amount of CPU time (in seconds) required to run Algorithm SL on a single trial, adjusted to reflect a 33MHz R3000 processor. itemize<<514:>> It should be noted that the running times for Algorithm SL, while an improvement over the Radziszowski-Kreher method, could be improved. The code for SL was not tuned to the Silicon Graphics machine (although Bailey's multiprecision code was written to work with SGI workstations). Careful recoding and tuning of crucial subroutines could probably yield significant improvements without changing the overall operation of the algorithm. A quick look at the results summarized in Table 3.1 shows that Algorithm SL greatly improves upon the performance of previous methods for small values of n ($n \leq 58$). In [33] Radziszowski and Kreher were able to solve all attempted subset sum problems for (n,d)=(42,68), but only managed to solve 30% of the (42,54) problems. Compare this result to SL, which was able to solve all attempted subset sum problems with n = 42 and density $d \leq 1.0$. In fact, SL appears to work as well as a lattice oracle for all $n \leq 50$. The algorithm first shows signs of degradation at n = 58, where a 100% success rate was not reached until b = 72. A true lattice oracle (using the Euclidean norm) should have been able to achieve 100% success at b = 63, where the density d = 0.926 is less than the critical 0.9408 bound. However, SL was still able to solve over half of the attempted subset sum problems at d = 0.962; in [33] the 0.50 success rate was not reached until $d \approx 0.56$. Columns four and five of the Table 3.1 show the number of row moves performed by the Seysen and LLL phases of SL. These numbers are a good first-order approximation of the amount of work performed by each phase, although it should be pointed out that there is no direct correspondence between the absolute magnitudes of the numbers. For fixed n, as b increases the Seysen phase performs more reduction steps on the lattice basis, and less work is required by the LLL phase to find the solution to the subset sum problem. As the density of the system decreases, Seysen's reduction algorithm comes closer to finding the desired solution vector. Indeed, in ten test cases with (n,d) = (24,24), the LLL phase was able to find solutions using only the y = 0.2578125 and y = 0.625 reductions. For higher densities of subset sum problems, the Seysen phase of SL reached a local minimum earlier, and LLL had a greater reduction to perform to find the solution. Note that once a Seysen reduction reached a local minimum it was considered finished; no attempt was made to ``kick'' or ``heat'' the reduced basis and then reapply Seysen. Application of one or more of the techniques described in Section 2.3 might yield better results, and is certainly a topic which should be investigated in the future.
  
   

  Table: Test Results Using Algorithm SL for $66 \leq n \leq 82$

  n	b	d = n/b	$RM_{\text{S}}$	$RM_{\text{LLL}}$	TL	$\text{S}_5 (\text{S}_1)$	% Solved	Average Time
  20 trials for each length b for each n
  66	76	0.868	109671	36111021	90	5 ( 0)	0.25	1774.39
  66	80	0.825	116604	33233636	84	7 ( 1)	0.35	1670.55
  66	84	0.786	120172	23212075	60	16 ( 5)	0.80	1465.55
  66	88	0.750	128015	24791753	63	17 ( 2)	0.85	1560.71
  66	92	0.717	134563	17049844	45	19 ( 9)	0.95	1249.72
  66	96	0.688	139469	14280958	40	19 (10)	0.95	1140.53
  66	100	0.660	142870	10472664	30	20 (11)	1.00	993.57
  66	104	0.635	148379	6026607	21	20 (19)	1.00	819.64
  66	108	0.611	155150	5688732	22	20 (18)	1.00	825.37
  66	112	0.589	162192	4621556	20	20 (20)	1.00	803.30
  74	106	0.698	175993	67316342	85	8 ( 2)	0.40	3416.51
  74	112	0.661	183540	55347194	71	12 ( 4)	0.60	3095.85
  74	118	0.627	189322	51147665	66	13 ( 5)	0.65	2850.97
  74	124	0.597	202651	23245962	33	19 (13)	0.95	1852.46
  74	130	0.569	211750	17077901	25	20 (16)	1.00	1600.57
  10 trials for each length b for each n
  82	134	0.612	122353	74911469	50	0 ( 0)	0.00	8499.82
  82	140	0.586	126724	54569482	37	5 ( 1)	0.50	6144.08
  82	146	0.562	132948	63474238	42	5 ( 0)	0.50	6315.46
  82	152	0.539	139374	22873751	17	10 ( 5)	1.00	3375.16
  82	158	0.519	144353	18199583	14	10 ( 7)	1.00	3154.05

  
  Although Algorithm SL works exceptionally well for small values of n, its performance degrades quickly with respect to n once $n \geq 60$. Table 3.2 shows the performance of SL for n in the range [66,82]. At n = 66, SL did not obtain a 100% success rate until the density dropped to d = 0.66, although the fact that SL solved 19 out of 20 attempts at b = 92 suggests that incrementing $\pi_1$ and/or $\pi_2$ might yield a 100% success rate at d = 0.717. If we consider only successes on the first attempt, SL reached the 100% level at b = 112, compared to b = 144 for Radziszowski and Kreher. (Note too that the method in [33] uses $\pi_1 = 1, 9 \leq \pi_2 \leq 15$, whereas in these experiments $\pi_2 = 8$ for SL.) Similar improvements may be seen for the cases where n = 74 and n = 82. Although at n = 82 Algorithm SL did not attain a success rate of 1.00 until the density had decreased to d = 0.539, similar results were not reported in [33] until d had dropped to below 0.39.
  
   

  Table: Test Results Using Algorithm SL for $90 \leq n \leq 106$

  n	b	d = n/b	$RM_{\text{S}}$	$RM_{\text{LLL}}$	TL	$\text{S}_5 (\text{S}_1)$	% Solved	Average Time
  10 trials for each length b for each n
  90	178	0.506	180739	111553580	40	3 ( 2)	0.30	14300.87
  90	186	0.484	188560	88163144	32	8 ( 2)	0.80	11241.77
  90	194	0.464	196090	67630320	25	8 ( 4)	0.80	9362.65
  90	202	0.446	198909	48109448	19	10 ( 5)	1.00	7277.74
  98	220	0.445	238948	177962307	38	3 ( 3)	0.30	21725.83
  98	228	0.430	249432	187347238	39	6 ( 0)	0.60	21841.45
  98	236	0.415	255213	125193960	28	9 ( 1)	0.90	17064.47
  98	244	0.402	264404	74096833	17	10 ( 6)	1.00	12386.50
  98	252	0.389	277285	39984465	11	10 ( 9)	1.00	9142.08
  98	260	0.377	280876	42340342	13	10 ( 7)	1.00	8560.10
  106	270	0.393	322902	265583840	37	5 ( 1)	0.50	34147.08
  106	280	0.379	335435	177869835	26	9 ( 2)	0.90	25219.92
  106	290	0.366	347679	175847501	26	8 ( 4)	0.80	26034.16
  106	300	0.353	357841	43319759	10	10 (10)	1.00	12137.60
  106	310	0.342	369215	49294587	12	10 ( 8)	1.00	13184.20
  106	320	0.331	375548	39512954	11	10 ( 9)	1.00	11652.82

  
  Table 3.3 shows the performance of SL on subset sum problems with $n \approx 100$. The density at which 100% a success rate is reached is steadily and significantly decreasing for small increases in n. By the time n = 106, SL is able to solve all attempted problems with density $\approx 0.35$, but densities above 0.4 appear unobtainable.
  
    

  Figure 3-8: Algorithm SL: S₁ vs. Density

  
  
  Figure 3-8 shows the success rate for solving subset sum problems on the first randomization ( $\text{S}_1$) versus density for all the test cases described in Tables 3.1 through 3.3. Compare the curves depicted in this figure to those for the Lagarias-Odlyzko (Figure 3-1) and the Radziszowski-Kreher (Figure 3-3) methods. Algorithm SL shows significant improvement over these previous methods and extends the ``frontier'' of solvable subset sum problems. Figure 3-9 shows the success rate versus density when SL was allowed to perform five attempted reductions ( $\text{S}_5$). The improvement made by Algorithm SL over previous methods may clearly be seen by comparing this figure to those shown previously. The shift in the frontier caused by increasing $\pi_1$ from one to five is also apparent.
  
    

  Figure 3-9: Algorithm SL: S₅ vs. Density

  
  
  The performance of Algorithm SL is a vast improvement over the techniques used in [26,33]. Not only is the success rate higher for Algorithm SL, but its improved running time allows larger-sized subset sum problems to be effectively attacked. Nevertheless, for $n \gtrsim 100$ Algorithm SL is still only able to attack subset sum problems with densities below 0.4. Subset sum problems with larger n and higher densities are unsolvable from a practical point of view.