Matrix file format questions

[Dubslow]

Originally Posted by Readme.nfs

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 row positions (each a 32-bit word, with words in arbitrary order), then floor((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.

1) When you say "list of row positions", do you mean that the position count includes the dense rows? I.e., for an array of sparse rows (whose length is nrows-dense_rows), if I read in pos, I should store that in the (pos - dense_rows)th row of the array?

2) The array of bits in little endian order: You mean that the first word gives the entries in the 0-7th dense rows? But, confusingly enough, bit shifts work in big endian fashion, so the 0th dense row is (byte0) & 1, the 1st is (byte0>>1) & 1, and the nth column (n < 8) is (byte0>>n) & 1? And then the 8th dense row is byte1 & 1, and the 9th is (byte1>>1) & 1?

[Dubslow]

Whoops, only now did I see this:

The sparse entries in each column are numbered from D onward.

I guess that answer's question 1.

[jasonp]

The bit positions are chosen so that you can recover bit position X by performing a multiple precision shift-and-mask-bit operation on the dense array for each entry in the matrix. I didn't care about endian-independence; only 5-year-old PowerPCs and the occasional supercomputer are big-endian anymore, and neither of these will restart a LA job that was started elsewhere.

[Batalov]

Originally Posted by jasonp

...only 5-year-old PowerPCs and the occasional supercomputer are big-endian anymore, and neither of these will restart a LA job that was started elsewhere.

SGI is dead as disco (not that there was anything wrong with SGI*... or with disco!), and so is DEC Alpha... All the big-endian powerhouses faded away. /sigh/

*I still have a freeze-dried Han Solo SGI Octane in my storage; it may or may not wake up, and I don't have a monitor cable for it anymore (all of its connectors are weird by these days' standards)

[Dubslow]

Another stupid question:

According to this paper (pg 4) and common sense, given x^2==y^2 mod n, then gcd(x-y,n) might reveal a factor where gcd(x+y,n) doesn't. Why, then, does Msieve only do the latter gcd? (trunk/gnfs/sqrt/sqrt.c, line 486: `mpz_add(tmp1, sqrt_r, sqrt_a); mpz_gcd(tmp1, tmp1, n);` ... )

[jasonp]

It used to do both GCDs, but Pari's MPQS code proved that doing one is sufficient; see the comments there.