next up previous
Next: Lanczos and conjugate gradient Up: No Title Previous: Introduction

  
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 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 [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].


next up previous
Next: Lanczos and conjugate gradient Up: No Title Previous: Introduction
Brian A. LaMacchia
1999-10-25