Machines and data

All computations reported in this paper were carried out on a Silicon Graphics 4D-220 computer. It has 4 R3000 MIPS Computers, Inc., 25 MHz processors, each rated at about 18 mips, or 18 times the speed of a DEC VAX 11/780 computer (and about 1.3 times the speed of a DECstation 3100). The parallel processing capability of this system was not used; all times reported here are for a single processor. This machine has 128 Mbytes of main memory.

All programs were written in C or Fortran. They were not carefully optimized, since the aim of the project was only to obtain rough performance figures. Substantial performance improvements can be made fairly easily, even without using assembly language.

 

Table 1: Large sparse sets of equations

Name	Number of Equations	Number of Unknowns	Average Number of Non-zeros per Equation
A	35,987	35,000	20.4
B	52,254	50,001	21.0
C	65,518	65,500	20.4
D	123,019	106,121	11.0
E	82,470	80,015	47.1
E1	82,470	75,015	46.6
F	25,201	25,001	46.7
G	30,268	25,001	47.9
H	61,343	30,001	49.3
I	102,815	80,001	43.2
J	226,688	199,203	48.8
K	288,017	96,321	15.5
K0	216,105	95,216	15.5
K1	165,245	93,540	15.5
K2	144,017	94,395	13.8
K3	144,432	92,344	15.5
K4	144,017	89,003	17.1
K5	115,659	90,019	15.5
K6	101,057	88,291	15.5
L	7,262	6,006	80.5
M	164,841	94,398	16.9

Table 1 describes the linear systems that were used in testing the algorithms. Data sets A through J were kindly provided by A. Lenstra and M. Manasse, and come from their work on factoring integers [12]. Sets A,B and C result from runs of the multiple polynomial quadratic sieve (mpqs) with the single large prime variation, but have had the large primes eliminated. Set D also comes from a run of mpqs, but this time the large primes were still in the data (except that equations with a large prime that does not occur elsewhere were dropped). Set E comes from a factorization that used the new number field sieve, and set E1 was derived from set E by deleting 5000 columns at the sparse end of the matrix. (Set E1was created to simulate a system that has more extra equations than Edoes, but has comparable density.) Sets F and G derive from runs of ppmpqs, the two large prime variation of mpqs [13]. Both sets arose during the factorization of the same integer; set G was obtained by running the sieving operation longer. Sets H and I come from other runs of ppmpqs (set I was produced during the factorization of the 111 decimal digit composite cofactor of 7¹⁴⁶+1). Set J was produced by the number field sieve factorization of F₉. All of these data sets (A-J) were tested modulo 2 only.

Data set K was obtained in the process of computing discrete logarithms modulo a prime p of 192 bits [10], and had to be solved modulo $\frac{p-1}{2}$ (a prime of 191 bits) and modulo 2. Set K was tested modulo both numbers. Sets K0 through K6 and L were derived from set K. Set K2 was derived by deleting the 144,000 equations from F that had the highest number of non-zero entries (weight). Set K4 was derived from K by deleting the 144,000 equations that had the lowest weights. Sets K0, K1, K3, K5, and K6were obtained by deleting randomly chosen equations from K. (The reason the number of unknowns varies in these sets is that in sets $K,K0,\ldots{},K6$, only the unknowns that actually appear in the equations are counted.) Set L was derived from set K by using structured Gaussian elimination. Finally, data set M was produced while computing discrete logarithms modulo a prime p of 224 bits [10].