Another large filtering job
 

Jason,

Here's the output of another large filtering job, 2,949+. Since msieve doesn't thread well on this 8-way quadcore computer I planned to move the matrix to a Core 2 quadcore, but it doesn't fit in 4GB of memory. We will have to do more sieving to get it to fit.

[CODE]Tue May 20 01:45:01 2008 Msieve v. 1.36
Tue May 20 01:45:01 2008 random seeds: 18baf458 85dd8e60
Tue May 20 01:45:01 2008 factoring 15953654164085048204147234739858829750770024
8827866272054279599480424280767338982697579495258848375150153519055443517739141989106990625338794428717145409749815953116707251616361046680221057 (189 digits)
Tue May 20 01:45:03 2008 no P-1/P+1/ECM available, skipping
Tue May 20 01:45:03 2008 commencing number field sieve (189-digit input)
Tue May 20 01:45:04 2008 R0: -89202980794122492566142873090593446023921665
Tue May 20 01:45:04 2008 R1: 9444732965739290427392
Tue May 20 01:45:04 2008 A0: -1
Tue May 20 01:45:04 2008 A1: -3
Tue May 20 01:45:04 2008 A2: 6
Tue May 20 01:45:04 2008 A3: 4
Tue May 20 01:45:04 2008 A4: -5
Tue May 20 01:45:04 2008 A5: -1
Tue May 20 01:45:04 2008 A6: 1
Tue May 20 01:45:04 2008 size score = 1.795073e-12, Murphy alpha = 3.125762, combined = 7.348938e-13
Tue May 20 01:46:04 2008 restarting with 161998431 relations
Tue May 20 01:46:04 2008
Tue May 20 01:46:04 2008 commencing relation filtering
Tue May 20 01:46:04 2008 commencing duplicate removal, pass 1
... errors snipped ...
Tue May 20 02:16:51 2008 found 33963863 hash collisions in 161997762 relations
Tue May 20 02:16:51 2008 commencing duplicate removal, pass 2
Tue May 20 02:32:50 2008 found 1 duplicates and 161997761 unique relations
Tue May 20 02:32:50 2008 memory use: 973.5 MB
Tue May 20 02:34:06 2008 ignoring smallest 5516229 rational and 5516281 algebraic ideals
Tue May 20 02:34:06 2008 filtering rational ideals above 95485952
Tue May 20 02:34:06 2008 filtering algebraic ideals above 95485952
Tue May 20 02:34:06 2008 need 16548765 more relations than ideals
Tue May 20 02:34:06 2008 commencing singleton removal, pass 1
Tue May 20 03:06:56 2008 relations with 0 large ideals: 924619
Tue May 20 03:06:56 2008 relations with 1 large ideals: 7022856
Tue May 20 03:06:56 2008 relations with 2 large ideals: 25605237
Tue May 20 03:06:56 2008 relations with 3 large ideals: 50282613
Tue May 20 03:06:56 2008 relations with 4 large ideals: 53178147
Tue May 20 03:06:56 2008 relations with 5 large ideals: 24984289
Tue May 20 03:06:56 2008 relations with 6 large ideals: 0
Tue May 20 03:06:56 2008 relations with 7+ large ideals: 0
Tue May 20 03:06:56 2008 161997761 relations and about 93108785 large ideals
Tue May 20 03:06:56 2008 commencing singleton removal, pass 2
Tue May 20 03:39:41 2008 found 17148624 singletons
Tue May 20 03:39:41 2008 current dataset: 144849137 relations and about 75222721 large ideals
Tue May 20 03:39:41 2008 commencing singleton removal, pass 3
Tue May 20 04:09:23 2008 relations with 0 large ideals: 924619
Tue May 20 04:09:23 2008 relations with 1 large ideals: 6783623
Tue May 20 04:09:23 2008 relations with 2 large ideals: 23901762
Tue May 20 04:09:23 2008 relations with 3 large ideals: 45426000
Tue May 20 04:09:23 2008 relations with 4 large ideals: 46558291
Tue May 20 04:09:23 2008 relations with 5 large ideals: 21254842
Tue May 20 04:09:23 2008 relations with 6 large ideals: 0
Tue May 20 04:09:23 2008 relations with 7+ large ideals: 0
Tue May 20 04:09:23 2008 144849137 relations and about 107248356 large ideals
Tue May 20 04:09:23 2008 commencing singleton removal, pass 4
Tue May 20 04:39:05 2008 found 25071772 singletons
Tue May 20 04:39:05 2008 current dataset: 119777365 relations and about 80323425 large ideals
Tue May 20 04:39:05 2008 commencing singleton removal, pass 5
Tue May 20 05:04:06 2008 relations with 0 large ideals: 924619
Tue May 20 05:04:06 2008 relations with 1 large ideals: 6382924
Tue May 20 05:04:06 2008 relations with 2 large ideals: 21195641
Tue May 20 05:04:06 2008 relations with 3 large ideals: 38105590
Tue May 20 05:04:06 2008 relations with 4 large ideals: 37047307
Tue May 20 05:04:06 2008 relations with 5 large ideals: 16121284
Tue May 20 05:04:06 2008 relations with 6 large ideals: 0
Tue May 20 05:04:06 2008 relations with 7+ large ideals: 0
Tue May 20 05:04:06 2008 119777365 relations and about 97401792 large ideals
Tue May 20 05:04:06 2008 commencing singleton removal, pass 6
Tue May 20 05:29:12 2008 found 19361650 singletons
Tue May 20 05:29:12 2008 current dataset: 100415715 relations and about 76719829 large ideals
Tue May 20 05:29:12 2008 commencing singleton removal, pass 7
Tue May 20 05:50:30 2008 found 5229533 singletons
Tue May 20 05:50:30 2008 current dataset: 95186182 relations and about 71377823 large ideals
Tue May 20 05:50:30 2008 commencing singleton removal, pass 8
Tue May 20 06:10:45 2008 found 1335973 singletons
Tue May 20 06:10:45 2008 current dataset: 93850209 relations and about 70033770 large ideals
Tue May 20 06:10:45 2008 commencing singleton removal, pass 9
Tue May 20 06:30:45 2008 found 330680 singletons
Tue May 20 06:30:45 2008 current dataset: 93519529 relations and about 69702558 large ideals
Tue May 20 06:30:45 2008 commencing singleton removal, final pass
Tue May 20 06:57:33 2008 memory use: 1844.2 MB
Tue May 20 06:57:33 2008 commencing in-memory singleton removal
Tue May 20 06:57:56 2008 begin with 93519529 relations and 78633825 unique ideals
Tue May 20 07:05:39 2008 reduce to 82811726 relations and 67709127 ideals in 18 passes
Tue May 20 07:05:39 2008 max relations containing the same ideal: 34
Tue May 20 07:06:07 2008 filtering rational ideals above 720000
Tue May 20 07:06:07 2008 filtering algebraic ideals above 720000
Tue May 20 07:06:07 2008 need 116164 more relations than ideals
Tue May 20 07:06:07 2008 commencing singleton removal, final pass
Tue May 20 08:56:11 2008 keeping 72175588 ideals with weight <= 20, new excess is 6565882
Tue May 20 08:59:30 2008 memory use: 2625.2 MB
Tue May 20 08:59:31 2008 commencing in-memory singleton removal
Tue May 20 08:59:56 2008 begin with 82811726 relations and 72175588 unique ideals
Tue May 20 09:04:58 2008 reduce to 82808720 relations and 72172582 ideals in 10 passes
Tue May 20 09:04:58 2008 max relations containing the same ideal: 20
Tue May 20 09:07:36 2008 removing 4400344 relations and 4000344 ideals in 400000 cliques
Tue May 20 09:07:41 2008 commencing in-memory singleton removal
Tue May 20 09:08:04 2008 begin with 78408376 relations and 72172582 unique ideals
Tue May 20 09:13:20 2008 reduce to 78259199 relations and 68022023 ideals in 11 passes
Tue May 20 09:13:20 2008 max relations containing the same ideal: 20
Tue May 20 09:15:41 2008 removing 3208248 relations and 2808248 ideals in 400000 cliques
Tue May 20 09:15:45 2008 commencing in-memory singleton removal
Tue May 20 09:16:08 2008 begin with 75050951 relations and 68022023 unique ideals
Tue May 20 09:20:13 2008 reduce to 74964603 relations and 65126917 ideals in 9 passes
Tue May 20 09:20:13 2008 max relations containing the same ideal: 20
Tue May 20 09:22:26 2008 removing 2823664 relations and 2423664 ideals in 400000 cliques
Tue May 20 09:22:30 2008 commencing in-memory singleton removal
Tue May 20 09:22:52 2008 begin with 72140939 relations and 65126917 unique ideals
Tue May 20 09:25:53 2008 reduce to 72070157 relations and 62632102 ideals in 7 passes
Tue May 20 09:25:53 2008 max relations containing the same ideal: 20
Tue May 20 09:28:00 2008 removing 2600206 relations and 2200206 ideals in 400000 cliques
Tue May 20 09:28:04 2008 commencing in-memory singleton removal
Tue May 20 09:28:24 2008 begin with 69469951 relations and 62632102 unique ideals
Tue May 20 09:31:18 2008 reduce to 69406730 relations and 60368311 ideals in 7 passes
Tue May 20 09:31:18 2008 max relations containing the same ideal: 20
Tue May 20 09:33:19 2008 removing 2452608 relations and 2052608 ideals in 400000 cliques
Tue May 20 09:33:23 2008 commencing in-memory singleton removal
Tue May 20 09:33:43 2008 begin with 66954122 relations and 60368311 unique ideals
Tue May 20 09:36:52 2008 reduce to 66895468 relations and 58256743 ideals in 8 passes
Tue May 20 09:36:52 2008 max relations containing the same ideal: 20
Tue May 20 09:38:49 2008 removing 2339518 relations and 1939518 ideals in 400000 cliques
Tue May 20 09:38:53 2008 commencing in-memory singleton removal
Tue May 20 09:39:11 2008 begin with 64555950 relations and 58256743 unique ideals
Tue May 20 09:41:50 2008 reduce to 64500111 relations and 56261060 ideals in 7 passes
Tue May 20 09:41:50 2008 max relations containing the same ideal: 20
Tue May 20 09:43:42 2008 removing 2253412 relations and 1853412 ideals in 400000 cliques
Tue May 20 09:43:46 2008 commencing in-memory singleton removal
Tue May 20 09:44:04 2008 begin with 62246699 relations and 56261060 unique ideals
Tue May 20 09:46:36 2008 reduce to 62193222 relations and 54353849 ideals in 7 passes
Tue May 20 09:46:36 2008 max relations containing the same ideal: 20
Tue May 20 09:48:24 2008 removing 1318812 relations and 1095863 ideals in 222949 cliques
Tue May 20 09:48:27 2008 commencing in-memory singleton removal
Tue May 20 09:48:44 2008 begin with 60874410 relations and 54353849 unique ideals
Tue May 20 09:51:13 2008 reduce to 60855353 relations and 53238851 ideals in 7 passes
Tue May 20 09:51:13 2008 max relations containing the same ideal: 20
Tue May 20 09:51:41 2008 relations with 0 large ideals: 269385
Tue May 20 09:51:41 2008 relations with 1 large ideals: 1820386
Tue May 20 09:51:41 2008 relations with 2 large ideals: 7408025
Tue May 20 09:51:41 2008 relations with 3 large ideals: 15851325
Tue May 20 09:51:41 2008 relations with 4 large ideals: 18783821
Tue May 20 09:51:41 2008 relations with 5 large ideals: 12156231
Tue May 20 09:51:41 2008 relations with 6 large ideals: 3848264
Tue May 20 09:51:41 2008 relations with 7+ large ideals: 717916
Tue May 20 09:51:41 2008 commencing 2-way merge
Tue May 20 09:53:46 2008 reduce to 39059430 relation sets and 31442928 unique ideals
Tue May 20 09:53:46 2008 commencing full merge
Tue May 20 10:16:52 2008 memory use: 3189.2 MB
Tue May 20 10:16:53 2008 found 20772723 cycles, need 19723128
Tue May 20 10:17:12 2008 weight of 19723128 cycles is about 1380674817 (70.00/cycle)
Tue May 20 10:17:12 2008 distribution of cycle lengths:
Tue May 20 10:17:12 2008 1 relations: 2610909
Tue May 20 10:17:12 2008 2 relations: 2765176
Tue May 20 10:17:12 2008 3 relations: 2736436
Tue May 20 10:17:12 2008 4 relations: 2402859
Tue May 20 10:17:12 2008 5 relations: 2070671
Tue May 20 10:17:12 2008 6 relations: 1728007
Tue May 20 10:17:12 2008 7 relations: 1445511
Tue May 20 10:17:12 2008 8 relations: 1188129
Tue May 20 10:17:12 2008 9 relations: 959965
Tue May 20 10:17:12 2008 10+ relations: 1815465
Tue May 20 10:17:12 2008 heaviest cycle: 14 relations
Tue May 20 10:17:22 2008 commencing cycle optimization
Tue May 20 10:19:41 2008 start with 94676072 relations
Tue May 20 10:43:47 2008 pruned 1275423 relations
Tue May 20 10:43:51 2008 memory use: 3324.2 MB
Tue May 20 10:43:51 2008 distribution of cycle lengths:
Tue May 20 10:43:51 2008 1 relations: 2610909
Tue May 20 10:43:51 2008 2 relations: 2797683
Tue May 20 10:43:51 2008 3 relations: 2798623
Tue May 20 10:43:51 2008 4 relations: 2432196
Tue May 20 10:43:51 2008 5 relations: 2099538
Tue May 20 10:43:51 2008 6 relations: 1738091
Tue May 20 10:43:51 2008 7 relations: 1450419
Tue May 20 10:43:51 2008 8 relations: 1182172
Tue May 20 10:43:51 2008 9 relations: 948690
Tue May 20 10:43:51 2008 10+ relations: 1664807
Tue May 20 10:43:52 2008 heaviest cycle: 14 relations
Tue May 20 10:46:03 2008
Tue May 20 10:46:03 2008 commencing linear algebra
Tue May 20 10:46:08 2008 read 19723128 cycles
Tue May 20 10:58:18 2008 cycles contain 56293144 unique relations
Tue May 20 11:09:44 2008 read 56293144 relations
Tue May 20 11:14:47 2008 using 32 quadratic characters above 2147483078
Tue May 20 11:29:06 2008 building initial matrix
Tue May 20 12:28:13 2008 memory use: 7026.5 MB
Tue May 20 12:28:35 2008 read 19723128 cycles
Tue May 20 12:29:00 2008 matrix is 19722462 x 19723128 (5955.5 MB) with weight 1805939782 (91.56/col)
Tue May 20 12:29:00 2008 sparse part has weight 1344251694 (68.16/col)
Tue May 20 12:50:48 2008 filtering completed in 3 passes
Tue May 20 12:50:59 2008 matrix is 19636745 x 19636945 (5945.5 MB) with weight 1802264473 (91.78/col)
Tue May 20 12:50:59 2008 sparse part has weight 1342562692 (68.37/col)
Tue May 20 12:55:31 2008 read 19636945 cycles
Tue May 20 12:55:56 2008 matrix is 19636745 x 19636945 (5945.5 MB) with weight 1802264473 (91.78/col)
Tue May 20 12:55:56 2008 sparse part has weight 1342562692 (68.37/col)
Tue May 20 12:55:57 2008 saving the first 48 matrix rows for later
Tue May 20 12:56:19 2008 matrix is 19636697 x 19636945 (5688.0 MB) with weight 1392293731 (70.90/col)
Tue May 20 12:56:20 2008 sparse part has weight 1294716794 (65.93/col)
Tue May 20 12:56:20 2008 matrix includes 64 packed rows
Tue May 20 12:56:20 2008 using block size 65536 for processor cache size 2048 kB
Tue May 20 12:59:38 2008 commencing Lanczos iteration
Tue May 20 12:59:38 2008 memory use: 5602.6 MB

[/CODE]

Greg

Getting that down to 4G will I suspect be quite a lot of work. My guess is that, once you've got a matrix, 10% more relations mean 20% fewer rows in the matrix; you need about 50% fewer rows, so another forty million unique relations is probably where I'd start, but that's an awful lot of sieving for a number that big.

[QUOTE=fivemack;133895]Getting that down to 4G will I suspect be quite a lot of work. My guess is that, once you've got a matrix, 10% more relations mean 20% fewer rows in the matrix; you need about 50% fewer rows, so another forty million unique relations is probably where I'd start, but that's an awful lot of sieving for a number that big.[/QUOTE]

We used both factorbase bounds at 90M (larger than the 70M we've
been using; except that 3,536+ used 80M), then sieved
50M-240M, all on the rational side. We plan on adding 3 independent
20M ranges; 30M-50M and 240M-260M rational and 50M-70M algebraic.
That way we'll see which range produced the most relns that are
non-duplicate with the first range; and use all three to bring the total
down --- suppose we could even add a few more in the most productive
direction, if still needed.

Wow, 19.36M^2; suppose we ought to have expected this, for
difficulty 263.7; above what the c260 12,241- had. We clearly still
have more sieving time than matrix space available; so going larger
may rely upon how over-sieving looks. -Bruce

[QUOTE=bdodson;133903] We clearly still
have more sieving time than matrix space available; so going larger
may rely upon how over-sieving looks. -Bruce[/QUOTE]

That, or we could beg, borrow, or steal someones distributed LA code. :smile:

In my very limited experience, I have not had particular trouble with rational-side relations duplicating algebraic-side relations; after all, to be both an algebraic-side and a rational-side relation requires you to have a really quite special factorisation.

I have quickly become an advocate of running both sides, since small special-Q really are intrinsically more efficient than large special-Q, and for a well-balanced problem (and unless you're sieving a C220 with a quartic, most problems are well-balanced) the yields on both sides are pretty close. On Fibonacci(1079) - a rather ugly sextic with up to four-digit coefficients, since fibonacci numbers have intrinsically rather bigger coefficients than Cunningham numbers, and the symmetric-polynomial trick roughly squares the coefficients - I had algebraic-side yields at q=23e6 corresponding to the rational-side yields at q=17e6. For 2^821-1 the algebraic yield at 7e7 is very comparable to the rational yield at 10e7.

I've just run a few tens of thousands of dimensions on fib1079 using -t1 and -t4 on a quad-core (Q6600, P35 chipset, 8G of cheapest-available DDR2/4200 RAM); the ETA came out as 3154 minutes with -t1 and 1993 minutes with -t4, which is really not very impressive scaling - though obviously 1160 saved minutes are not to be sniffed at.

msieve 1.36
 

Janson,

New calculation Rsa154 is made. Completely with use msieve 1.36. Works.

[QUOTE=miklin;134069]
New calculation Rsa154 is made. Completely with use msieve 1.36. Works.[/QUOTE]
Excellent, thanks.

[QUOTE=bdodson;133847]An update, 3p536 is at 86.9%, 10m257 at 61.8%, 10p257 at
29.7% and 3m547 at 12.5%. Yet another reboot/crash with
8 hrs of idle cpus and another 7-8hrs or more beyond that since
each matrix wrote its last checkpoint. If c. 40-days computing
walltime is somewhere near the c252 matrix runtime, the remaining
13.1% would be 5 days, 6 hours; so maybe May 27.

Supposing the matrix finishes, am I supposed to be able to get
each of four processors to run two independent dependencies?
I'd appreciate having the exact command line to refer to.

Seems like my chances are still good to finish one factorization before
the new quadcore smp server opens to our public users on June 1; and
I'm hoping to have a second one done before the old server is boxed-up
and shipped back on June 15.
-Bruce[/QUOTE]

Very Nice Work!! :smile::bow:

Allow me to suggest that the fact that sieving work is outstripping the
matrix work by a fair margin illustrates a point I tried to make some
time ago: the LA involved in factorization algorithms is still not a well
solved problem. Small scale parallelizations seem to work. However,
we are still unable to obtain a large scale speedup of the LA by throwing
even a moderate number (say 16 to 32) of machines at it. Communication
is still a (relatively) unsolved bottleneck.

[QUOTE=R.D. Silverman;134546]Very Nice Work!! :smile::bow:

Allow me to suggest that the fact that sieving work is outstripping the
matrix work by a fair margin illustrates a point I tried to make some
time ago: the LA involved in factorization algorithms is still not a well
solved problem. Small scale parallelizations seem to work. However,
we are still unable to obtain a large scale speedup of the LA by throwing
even a moderate number (say 16 to 32) of machines at it. Communication
is still a (relatively) unsolved bottleneck.[/QUOTE]Block Wiedemann, as used by the M1061 crowd recently?


Paul

To give some idea of the depth of the block-lanczos unparallelisability pit, frmky is not observing speedups with 2 cores over 1 on his matrix, and I get a factor 1.6 on a fairly small matrix with 4 cores over 1.

Block Wiedemann is non-trivial to implement - the core is a really-really-big GF(2) polynomial GCD, and FFT-based GCD algorithms are big, tetchy, fragile things that have been observed to trouble even jasonp.

I'm sure I've seen a useful paper, but my brain is oozing out of my navel as I read the list of titles like [i]A New Proxy Identity-Based Signcryption Scheme for Partial Delegation of Signing Rights[/i], [i]Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic field[/i] or [i]Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros[/i] on eprint.iacr.org

For SNFS-260 numbers, we're in an interesting portion of the space, where we have reasonable numbers of computers that can hold the whole matrix so don't need to worry about efficient matrix multiply across clusters - I expect there to be more people with two 8GB machines than eight 2GB machines, though I'm not lucky enough to count myself in either category at the moment.

Wiedemann may well be the right answer there, though the memory usage of the Berlekamp-Massey step may be nasty (it's O((m+n)^2/n d, where d is the number of matrix rows, and for M1039 m=512, n=256 it took 128GB which means O is about one byte. n is the number of computers participating times the width of the vectors multiplied by each computer, and m is a parameter of your choice subject to the fact that the number of matvecs required is d/m + d/n (so you want it to be big) and the Berlekamp-Massey time complexity has an (m+n)^3/n factor (so you want it to be small).

With two computers participating, it seems to make sense to have 256-bit-wide vectors on each computer, m=256, and you need 16GB for the memory-intensive stage. I don't have the shadow of anything resembling a clue of how long it would take to run.