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.
Number of Equations
Number of Unknowns
Average Number of Non-zeros per Equation
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 . 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 . 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 7146+1). Set J was produced by the number field sieve factorization of F9. 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 , 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 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 , 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 .