GF(2) Matrix request

[oslik]

Hi everyone. I'm now in a process of writing and testing the linear algebra
step for GNFS (or QS), whoose goal is to solve linear system on GF(2).
My realization is a realization of Block-Coppersmith algorithm and is intended
for use on parallel computers (using MPI-interface). Block-Coppersmith can be parallelized much better, than Block-Lanscoz, which is now used in
GGNFS and msieve programs, so that may be a good option for handling
really large numbers.

As I understood from this forum, many of you are doing hard job in factoring
large integers using GGNFS or msieve programs, sometimes sieving takes a very long time. My question is, that if someone can give me some test matrices for linear algebra step, I will appreciate it very much. I hope, that after some testing I will be able to present a version of Block-Coppersmith for clusters and maybe even for distributed computations (I have some ideas and progs for that).

So, I ask for matrices, of any size :-)

Thank you in advance,
Ivan.

[jasonp]

Originally Posted by oslik

My question is, that if someone can give me some test matrices for linear algebra step, I will appreciate it very much. I hope, that after some testing I will be able to present a version of Block-Coppersmith for clusters and maybe even for distributed computations (I have some ideas and progs for that).

So, I ask for matrices, of any size :-)

I hope you have lots of disk space :)

The largest matrix I have on disk has size about 4M, which is only moderately large considering the size of current NFS efforts. With enough compression it should fit on a single CD. Send me email to coordinate delivery if you're interested; others here can offer far larger matrices

[fivemack]

Originally Posted by oslik

So, I ask for matrices, of any size :-)

Thank you in advance,
Ivan.

In what format do you want these matrices? Tens of millions of lines of 'X Y\n'?

And what sort of size are you really after? The standard processing programs tend not to write out matrices in full, though obviously they could be persuaded to; a large factorisation I have lying around is

Constructed a 2916896 x 2917143 matrix of weight 202031153 in 82 minutes
Solved in 23.5 hours (two CPUs), using 1.5G memory

but writing out that matrix would take most of a CD in compressed form. I have significantly smaller ones available, too, from 120 rather than 206-digit SNFS.

[jasonp]

Originally Posted by fivemack

In what format do you want these matrices? Tens of millions of lines of 'X Y\n'?

And what sort of size are you really after? The standard processing programs tend not to write out matrices in full, though obviously they could be persuaded to; a large factorisation I have lying around is

Since the latest msieve version does checkpoint and restart, the whole matrix is in fact written to disk, in a completely undocumented binary format.

Actually, maybe it would be a valuable exercise to document all the on-disk formats of the intermediate files. That would let other programs interoperate, and it's a big win to use the same relation format as GGNFS :)

[henryzz]

would it be possible for someone to write a parellized siever as well so all the slowest bits can be shared

[akruppa]

Sieving already is embarrasingly parallel. Just assign different ranges of b-values or special-q values to different machines.

Alex

[frmky]

I can send a 6.4M matrix your way once I know the format you want, and how to put an msieve matrix in that format. Perhaps msieve 1.29's binary format would be easiest.

Greg

[oslik]

Thank you for you replies. I've PM-ed everyone with details :-)
The format I'm looking for can be any format I can read from file and convert in to GGNFS matrix format (I looks very convenient for handling sparse matrices). I'll report the results as soon as they are available and hope to present them and even the code :-)

[jasonp]

Greg, the easiest way to produce the matrix file is to rerun the filtering using msieve 1.29, then start the linear algebra. This will produce msieve.dat.mat; for linear algebra experiments that will not use the dependencies that are generated, you only need this file. Apologies that this will take hours though :(

In case anyone is interested, here's the binary format (it's really easy):

The matrix file is an array of 32-bit words, with byte ordering determined by the machine that produced the matrix (it will be little-endian for just about everybody). The nonzero matrix entries are stored by column, because they are easy to generate that way. The first word in the file is the number of rows, the second is the number of dense rows ('D'), and the third is the number of matrix columns. Each column is then dumped out. For each column, there is a 32-bit word indicating the number of sparse entries in the column, then a list of that many nonzero column positions (each a 32-bit word, with words in arbitrary order), then (D+31)/32 words for the dense rows in that column. The latter should be treated as an array of D bits in little-endian word order.

Rows are numbered from 0 to (number of rows - 1). Rows 0 to D-1 are considered dense, with a set bit in the bitfield indicating a nonzero entry for that column. The sparse entries in each column are numbered from D onward. Functions dump_matrix and read_matrix, in gnfs/gf2.c, give sample code for writing to / reading from the matrix file.

Does the above make sense? Does anyone think it would be a good idea to compress the above somehow? For example, for matrices with < 16M rows and columns (this is enough for 200-digit GNFS) all the 32-bit quantities can be stored as 24-byte integers, saving 1/4 of the disk space.

[oslik]

Yes it maybe worth for large matrices.Another idea may be to "zip" a matrix somehow, because if you store a sparse matrices (from GGNFS factorization) it is smaller in zip format, so there is a room for improvement :-). Maybe you can store not indices
but their differences in each column (not the index, but the distance to the next non-zero entry), so fewer bits for the matrix storage.

[frmky]

Originally Posted by jasonp

Apologies that this will take hours though :(

A few hours of time is the least of my worries, especially if it will lead to an efficient, parallel, public LA implementation.

Originally Posted by jasonp

Does anyone think it would be a good idea to compress the above somehow?

I personally don't think it really matters. If there are lots of 0's, then that just means it will compress better when shipped from one place to another. Hard drives are large now, so the space during a run doesn't matter. It will take a bit longer to access, but as long as it is rarely accessed on disk during a run, it doesn't seem to make much difference.

Greg