mersenneforum.org 3- table
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-17, 09:27 #34 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Did 10240 curves at B1=110M on 3,589- and 10239 curves on 3,523-. I simply do ~10000 on each 3,n- composite, except those that are ready for sieving already. Alex
 2007-12-24, 23:12 #35 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts I'd like to reserve 3,533- for NFS. Alex
 2008-01-03, 20:59 #36 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts What would you say, is 3,527- c160 difficulty 252 an SNFS or GNFS number? What about 3,565- c160 difficulty 215.6 but with a quartic? Alex
2008-01-04, 00:50   #37
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by akruppa What would you say, is 3,527- c160 difficulty 252 an SNFS or GNFS number? What about 3,565- c160 difficulty 215.6 but with a quartic? Alex

GNFS for both.

 2008-01-20, 09:33 #38 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 3,533- Code: Wed Dec 26 13:23:54 2007 Msieve v. 1.32 Wed Dec 26 13:23:54 2007 random seeds: 7e744583 2bd2b85b Wed Dec 26 13:23:54 2007 factoring 1190326221869543821572917966325809978702570962145981006882469554080512479946881241200223254954445291863827088943611095445819657747251273129779679878747749184725240225632855343166865881812906551356242819 (202 digits) Wed Dec 26 13:23:56 2007 no P-1/P+1/ECM available, skipping Wed Dec 26 13:23:56 2007 commencing number field sieve (201-digit input) Wed Dec 26 13:23:56 2007 R0: 1330279464729113309844748891857449678410 Wed Dec 26 13:23:56 2007 R1: -36472996377170786403 Wed Dec 26 13:23:56 2007 A0: -1 Wed Dec 26 13:23:56 2007 A1: 3 Wed Dec 26 13:23:56 2007 A2: 6 Wed Dec 26 13:23:56 2007 A3: -4 Wed Dec 26 13:23:56 2007 A4: -5 Wed Dec 26 13:23:56 2007 A5: 1 Wed Dec 26 13:23:56 2007 A6: 1 Wed Dec 26 13:23:56 2007 size score = 4.295996e-11, Murphy alpha = 3.082719, combined = 1.780522e-11 Wed Dec 26 13:27:59 2007 restarting with 97518313 relations Wed Dec 26 13:27:59 2007 Wed Dec 26 13:27:59 2007 commencing relation filtering Wed Dec 26 13:27:59 2007 commencing duplicate removal, pass 1 Wed Dec 26 13:30:59 2007 error -11 reading relation 23489158 Wed Dec 26 13:33:00 2007 error -11 reading relation 39352198 Wed Dec 26 13:33:30 2007 error -6 reading relation 43330678 Wed Dec 26 13:34:30 2007 error -6 reading relation 51077186 Wed Dec 26 13:35:00 2007 error -11 reading relation 55025904 Wed Dec 26 13:36:28 2007 error -6 reading relation 66508705 Wed Dec 26 13:37:10 2007 error -6 reading relation 71907697 Wed Dec 26 13:37:48 2007 error -6 reading relation 76943586 Wed Dec 26 13:38:31 2007 error -11 reading relation 82437229 Wed Dec 26 13:39:04 2007 error -11 reading relation 86711100 Wed Dec 26 13:39:05 2007 error -11 reading relation 86922471 Wed Dec 26 13:39:39 2007 error -11 reading relation 91225739 Wed Dec 26 13:40:10 2007 error -11 reading relation 95314957 Wed Dec 26 13:40:18 2007 error -11 reading relation 96294221 Wed Dec 26 13:40:30 2007 found 26802289 hash collisions in 97518299 relations Wed Dec 26 13:40:30 2007 commencing duplicate removal, pass 2 Wed Dec 26 13:45:26 2007 found 15446223 duplicates and 82072076 unique relations Wed Dec 26 13:45:26 2007 memory use: 504.8 MB Wed Dec 26 13:46:04 2007 ignoring smallest 3692540 rational and 3692185 algebraic ideals Wed Dec 26 13:46:04 2007 filtering ideals above 62338726 Wed Dec 26 13:46:04 2007 need 12554032 more relations than ideals Wed Dec 26 13:46:04 2007 commencing singleton removal, pass 1 Wed Dec 26 13:57:32 2007 relations with 0 large ideals: 969350 Wed Dec 26 13:57:32 2007 relations with 1 large ideals: 6057841 Wed Dec 26 13:57:32 2007 relations with 2 large ideals: 17772352 Wed Dec 26 13:57:32 2007 relations with 3 large ideals: 27370042 Wed Dec 26 13:57:32 2007 relations with 4 large ideals: 22187240 Wed Dec 26 13:57:32 2007 relations with 5 large ideals: 7715251 Wed Dec 26 13:57:32 2007 relations with 6 large ideals: 0 Wed Dec 26 13:57:32 2007 relations with 7+ large ideals: 0 Wed Dec 26 13:57:32 2007 82072076 relations and about 59667367 large ideals Wed Dec 26 13:57:32 2007 commencing singleton removal, pass 2 Wed Dec 26 14:09:13 2007 found 16408833 singletons Wed Dec 26 14:09:13 2007 current dataset: 65663243 relations and about 41828732 large ideals Wed Dec 26 14:09:13 2007 commencing singleton removal, pass 3 Wed Dec 26 14:18:40 2007 relations with 0 large ideals: 969350 Wed Dec 26 14:18:40 2007 relations with 1 large ideals: 5656217 Wed Dec 26 14:18:40 2007 relations with 2 large ideals: 15416786 Wed Dec 26 14:18:40 2007 relations with 3 large ideals: 21972200 Wed Dec 26 14:18:40 2007 relations with 4 large ideals: 16413003 Wed Dec 26 14:18:40 2007 relations with 5 large ideals: 5235687 Wed Dec 26 14:18:40 2007 relations with 6 large ideals: 0 Wed Dec 26 14:18:40 2007 relations with 7+ large ideals: 0 Wed Dec 26 14:18:40 2007 65663243 relations and about 52741943 large ideals Wed Dec 26 14:18:40 2007 commencing singleton removal, pass 4 Wed Dec 26 14:28:17 2007 found 13294930 singletons Wed Dec 26 14:28:17 2007 current dataset: 52368313 relations and about 38275780 large ideals Wed Dec 26 14:28:17 2007 commencing singleton removal, pass 5 Wed Dec 26 14:38:11 2007 found 3403473 singletons Wed Dec 26 14:38:11 2007 current dataset: 48964840 relations and about 34780175 large ideals Wed Dec 26 14:38:11 2007 commencing singleton removal, pass 6 Wed Dec 26 14:49:50 2007 found 852512 singletons Wed Dec 26 14:49:50 2007 current dataset: 48112328 relations and about 33921533 large ideals Wed Dec 26 14:49:50 2007 commencing singleton removal, pass 7 Wed Dec 26 14:58:55 2007 found 208366 singletons Wed Dec 26 14:58:55 2007 current dataset: 47903962 relations and about 33712770 large ideals Wed Dec 26 14:58:55 2007 commencing singleton removal, final pass Wed Dec 26 15:09:33 2007 memory use: 1647.4 MB Wed Dec 26 15:09:33 2007 commencing in-memory singleton removal Wed Dec 26 15:09:39 2007 begin with 47903962 relations and 38813836 unique ideals Wed Dec 26 15:11:17 2007 reduce to 40403351 relations and 31099438 ideals in 17 passes Wed Dec 26 15:11:17 2007 max relations containing the same ideal: 34 Wed Dec 26 15:11:22 2007 dataset has 26.0% excess relations Wed Dec 26 15:11:56 2007 ignoring smallest 3344241 rational and 3343753 algebraic ideals Wed Dec 26 15:11:56 2007 filtering ideals above 56104853 Wed Dec 26 15:11:56 2007 need 8373521 more relations than ideals Wed Dec 26 15:11:56 2007 commencing singleton removal, final pass Wed Dec 26 15:23:04 2007 memory use: 1639.4 MB Wed Dec 26 15:23:04 2007 commencing in-memory singleton removal Wed Dec 26 15:23:10 2007 begin with 47903962 relations and 39510132 unique ideals Wed Dec 26 15:24:51 2007 reduce to 40389102 relations and 31780941 ideals in 17 passes Wed Dec 26 15:24:51 2007 max relations containing the same ideal: 34 Wed Dec 26 15:25:23 2007 removing 1494545 relations and 1377225 ideals in 117320 cliques Wed Dec 26 15:25:24 2007 commencing in-memory singleton removal Wed Dec 26 15:25:29 2007 begin with 38894557 relations and 31780941 unique ideals Wed Dec 26 15:26:11 2007 reduce to 38859831 relations and 30368839 ideals in 8 passes Wed Dec 26 15:26:11 2007 max relations containing the same ideal: 33 Wed Dec 26 15:26:40 2007 removing 1089635 relations and 972315 ideals in 117320 cliques Wed Dec 26 15:26:42 2007 commencing in-memory singleton removal Wed Dec 26 15:26:46 2007 begin with 37770196 relations and 30368839 unique ideals Wed Dec 26 15:27:27 2007 reduce to 37750521 relations and 29376795 ideals in 8 passes Wed Dec 26 15:27:27 2007 max relations containing the same ideal: 33 Wed Dec 26 15:27:55 2007 removing 3350 relations and 3146 ideals in 204 cliques Wed Dec 26 15:27:56 2007 commencing in-memory singleton removal Wed Dec 26 15:28:00 2007 begin with 37747171 relations and 29376795 unique ideals Wed Dec 26 15:28:05 2007 reduce to 37747171 relations and 29373649 ideals in 1 passes Wed Dec 26 15:28:05 2007 max relations containing the same ideal: 33 Wed Dec 26 15:28:14 2007 dataset has 13.4% excess relations Wed Dec 26 15:28:45 2007 ignoring smallest 2993835 rational and 2993431 algebraic ideals Wed Dec 26 15:28:45 2007 filtering ideals above 49870980 Wed Dec 26 15:28:45 2007 need 7975503 more relations than ideals Wed Dec 26 15:28:45 2007 commencing singleton removal, final pass Wed Dec 26 15:36:30 2007 memory use: 1307.2 MB Wed Dec 26 15:36:30 2007 commencing in-memory singleton removal Wed Dec 26 15:36:35 2007 begin with 37747171 relations and 30073665 unique ideals Wed Dec 26 15:37:11 2007 reduce to 37737579 relations and 30064073 ideals in 7 passes Wed Dec 26 15:37:11 2007 max relations containing the same ideal: 34 Wed Dec 26 15:37:15 2007 dataset has 3.9% excess relations Wed Dec 26 15:37:20 2007 relations with 0 large ideals: 498253 Wed Dec 26 15:37:20 2007 relations with 1 large ideals: 2882463 Wed Dec 26 15:37:20 2007 relations with 2 large ideals: 8349764 Wed Dec 26 15:37:20 2007 relations with 3 large ideals: 12643079 Wed Dec 26 15:37:20 2007 relations with 4 large ideals: 9927326 Wed Dec 26 15:37:20 2007 relations with 5 large ideals: 3428953 Wed Dec 26 15:37:20 2007 relations with 6 large ideals: 7733 Wed Dec 26 15:37:20 2007 relations with 7+ large ideals: 8 Wed Dec 26 15:37:20 2007 commencing 2-way merge Wed Dec 26 15:38:00 2007 reduce to 23599193 relation sets and 15925687 unique ideals Wed Dec 26 15:38:00 2007 commencing full merge Wed Dec 26 15:45:27 2007 found 11879540 cycles, need 10239887 Wed Dec 26 15:45:36 2007 weight of 10239887 cycles is about 665758135 (65.02/cycle) Wed Dec 26 15:45:36 2007 distribution of cycle lengths: Wed Dec 26 15:45:36 2007 1 relations: 1545245 Wed Dec 26 15:45:36 2007 2 relations: 1411653 Wed Dec 26 15:45:36 2007 3 relations: 1373060 Wed Dec 26 15:45:36 2007 4 relations: 1196897 Wed Dec 26 15:45:36 2007 5 relations: 1044265 Wed Dec 26 15:45:36 2007 6 relations: 878262 Wed Dec 26 15:45:36 2007 7 relations: 741534 Wed Dec 26 15:45:36 2007 8 relations: 614041 Wed Dec 26 15:45:36 2007 9 relations: 516853 Wed Dec 26 15:45:36 2007 10+ relations: 918077 Wed Dec 26 15:45:36 2007 heaviest cycle: 13 relations Wed Dec 26 15:45:38 2007 commencing cycle optimization Wed Dec 26 15:46:06 2007 start with 48343832 relations Wed Dec 26 15:48:03 2007 pruned 894931 relations Wed Dec 26 15:48:03 2007 distribution of cycle lengths: Wed Dec 26 15:48:03 2007 1 relations: 1545245 Wed Dec 26 15:48:03 2007 2 relations: 1437173 Wed Dec 26 15:48:03 2007 3 relations: 1416723 Wed Dec 26 15:48:03 2007 4 relations: 1217414 Wed Dec 26 15:48:03 2007 5 relations: 1065472 Wed Dec 26 15:48:03 2007 6 relations: 886793 Wed Dec 26 15:48:03 2007 7 relations: 746261 Wed Dec 26 15:48:03 2007 8 relations: 610710 Wed Dec 26 15:48:03 2007 9 relations: 507201 Wed Dec 26 15:48:03 2007 10+ relations: 806895 Wed Dec 26 15:48:03 2007 heaviest cycle: 13 relations Wed Dec 26 15:48:38 2007 Wed Dec 26 15:48:38 2007 commencing linear algebra Wed Dec 26 15:48:48 2007 read 10239887 cycles Wed Dec 26 15:50:27 2007 cycles contain 28618783 unique relations Wed Dec 26 15:54:48 2007 read 28618783 relations Wed Dec 26 15:56:17 2007 using 32 quadratic characters above 1073741372 Wed Dec 26 16:18:00 2007 read 10239887 cycles Wed Dec 26 16:18:10 2007 matrix is 10219468 x 10239887 with weight 876288057 (avg 85.58/col) Wed Dec 26 16:28:25 2007 filtering completed in 3 passes Wed Dec 26 16:28:28 2007 matrix is 10048690 x 10048879 with weight 860420525 (avg 85.62/col) Wed Dec 26 16:30:44 2007 read 10048879 cycles Wed Dec 26 16:30:54 2007 matrix is 10048690 x 10048879 with weight 860420525 (avg 85.62/col) Wed Dec 26 16:30:55 2007 saving the first 48 matrix rows for later Wed Dec 26 16:31:03 2007 matrix is 10048642 x 10048879 with weight 656121657 (avg 65.29/col) Wed Dec 26 16:31:03 2007 matrix includes 64 packed rows Wed Dec 26 16:31:03 2007 using block size 43690 for processor cache size 1024 kB Wed Dec 26 16:32:13 2007 commencing Lanczos iteration (2 threads) Sat Jan 19 17:48:26 2008 lanczos halted after 158909 iterations (dim = 10048626) Sat Jan 19 17:48:58 2008 recovered 39 nontrivial dependencies Sat Jan 19 17:48:59 2008 Sat Jan 19 17:48:59 2008 commencing square root phase Sat Jan 19 17:48:59 2008 reading relations for dependency 1 Sat Jan 19 17:49:04 2008 read 5021608 cycles Sat Jan 19 17:49:36 2008 cycles contain 16903515 unique relations Sat Jan 19 17:53:47 2008 read 16903515 relations Sat Jan 19 17:58:41 2008 multiplying 23309294 relations Sat Jan 19 20:07:53 2008 multiply complete, coefficients have about 576.55 million bits Sat Jan 19 20:08:24 2008 initial square root is modulo 148817 Sat Jan 19 22:56:52 2008 reading relations for dependency 2 Sat Jan 19 22:57:08 2008 read 5024236 cycles Sat Jan 19 22:57:42 2008 cycles contain 16911873 unique relations Sat Jan 19 23:01:51 2008 read 16911873 relations Sat Jan 19 23:06:16 2008 multiplying 23333068 relations Sun Jan 20 01:15:05 2008 multiply complete, coefficients have about 577.15 million bits Sun Jan 20 01:15:36 2008 initial square root is modulo 150659 Sun Jan 20 04:01:17 2008 prp63 factor: 150998319124240638554051708078408319882230731449000713669057713 Sun Jan 20 04:01:17 2008 prp139 factor: 7883042862815906861504265211756982516171688170555130221678853379827026522092040013662664709093256898291428386732137962884501006558180661363 Sun Jan 20 04:01:17 2008 elapsed time 590:37:23 Sieved with Franke/Kleinjung lattice siever, let msieve do everything else. Doing the post-processing with msieve is very convenient, once you got the file formats right it's a fire-and-forget job. Alex
2008-01-20, 15:04   #39
jasonp
Tribal Bullet

Oct 2004

3,527 Posts

Quote:
 Originally Posted by akruppa Sieved with Franke/Kleinjung lattice siever, let msieve do everything else. Doing the post-processing with msieve is very convenient, once you got the file formats right it's a fire-and-forget job.
24.5 days for the postprocessing but 2.5 days for the sieving? And I thought my code was fast

I'm going to regret asking this, but is it time to consider adding parallel code using MPI or OpenMP to the linear algebra? I have no way of testing it locally, and I think only Alex, Greg and Tom have the resources to run cluster-scale linear algebra, so this may be moot.

Last fiddled with by jasonp on 2008-01-20 at 15:07

 2008-01-20, 16:58 #40 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 2.5 days of sieving on 200 or so cpus, and 24.5 days postprocessing on 2 cpus, so I think your code is holding up pretty well! For the linear algebra, I think having good multi-threading for multi-cpu/multi-core machines will be ok for a quite while. I imagine distributed BL or BW will be a lot of work to write, and few people will be able to get a large chunk on continuous time on a cluster to solve a large matrix - I know I won't, at least not easily. I don't mind letting a single box crunch away for a couple of weeks or a few months at worst. I mean, we don't have a deadline to meet with these factorizations or anything... If you'd like to play with distributed matrix solving code, by all means go ahead! But I think at this time there's no dire need to have it for Cunningham factorizations. Alex Last fiddled with by akruppa on 2008-01-20 at 17:47 Reason: In fact, I don't know what the exact sieving time and number of cores was. Maybe ~100 cpu days?
2008-01-20, 18:13   #41
xilman
Bamboozled!

May 2003
Down not across

22·3·7·112 Posts

Quote:
 Originally Posted by akruppa For the linear algebra, I think having good multi-threading for multi-cpu/multi-core machines will be ok for a quite while. I imagine distributed BL or BW will be a lot of work to write, and few people will be able to get a large chunk on continuous time on a cluster to solve a large matrix - I know I won't, at least not easily. I don't mind letting a single box crunch away for a couple of weeks or a few months at worst. I mean, we don't have a deadline to meet with these factorizations or anything... If you'd like to play with distributed matrix solving code, by all means go ahead! But I think at this time there's no dire need to have it for Cunningham factorizations. Alex
FWIW, the mpich distribution of MPI uses threads if more than one MPI-enabled process is running on the same machine. So, for instance, a dual quadcore machine can run 8 MPI programs on the same box without any network traffic. Actually, it will run more than 8 processes but two or more will be scheduled on the same core. Strangely enough, I have idle-time access to just such a machine though I have not yet used it for linear algebra. It's running P-1 with B1=1e9 on the generalized Cullen & Woodall numbers right now. Nothing too impressive has appeared yet --- the best is a P46.

But I digress --- back to the point: a case could be made that it is worth wrting MPI-enabled code even if a cluster isn't available right now. It will run multi-threaded at a reasonable speed on a single machine and it will be ready at a moment's notice if a cluster is available.

Paul

2008-01-20, 18:34   #42
ET_
Banned

"Luigi"
Aug 2002
Team Italia

112268 Posts

Quote:
 Originally Posted by xilman But I digress --- back to the point: a case could be made that it is worth wrting MPI-enabled code even if a cluster isn't available right now. It will run multi-threaded at a reasonable speed on a single machine and it will be ready at a moment's notice if a cluster is available. Paul
Would you mind pointing me to tests explaining in-deep use of parallel resources to write numerical analysis code? All I got is the following:

Kenneth A. Berman & Jerome L. Paul, "Algorithms: Sequential, Parallel and Distributed" (Thomson Course technology).

Donald Knuth: "TAOCP" & "Concrete Mathematics".

MPI : The complete reference (from http://www.netlib.org/utk/papers/mpi-book/mpi-book.html)

MPI : A message-passing standard architecture (from http://www.mpi-forum.org/docs/mpi-11...pi-report.html)

I know I could check Amazon as well, but if I had a pointer in the right direction from someone who has the right knowledge, I would spare some time in choosing the right one...

Luigi

2008-01-20, 22:39   #43
xilman
Bamboozled!

May 2003
Down not across

22×3×7×112 Posts

Quote:
 Originally Posted by ET_ Would you mind pointing me to tests explaining in-deep use of parallel resources to write numerical analysis code? ... I know I could check Amazon as well, but if I had a pointer in the right direction from someone who has the right knowledge, I would spare some time in choosing the right one...
To be honest, I can't help much. I don't have very much experience in the field myself.

My guess is that you may be able to pick up pointers if you investigate the HPC (High Performance Computing) area, though be prepared to come across a fair amount of Fortran...

On a more theoretical level, find out more about Tony Hoare and his research groups (that's CAR Hoare to those who don't know him --- Tony and I worked together at MS research and our paths had crossed at Oxford before that, but I digress) and "Communication Sequential Processes", or CSP.

If any more books or resources come to mind I'll post more. It's possible that Ernst may be able to help too.

Paul

 2008-03-09, 20:08 #44 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts I'll do 3,553- c163. Alex

 Similar Threads Thread Thread Starter Forum Replies Last Post garo Cunningham Tables 85 2020-04-15 21:12 garo Cunningham Tables 82 2020-03-15 21:47 garo Cunningham Tables 99 2020-01-10 06:29 garo Cunningham Tables 79 2020-01-01 15:26 garo Cunningham Tables 41 2016-08-04 04:24

All times are UTC. The time now is 11:53.

Fri Aug 7 11:53:23 UTC 2020 up 21 days, 7:40, 1 user, load averages: 2.90, 2.68, 2.51