All computations reported in this paper were carried out on a Silicon Graphics 4D220 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.
Name 
Number of Equations 
Number of Unknowns 
Average Number of Nonzeros 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^{146}+1). Set J was produced by the number field sieve factorization of F_{9}. All of these data sets (AJ) 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 (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 nonzero 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 , 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].