Msieve 1.53 feedback

[jasonp]

Sorry I did read your previous analysis (thank you that was boneheaded of me) but have been too buried to do anything about it.

[debrouxl]

I noticed that the folks from the "Factoring as a Service" project ( http://seclab.upenn.edu/projects/faas/ ) are using a patched msieve 1.52.
The patch adds some threaded versions of existing functions, but at least one change is presented as a real bugfix certainly worth upstreaming. In gnfs/gnfs.h:

This is a bug fix to the existing mpz_poly_copy() code. A simple memcpy is not sufficient for mpz_t. It must be set correctly using the mpz_set() method.

Patch: https://github.com/eniac/faas/blob/m...s/msieve.patch

[jasonp]

Awesome, thanks for the reference. Yes it's a silly bug and needs fixing.

This paper is the first direct comparison I have seen of the LA in CADO vs Msieve. It also is pretty gratifying that the filtering and LA work exactly as designed on a grid infrastructure I've never used.

[debrouxl]

Indeed. I hadn't yet skimmed the paper, but the comparison is pretty interesting.

I'm not knowledgeable to review MPI code, and by now, I doubt their code needs much additional testing, so I don't think I can be of much help integrating the rest of their changes to upstream msieve.

[jasonp]

The other thing to bear in mind is that Block Weidemann needs 1.5x as many matrix multiplies as Block Lanczos, when otherwise parametrized identically. So there's a significant headwind that the independent parallelism of BW has to fight against, in addition to the communication overhead of parallel matrix-vector products.

Those matrix multiplies are somewhat easier than the BL version, since Block Lanczos need both standard and transpose matrix multiplies. That guides the storage scheme for identifying matrix nonzeros, and gives BW more flexibility.

The MPI code in Msieve was basically made possible by NFS@Home, and made awesome by lots of ideas from Greg and from Ilya Popovyan (poily on the forum).

[fivemack]

In worktodo.ini I put

42857434224874487316101235884625321672621468992767603975720122719934913716966438929751735586358421282460051668796790253996189486073881951577861086006924202623766039565813608207693472680875744587593619524755820478921777990571259251057

In msieve.fb I put

N 42857434224874487316101235884625321672621468992767603975720122719934913716966438929751735586358421282460051668796790253996189486073881951577861086006924202623766039565813608207693472680875744587593619524755820478921777990571259251057
SKEW 1
A0 56783761
A3 56783758
A6 56806369
R0 591541410726415701383522368056534442849
R1 -1

But when I run msieve -v -nc1 to get the combined-score value, it tells me 'warning: NFS input not found in factor base file'.

This turns out to be because the number is divisible by three, and msieve took out that factor before looking in the factor base file. Removing the factor manually makes it work.

[chris2be8]

I've just has a long trip down the garden path debugging what turned out to be an error in my script. The symptom was that msieve did absolutely nothing when called with an empty ini file:

chris@linux-5hwg:~/bin> /home/chris/ggnfs/bin/msieve -i /dev/null
chris@linux-5hwg:~/bin>

I spend about an hour trying to work out why the script wasn't calling msieve before I realized it was calling msieve, but msieve was being coy.

I got the same (lack of) output with Msieve v. 1.52 (SVN 956) and with Msieve v. 1.53 (SVN 988M)

Some output to indicate that msieve had been called but could not find anything in the ini file would have saved a lot of puzzling.

Chris

[xilman]

Originally Posted by chris2be8

The symptom was that msieve did absolutely nothing when called with an empty ini file

You asked for it, you got it.

Originally Posted by chris2be8

Some output to indicate that msieve had been called but could not find anything in the ini file would have saved a lot of puzzling.

Perhaps so.

This is a screen shot taken just now to show typical behaviour on my systerm:

pcl@anubis ~ $ cat < /dev/null
pcl@anubis ~ $ bc < /dev/null
pcl@anubis ~ $ mkdir foo
pcl@anubis ~ $ cd foo
pcl@anubis ~/foo $ ls
pcl@anubis ~/foo $

You might be on to something.

[jasonp]

I see what you mean; probably worth a fix

[Dubslow]

Just saw this on an otherwise uninteresting C119 from an aliquot sequence:

commencing linear algebra
read 719173 cycles
cycles contain 2543430 unique relations
read 2543430 relations
using 20 quadratic characters above 134216912
building initial matrix
memory use: 317.8 MB
read 719173 cycles
matrix is 718994 x 719173 (216.7 MB) with weight 67200164 (93.44/col)
sparse part has weight 48891645 (67.98/col)
filtering completed in 2 passes
matrix is 717247 x 717426 (216.5 MB) with weight 67132467 (93.57/col)
sparse part has weight 48871111 (68.12/col)
matrix starts at (0, 0)
matrix is 717247 x 717426 (216.5 MB) with weight 67132467 (93.57/col)
sparse part has weight 48871111 (68.12/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 717199 x 717426 (207.7 MB) with weight 53501684 (74.57/col)
sparse part has weight 47283662 (65.91/col)
using block size 8192 and superblock size 786432 for processor cache size 8192 kB
commencing Lanczos iteration (4 threads)
memory use: 161.3 MB
linear algebra at 0.4%, ETA 0h15m717426 dimensions (0.4%, ETA 0h15m)    
linear algebra completed 717105 of 717426 dimensions (100.0%, ETA 0h 0m)    
lanczos halted after 11343 iterations (dim = 717197)
recovered 29 nontrivial dependencies
BLanczosTime: 1089
nfs: commencing msieve sqrt

commencing square root phase
reading relations for dependency 1
read 358809 cycles
cycles contain 1272586 unique relations
read 1272586 relations
multiplying 1272586 relations
multiply complete, coefficients have about 58.21 million bits
initial square root is modulo 227729329
Newton iteration failed to converge
algebraic square root failed

[jyb]

Originally Posted by Dubslow

Just saw this on an otherwise uninteresting C119 from an aliquot sequence:

commencing linear algebra
read 719173 cycles
cycles contain 2543430 unique relations
read 2543430 relations
using 20 quadratic characters above 134216912
building initial matrix
memory use: 317.8 MB
read 719173 cycles
matrix is 718994 x 719173 (216.7 MB) with weight 67200164 (93.44/col)
sparse part has weight 48891645 (67.98/col)
filtering completed in 2 passes
matrix is 717247 x 717426 (216.5 MB) with weight 67132467 (93.57/col)
sparse part has weight 48871111 (68.12/col)
matrix starts at (0, 0)
matrix is 717247 x 717426 (216.5 MB) with weight 67132467 (93.57/col)
sparse part has weight 48871111 (68.12/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 717199 x 717426 (207.7 MB) with weight 53501684 (74.57/col)
sparse part has weight 47283662 (65.91/col)
using block size 8192 and superblock size 786432 for processor cache size 8192 kB
commencing Lanczos iteration (4 threads)
memory use: 161.3 MB
linear algebra at 0.4%, ETA 0h15m717426 dimensions (0.4%, ETA 0h15m)    
linear algebra completed 717105 of 717426 dimensions (100.0%, ETA 0h 0m)    
lanczos halted after 11343 iterations (dim = 717197)
recovered 29 nontrivial dependencies
BLanczosTime: 1089
nfs: commencing msieve sqrt

commencing square root phase
reading relations for dependency 1
read 358809 cycles
cycles contain 1272586 unique relations
read 1272586 relations
multiplying 1272586 relations
multiply complete, coefficients have about 58.21 million bits
initial square root is modulo 227729329
Newton iteration failed to converge
algebraic square root failed

I see this happen occasionally, but msieve just moves on to the next dependency, so it's not really a big problem. Did that not happen here?