6^383+1 by GNFS is complete. Thanks!

[fivemack]

Thanks to the enormous amount of sieving that's been possible by having contributors in three continents, the matrix is of an almost convenient size - no bigger than the matrices that NFSnet have had to deal with for SNFS on numbers of 800 bits.

matrix is 9331810 x 9331986 (2483.5 MB) with weight 829935487 (88.93/col)
sparse part has weight 539050715 (57.76/col)
saving the first 48 matrix rows for later
matrix is 9331762 x 9331986 (2401.9 MB) with weight 627984794 (67.29/col)
sparse part has weight 536323527 (57.47/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (4 threads)
memory use: 2554.7 MB
linear algebra completed 508 out of 9331986 dimensions (0.0%)

The post-processing used an 8GB machine, but since the matrix itself fits in 4GB

22385 nfsslave  18   0 2959m 2.9g  464 R  234 75.3  42:16.29 msieve

I can run it on a machine on which I have not observed threaded-msieve to fail; I'm getting around 400 dimensions a minute, so 9.3 million dimensions in about 25000 minutes, which is under three weeks.

[Andi47]

Originally Posted by fivemack

Thanks to the enormous amount of sieving that's been possible by having contributors in three continents, the matrix is of an almost convenient size - no bigger than the matrices that NFSnet have had to deal with for SNFS on numbers of 800 bits.

Two questions:

1.) How many unique relations did you get?
2.) Is it oversieved (if yes, how much?), or do we have just enough relations?

[fivemack]

Fri Jan 18 20:35:52 2008  found 68941674 hash collisions in 227965000 relations
Fri Jan 18 20:35:52 2008  commencing duplicate removal, pass 2
Fri Jan 18 21:01:12 2008  found 43495997 duplicates and 184469003 unique relations

I'm not sure what the right definition of 'oversieved' is - I suppose I think of anything which does clique-removal to get to 70% excess as oversieved, but the matrix-preparation for this run behaved in a rather different way to anything I'd seen before (log attached), with the filtering bound starting off enormous and going downwards, via huge amounts of clique removal, to denser and denser matrices.

I suspect this was substantially oversieved, but since the compute power available for sieving is significantly greater than that available for linear algebra, oversieving is the way to go - you can actually save a day of real-time at the matrix step by spending a day of real-time sieving.

[jasonp]

Originally Posted by fivemack

the matrix-preparation for this run behaved in a rather different way to anything I'd seen before (log attached), with the filtering bound starting off enormous and going downwards, via huge amounts of clique removal, to denser and denser matrices.

This is a consequence of using 31-bit large primes. The estimate for the initial filtering bound is much too large because it is the arithmetic mean of all the primes in relations, and when you have large primes bigger than 29 bits the average starts off much too large. I'm actually happy you got a decent matrix given this kind of handicap. One thing I noticed is that once the matrix was built the linear algebra pruned its size by about 8%, and this is rather a lot, suggesting that there were still a lot of singletons and cliques that the filtering could have pruned. You may be able to get a better matrix if you manually force the initial filtering bound, via args to -nc1, to be 2-3x the factor base bound. Recent NFSNET jobs may also suffer from this problem, though it wouldn't be as acute there because they were not so heavily oversieved.

I think the code would be able to get a better initial bound estimate by computing a histogram of all the primes in relations, and choosing the bound to be the middle of the first bin at which the number of primes per relation drops below X, so that filtering will start at the point where the dataset is sparsely populated with large primes.

[xilman]

Originally Posted by jasonp

I think the code would be able to get a better initial bound estimate by computing a histogram of all the primes in relations, and choosing the bound to be the middle of the first bin at which the number of primes per relation drops below X, so that filtering will start at the point where the dataset is sparsely populated with large primes.

When I first started reading your post, the word "mode" came to mind. Your last paragraph (quoted) shows we're thinking alike.


Paul

[jasonp]

Tom, could you try replacing gnfs/filter/duplicate.c with the attached, then rerunning just the duplicate removal and the beginning of the singleton removal? I've made the changes above, and it produces a better initial filtering bound in a few local tests.

[fivemack]

It is with mild vexation that I must report that the first matrix job on 6^383+1 has failed - it's got to 104% completeness, after two weeks on a quad-core of known reliability, and I've never observed a successful matrix get to more than 100%.

This is the matrix produced without applying jasonp's patch; I'll do that this evening and set the quad-core running for another two weeks.

[jasonp]

Originally Posted by fivemack

It is with mild vexation that I must report that the first matrix job on 6^383+1 has failed - it's got to 104% completeness, after two weeks on a quad-core of known reliability, and I've never observed a successful matrix get to more than 100%.

This is the matrix produced without applying jasonp's patch; I'll do that this evening and set the quad-core running for another two weeks.

In the worst case you'll have to revert to an older version of the linear algebra, one that doesn't use the fancy threading patches.

[fivemack]

It is with slightly more than mild vexation that I must report that the second matrix job on 6^383+1 has failed; it completed the Lanczos step without issue, but found only trivial kernel vectors.

I have a backlog of slightly smaller Cunningham numbers to process; the next thing I'll try is processing with a filtering bound equal to the factor-base size. I've enough memory to handle a denser matrix, and my suspicion is that the over-sieving plus the quest for sparseness has led to a matrix where A^T A has too large a kernel. I'll see how this goes by the beginning of March.

[R.D. Silverman]

Originally Posted by fivemack

It is with slightly more than mild vexation that I must report that the second matrix job on 6^383+1 has failed; it completed the Lanczos step without issue, but found only trivial kernel vectors.

I have a backlog of slightly smaller Cunningham numbers to process; the next thing I'll try is processing with a filtering bound equal to the factor-base size. I've enough memory to handle a denser matrix, and my suspicion is that the over-sieving plus the quest for sparseness has led to a matrix where A^T A has too large a kernel. I'll see how this goes by the beginning of March.

Join the club. I failed twice with 6,299-.

I frequently find that the CWI solver fails if the matrix is too sparse.

[xilman]

Originally Posted by R.D. Silverman

Join the club. I failed twice with 6,299-.

I frequently find that the CWI solver fails if the matrix is too sparse.

Only once have I had the CWI Lanczos fail on me for over-sparseness, that for 2,811- when I hit other problems trying to build a denser matrix.

I try to aim for a small dense matrix, only slightly over-square. The CWI filter code makes it very hard to go over-dense but very easy to make it over-sparse.


Paul