Running Msieve

[frmky]

Hi,

I ran some timing tests on the new threaded linear algebra in msieve-1.22. I used a workstation with two Xeon 5160 dual-core processors. The matrix is from the factorization of 4^323+3^323, which has an SNFS difficulty of 195 digits. The details of the matrix from the log file are

Tue May 29 22:45:48 2007  commencing linear algebra
Tue May 29 22:45:48 2007  factor base loaded:
Tue May 29 22:45:48 2007  849252 rational ideals (max prime = 12999997)
Tue May 29 22:45:48 2007  848793 algebraic ideals (max prime = 12999997)
Tue May 29 22:45:49 2007  read 1505438 cycles
Tue May 29 22:45:55 2007  cycles contain 3820450 unique relations
Tue May 29 22:46:18 2007  read 3820450 relations
Tue May 29 22:46:24 2007  using 32 quadratic characters above 268435244
Tue May 29 22:48:17 2007  matrix is 1505238 x 1505438 with weight 132481035 (avg 88.00/col)
Tue May 29 22:48:21 2007  filtering completed in 1 passes
Tue May 29 22:48:22 2007  matrix is 1505238 x 1505438 with weight 132481035 (avg 88.00/col)
Tue May 29 22:48:41 2007  saving the first 48 matrix rows for later
Tue May 29 22:48:42 2007  matrix is 1505190 x 1505438 with weight 100149145 (avg 66.52/col)
Tue May 29 22:48:42 2007  matrix includes 64 packed rows
Tue May 29 22:48:42 2007  using block size 65536 for processor cache size 4096 kB

Here are the results, with comparisons to the 1 thread case:

1 thread 06:59:12
2 threads, using both cores on 1 processor 05:39:03 (19.1% less)
2 threads, using 1 core on each processor 04:09:22 (40.5% less)
4 threads 03:58:52 (43% less)

As you can see, using 1 core on each processor is much better than using 2 cores on the same processor, but moving from 1 core on each processor to both cores on each processor doesn't make that much of a difference.

Greg

[fivemack]

Originally Posted by Andi47

With enough relations (4.9M) the linear algebra succeeded anyway.

Error -14 means that the product of the given algebraic factors doesn't equal the value of the polynomial at the point (A,B); whenever there's an error message that relation is simply ignored, so you don't have to worry about it contaminating the matrix.

[Andi47]

Originally Posted by jasonp

Andi, congrats on finishing. Other people have reported the -14 errors and I'm investigating. My guess is that your old factor base had a mistaken entry or two, which the new code caught.

Is it dependend on an old (1.21) factor base, when relations which have definitely been found with 1.22 ("error -14 reading relation 4.7M and something") give error -14?

P.S.: What is error -3? I got one of them with one of the relations - see my outputfile in my previous post.

P.P.S.: My second NFS factorisation which I had started with 1.22 also finished, it showed no errors, neither -14, nor -3.

[jasonp]

Originally Posted by Andi47

P.S.: What is error -3? I got one of them with one of the relations - see my outputfile in my previous post.

-3 is an error that only happens to free relations. When free relations get added, there is minimal checking to make sure a free relation is valid, and the code only is rigorous when the filtering starts. This technically means you can get one or two relation read failures even if nothing is wrong (I've seen this many times by now).

[BotXXX]

I'm currently sieving a 138-digit number with the tools from GGNFS, i would like to use msieve to build the matrix and complete the factorisation. But i'm running into a small problem. I've set up the msieve configuration with help of this post ( http://www.mersenneforum.org/showpos...&postcount=403 ) and 'imported' the relations GGNFS has found so far (only half way, but just trying it out for the moment). When starting msieve with the command "msieve -nc -v" the following happens:

Msieve v. 1.23
Fri Jun 08 16:30:55 2007
random seeds: 0e1bf7fc 13ac1047
factoring 127.........879 (138 digits)
commencing number field sieve (137-digit input)
R0: -146372720447233464294631106
R1:  1091334310409821
A0:  42943782279228296573571095930067
A1: -2586201753157187479015023504
A2:  31338013316569083031446
A3:  275981660844953476
A4: -335895729241
A5:  1894140
size score = 0.000000e+000, Murphy alpha = 0.000000, combined = 0.000000e+000

As you can see, it recognises the input of 138 digits, but for th nfs it only uses 137-digits? And therefor i think that it also can not place a score to the poly? Is this correct?

I'm using the available Windows binary from your website, also had the problem with versie 1.22. I just tried to compile a local version, but am running into problems with Msys to complie msieve. the gls toolkit is not integrated, etc.

[jasonp]

Originally Posted by BotXXX

As you can see, it recognises the input of 138 digits, but for th nfs it only uses 137-digits? And therefor i think that it also can not place a score to the poly? Is this correct?

I'm using the available Windows binary from your website, also had the problem with versie 1.22. I just tried to compile a local version, but am running into problems with Msys to complie msieve. the gls toolkit is not integrated, etc.

GSL is straightforward to build in Msys, it just takes a while.

I've noticed the difference in input size for other jobs too, it's a harmless problem. Basically the first printout is always right, and the second printing of the number is an estimate that is (often!) wrong. The errors evaluating the polynomial are due to problems with GSL's numerical integration code, which are harmless if you are only using '-nc'. Brian Gladman has given me new integration code which the next release will have, and which should work in all cases (and remove the GSL dependency).

[akruppa]

I just found that for building msieve on x86-64 Fedora Core 6, you need to add -lgslcblas to the list of libraries, i.e. with

LIB_GSL = -lgsl -lgslcblas

in the Makefile.

Alex

[fivemack]

Originally Posted by jasonp

Now available. This is an interim release to get some linear algebra and NFS filtering fixes out, that seem to be necessary to complete big NFS jobs using msieve.

The plan for the next version is the same as before. Happy factoring,
jasonp

Is there some minimum size of matrix for which the threading is used? We have a 2S4C Opteron machine at work, I tried running the matrix from a tiny (C80 MPQS) example with -t 1, -t 2 and -t 4, and

matrix is 40629 x 40741 with weight 873408 (avg 21.44/col)
matrix includes 64 packed rows
commencing Lanczos iteration
lanczos halted after 644 iterations

msieve-1.23/msieve -v -t 1   32.32s user 0.09s system 99% cpu 32.428 total
msieve-1.23/msieve -v -t 2   32.13s user 0.10s system 99% cpu 32.245 total
msieve-1.23/msieve -v -t 4   32.55s user 0.16s system 99% cpu 32.730 total

[jasonp]

Originally Posted by fivemack

Is there some minimum size of matrix for which the threading is used?

Yes, the matrix has to have at least 250k columns. You can change this by modifying MIN_NCOLS_TO_THREAD in common/lanczos/lanczos.h. Also, threading is only used when the matrix is packed into block form, and that's only done if it has more than MIN_NCOLS_TO_PACK (=50k) columns

On my home machine the lanczos iteration for a matrix of this size with one thread takes less than 10 minutes, and I didn't think it worthwhile to fight the synchonization overhead when each iteration runs so quickly. With the current architecture and N threads, each matrix multiply requires 2*N-2 thread spawn/join calls. A different architecture, that spawns threads once and reuses them for each matrix multiply, could reduce that overhead, but synchronizing a thread pool like that is much more tricky than I as willing to deal with.

PS: you can add gslcblas to the msieve makefile or you can configure GSL with --disable-shared

[antiroach]

Are 109 digit numbers too large for msieve QS to do? I just tried it and got this :

./msieve -v 6287519180589851139882693558840635632241012858583497665823906751707884219221125879481642916986596731056494167


Msieve v. 1.24
Wed Jun 27 20:49:20 2007
random seeds: bac9e657 50827a30
factoring 6287519180589851139882693558840635632241012858583497665823906751707884219221125879481642916986596731056494167 (109 digits)
commencing quadratic sieve (109-digit input)
using multiplier of 3
using 64kb Athlon XP sieve core
sieve interval: 26 blocks of size 65536
processing polynomials in batches of 4
using a sieve bound of 5964001 (205333 primes)
using large prime bound of 894600150 (29 bits)
using double large prime bound of 12969765365675250 (46-54 bits)
using trial factoring cutoff of 54 bits
polynomial 'A' values have 14 factors

sieving in progress (press Ctrl-C to pause)
Segmentation fault

[Timmy]

I tried factoring the GGNFS RSA110 test with msieve and it failed in the lanczos stage. The error occurs in lanczos_matmul.c @ line 354 and its an access violation.