Extreme oversieving and msieve

jbristow · 2008-01-01, 23:02

I threw a bit too much at this overnight run on a tiny number, but I thought it might be interesting to share the log file. The first run ended when it was unable to allocate sufficient memory at the last step. I then reran it with half the relations and it finished fine.

Code:

Tue Jan 01 13:57:22 2008  Msieve v. 1.32
Tue Jan 01 13:57:22 2008  random seeds: 1b50f4a4 44f7dd4a
Tue Jan 01 13:57:22 2008  factoring 54814708436245992442100810834915713343640736362611433416566101102748762581073923891414781395443838716086492479426441511 (119 digits)
Tue Jan 01 13:57:23 2008  searching for 15-digit factors
Tue Jan 01 13:57:24 2008  commencing number field sieve (119-digit input)
Tue Jan 01 13:57:24 2008  R0: -44567640326363195900190045974568007
Tue Jan 01 13:57:24 2008  R1:  45474735088646411895751953125
Tue Jan 01 13:57:24 2008  A0:  1
Tue Jan 01 13:57:24 2008  A1:  1
Tue Jan 01 13:57:24 2008  A2:  1
Tue Jan 01 13:57:24 2008  A3:  1
Tue Jan 01 13:57:24 2008  A4:  1
Tue Jan 01 13:57:24 2008  size score = 6.994838e-014, Murphy alpha = 1.730510, combined = 3.500720e-014
Tue Jan 01 13:57:38 2008  restarting with 17704493 relations
Tue Jan 01 13:57:38 2008  generating factor base
Tue Jan 01 13:57:40 2008  factor base complete:
Tue Jan 01 13:57:40 2008  230209 rational roots (max prime = 3199997)
Tue Jan 01 13:57:40 2008  230189 algebraic roots (max prime = 3199991)
Tue Jan 01 13:57:40 2008  added 57547 free relations
Tue Jan 01 13:57:40 2008  
Tue Jan 01 13:57:40 2008  commencing relation filtering
Tue Jan 01 13:57:40 2008  commencing duplicate removal, pass 1
Tue Jan 01 13:59:32 2008  found 1284979 hash collisions in 17762040 relations
Tue Jan 01 13:59:32 2008  commencing duplicate removal, pass 2
Tue Jan 01 14:00:00 2008  found 758195 duplicates and 17003845 unique relations
Tue Jan 01 14:00:00 2008  memory use: 65.3 MB
Tue Jan 01 14:00:01 2008  ignoring smallest 258354 rational and 258161 algebraic ideals
Tue Jan 01 14:00:01 2008  filtering ideals above 3623814
Tue Jan 01 14:00:01 2008  need 878075 more relations than ideals
Tue Jan 01 14:00:01 2008  commencing singleton removal, pass 1
Tue Jan 01 14:01:55 2008  relations with 0 large ideals: 164947
Tue Jan 01 14:01:55 2008  relations with 1 large ideals: 1010930
Tue Jan 01 14:01:55 2008  relations with 2 large ideals: 3673612
Tue Jan 01 14:01:55 2008  relations with 3 large ideals: 6319266
Tue Jan 01 14:01:55 2008  relations with 4 large ideals: 4680516
Tue Jan 01 14:01:55 2008  relations with 5 large ideals: 1154574
Tue Jan 01 14:01:55 2008  relations with 6 large ideals: 0
Tue Jan 01 14:01:55 2008  relations with 7+ large ideals: 0
Tue Jan 01 14:01:55 2008  17003845 relations and about 6754380 large ideals
Tue Jan 01 14:01:55 2008  commencing singleton removal, pass 2
Tue Jan 01 14:03:51 2008  found 930630 singletons
Tue Jan 01 14:03:51 2008  current dataset: 16073215 relations and about 5809096 large ideals
Tue Jan 01 14:03:51 2008  commencing singleton removal, pass 3
Tue Jan 01 14:05:41 2008  found 39934 singletons
Tue Jan 01 14:05:41 2008  current dataset: 16033281 relations and about 5769129 large ideals
Tue Jan 01 14:05:41 2008  commencing singleton removal, final pass
Tue Jan 01 14:07:41 2008  memory use: 548.8 MB
Tue Jan 01 14:07:41 2008  commencing in-memory singleton removal
Tue Jan 01 14:07:42 2008  begin with 16033281 relations and 5940281 unique ideals
Tue Jan 01 14:07:50 2008  reduce to 15977590 relations and 5884534 ideals in 5 passes
Tue Jan 01 14:07:50 2008  max relations containing the same ideal: 195
Tue Jan 01 14:07:55 2008  removing 904548 relations and 504548 ideals in 400000 cliques
Tue Jan 01 14:07:55 2008  commencing in-memory singleton removal
Tue Jan 01 14:07:56 2008  begin with 15073042 relations and 5884534 unique ideals
Tue Jan 01 14:08:01 2008  reduce to 15046550 relations and 5352591 ideals in 3 passes
Tue Jan 01 14:08:01 2008  max relations containing the same ideal: 187
Tue Jan 01 14:08:05 2008  removing 807852 relations and 407852 ideals in 400000 cliques
Tue Jan 01 14:08:06 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:07 2008  begin with 14238698 relations and 5352591 unique ideals
Tue Jan 01 14:08:11 2008  reduce to 14233916 relations and 4939874 ideals in 3 passes
Tue Jan 01 14:08:11 2008  max relations containing the same ideal: 175
Tue Jan 01 14:08:15 2008  removing 801285 relations and 401285 ideals in 400000 cliques
Tue Jan 01 14:08:15 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:16 2008  begin with 13432631 relations and 4939874 unique ideals
Tue Jan 01 14:08:18 2008  reduce to 13432127 relations and 4538081 ideals in 2 passes
Tue Jan 01 14:08:18 2008  max relations containing the same ideal: 165
Tue Jan 01 14:08:22 2008  removing 470513 relations and 235340 ideals in 235173 cliques
Tue Jan 01 14:08:22 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:23 2008  begin with 12961614 relations and 4538081 unique ideals
Tue Jan 01 14:08:25 2008  reduce to 12961575 relations and 4302702 ideals in 2 passes
Tue Jan 01 14:08:25 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:28 2008  removing 25347 relations and 12682 ideals in 12665 cliques
Tue Jan 01 14:08:28 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:29 2008  begin with 12936228 relations and 4302702 unique ideals
Tue Jan 01 14:08:31 2008  reduce to 12936221 relations and 4290013 ideals in 2 passes
Tue Jan 01 14:08:31 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:34 2008  removing 8682 relations and 4342 ideals in 4340 cliques
Tue Jan 01 14:08:35 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:36 2008  begin with 12927539 relations and 4290013 unique ideals
Tue Jan 01 14:08:37 2008  reduce to 12927539 relations and 4285671 ideals in 1 passes
Tue Jan 01 14:08:37 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:40 2008  removing 2939 relations and 1470 ideals in 1469 cliques
Tue Jan 01 14:08:40 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:41 2008  begin with 12924600 relations and 4285671 unique ideals
Tue Jan 01 14:08:42 2008  reduce to 12924600 relations and 4284201 ideals in 1 passes
Tue Jan 01 14:08:42 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:45 2008  removing 1032 relations and 516 ideals in 516 cliques
Tue Jan 01 14:08:45 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:46 2008  begin with 12923568 relations and 4284201 unique ideals
Tue Jan 01 14:08:47 2008  reduce to 12923568 relations and 4283685 ideals in 1 passes
Tue Jan 01 14:08:47 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:50 2008  removing 334 relations and 167 ideals in 167 cliques
Tue Jan 01 14:08:50 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:51 2008  begin with 12923234 relations and 4283685 unique ideals
Tue Jan 01 14:08:52 2008  reduce to 12923234 relations and 4283518 ideals in 1 passes
Tue Jan 01 14:08:52 2008  max relations containing the same ideal: 162
Tue Jan 01 14:08:55 2008  removing 132 relations and 66 ideals in 66 cliques
Tue Jan 01 14:08:55 2008  commencing in-memory singleton removal
Tue Jan 01 14:08:56 2008  begin with 12923102 relations and 4283518 unique ideals
Tue Jan 01 14:08:57 2008  reduce to 12923102 relations and 4283452 ideals in 1 passes
Tue Jan 01 14:08:57 2008  max relations containing the same ideal: 162
Tue Jan 01 14:09:00 2008  removing 58 relations and 29 ideals in 29 cliques
Tue Jan 01 14:09:01 2008  commencing in-memory singleton removal
Tue Jan 01 14:09:02 2008  begin with 12923044 relations and 4283452 unique ideals
Tue Jan 01 14:09:03 2008  reduce to 12923044 relations and 4283423 ideals in 1 passes
Tue Jan 01 14:09:03 2008  max relations containing the same ideal: 162
Tue Jan 01 14:09:06 2008  removing 20 relations and 10 ideals in 10 cliques
Tue Jan 01 14:09:06 2008  commencing in-memory singleton removal
Tue Jan 01 14:09:07 2008  begin with 12923024 relations and 4283423 unique ideals
Tue Jan 01 14:09:08 2008  reduce to 12923024 relations and 4283413 ideals in 1 passes
Tue Jan 01 14:09:08 2008  max relations containing the same ideal: 162
Tue Jan 01 14:09:11 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:09:14 2008  dataset has 1572.7% excess relations
Tue Jan 01 14:09:14 2008  ignoring smallest 234347 rational and 234301 algebraic ideals
Tue Jan 01 14:09:14 2008  filtering ideals above 3261432
Tue Jan 01 14:09:15 2008  need 7775649 more relations than ideals
Tue Jan 01 14:09:15 2008  commencing singleton removal, final pass
Tue Jan 01 14:10:53 2008  memory use: 369.2 MB
Tue Jan 01 14:10:53 2008  commencing in-memory singleton removal
Tue Jan 01 14:10:54 2008  begin with 12923024 relations and 4331280 unique ideals
Tue Jan 01 14:10:55 2008  reduce to 12923024 relations and 4331280 ideals in 1 passes
Tue Jan 01 14:10:55 2008  max relations containing the same ideal: 167
Tue Jan 01 14:10:58 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:11:01 2008  dataset has 1563.4% excess relations
Tue Jan 01 14:11:02 2008  ignoring smallest 210039 rational and 209873 algebraic ideals
Tue Jan 01 14:11:02 2008  filtering ideals above 2899051
Tue Jan 01 14:11:02 2008  need 6873395 more relations than ideals
Tue Jan 01 14:11:02 2008  commencing singleton removal, final pass
Tue Jan 01 14:12:42 2008  memory use: 369.2 MB
Tue Jan 01 14:12:42 2008  commencing in-memory singleton removal
Tue Jan 01 14:12:43 2008  begin with 12923024 relations and 4380011 unique ideals
Tue Jan 01 14:12:44 2008  reduce to 12923024 relations and 4380011 ideals in 1 passes
Tue Jan 01 14:12:44 2008  max relations containing the same ideal: 167
Tue Jan 01 14:12:47 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:12:50 2008  dataset has 1554.0% excess relations
Tue Jan 01 14:12:50 2008  ignoring smallest 185570 rational and 185561 algebraic ideals
Tue Jan 01 14:12:50 2008  filtering ideals above 2536669
Tue Jan 01 14:12:50 2008  need 5980109 more relations than ideals
Tue Jan 01 14:12:50 2008  commencing singleton removal, final pass
Tue Jan 01 14:14:30 2008  memory use: 369.2 MB
Tue Jan 01 14:14:31 2008  commencing in-memory singleton removal
Tue Jan 01 14:14:32 2008  begin with 12923024 relations and 4428797 unique ideals
Tue Jan 01 14:14:33 2008  reduce to 12923024 relations and 4428797 ideals in 1 passes
Tue Jan 01 14:14:33 2008  max relations containing the same ideal: 167
Tue Jan 01 14:14:36 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:14:37 2008  dataset has 1544.5% excess relations
Tue Jan 01 14:14:38 2008  ignoring smallest 160930 rational and 160829 algebraic ideals
Tue Jan 01 14:14:38 2008  filtering ideals above 2174288
Tue Jan 01 14:14:38 2008  need 5096536 more relations than ideals
Tue Jan 01 14:14:38 2008  commencing singleton removal, final pass
Tue Jan 01 14:16:19 2008  memory use: 369.2 MB
Tue Jan 01 14:16:19 2008  commencing in-memory singleton removal
Tue Jan 01 14:16:20 2008  begin with 12923024 relations and 4478169 unique ideals
Tue Jan 01 14:16:21 2008  reduce to 12923024 relations and 4478169 ideals in 1 passes
Tue Jan 01 14:16:21 2008  max relations containing the same ideal: 167
Tue Jan 01 14:16:25 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:16:28 2008  dataset has 1535.0% excess relations
Tue Jan 01 14:16:28 2008  ignoring smallest 135906 rational and 135745 algebraic ideals
Tue Jan 01 14:16:28 2008  filtering ideals above 1811906
Tue Jan 01 14:16:28 2008  need 4222427 more relations than ideals
Tue Jan 01 14:16:28 2008  commencing singleton removal, final pass
Tue Jan 01 14:18:10 2008  memory use: 369.2 MB
Tue Jan 01 14:18:10 2008  commencing in-memory singleton removal
Tue Jan 01 14:18:11 2008  begin with 12923024 relations and 4528277 unique ideals
Tue Jan 01 14:18:13 2008  reduce to 12923024 relations and 4528277 ideals in 1 passes
Tue Jan 01 14:18:13 2008  max relations containing the same ideal: 167
Tue Jan 01 14:18:16 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:18:19 2008  dataset has 1525.3% excess relations
Tue Jan 01 14:18:19 2008  ignoring smallest 110592 rational and 110409 algebraic ideals
Tue Jan 01 14:18:19 2008  filtering ideals above 1449525
Tue Jan 01 14:18:19 2008  need 3357898 more relations than ideals
Tue Jan 01 14:18:19 2008  commencing singleton removal, final pass
Tue Jan 01 14:20:03 2008  memory use: 369.2 MB
Tue Jan 01 14:20:03 2008  commencing in-memory singleton removal
Tue Jan 01 14:20:04 2008  begin with 12923024 relations and 4578927 unique ideals
Tue Jan 01 14:20:05 2008  reduce to 12923024 relations and 4578927 ideals in 1 passes
Tue Jan 01 14:20:05 2008  max relations containing the same ideal: 167
Tue Jan 01 14:20:09 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:20:12 2008  dataset has 1515.5% excess relations
Tue Jan 01 14:20:12 2008  ignoring smallest 84784 rational and 84753 algebraic ideals
Tue Jan 01 14:20:12 2008  filtering ideals above 1087144
Tue Jan 01 14:20:12 2008  need 2503229 more relations than ideals
Tue Jan 01 14:20:12 2008  commencing singleton removal, final pass
Tue Jan 01 14:21:57 2008  memory use: 490.2 MB
Tue Jan 01 14:21:57 2008  commencing in-memory singleton removal
Tue Jan 01 14:21:59 2008  begin with 12923024 relations and 4630391 unique ideals
Tue Jan 01 14:22:00 2008  reduce to 12923024 relations and 4630391 ideals in 1 passes
Tue Jan 01 14:22:00 2008  max relations containing the same ideal: 170
Tue Jan 01 14:22:05 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:22:07 2008  dataset has 1505.5% excess relations
Tue Jan 01 14:22:07 2008  ignoring smallest 58400 rational and 58257 algebraic ideals
Tue Jan 01 14:22:07 2008  filtering ideals above 724762
Tue Jan 01 14:22:07 2008  need 1658526 more relations than ideals
Tue Jan 01 14:22:07 2008  commencing singleton removal, final pass
Tue Jan 01 14:23:54 2008  memory use: 490.2 MB
Tue Jan 01 14:23:54 2008  commencing in-memory singleton removal
Tue Jan 01 14:23:56 2008  begin with 12923024 relations and 4683271 unique ideals
Tue Jan 01 14:23:57 2008  reduce to 12923024 relations and 4683271 ideals in 1 passes
Tue Jan 01 14:23:57 2008  max relations containing the same ideal: 222
Tue Jan 01 14:24:02 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:24:03 2008  dataset has 1495.3% excess relations
Tue Jan 01 14:24:03 2008  ignoring smallest 30938 rational and 30889 algebraic ideals
Tue Jan 01 14:24:03 2008  filtering ideals above 362381
Tue Jan 01 14:24:03 2008  need 823975 more relations than ideals
Tue Jan 01 14:24:03 2008  commencing singleton removal, final pass
Tue Jan 01 14:25:54 2008  memory use: 490.2 MB
Tue Jan 01 14:25:54 2008  commencing in-memory singleton removal
Tue Jan 01 14:25:56 2008  begin with 12923024 relations and 4738096 unique ideals
Tue Jan 01 14:25:57 2008  reduce to 12923024 relations and 4738096 ideals in 1 passes
Tue Jan 01 14:25:57 2008  max relations containing the same ideal: 380
Tue Jan 01 14:26:02 2008  removing 0 relations and 0 ideals in 0 cliques
Tue Jan 01 14:26:04 2008  dataset has 1484.6% excess relations
Tue Jan 01 14:26:04 2008  ignoring smallest 0 rational and 0 algebraic ideals
Tue Jan 01 14:26:04 2008  filtering ideals above 0
Tue Jan 01 14:26:04 2008  need 557836 more relations than ideals
Tue Jan 01 14:26:04 2008  commencing singleton removal, final pass

Code:

Tue Jan 01 14:32:22 2008  Msieve v. 1.32
Tue Jan 01 14:32:22 2008  random seeds: 699fd7d0 cbd29e72
Tue Jan 01 14:32:22 2008  factoring 54814708436245992442100810834915713343640736362611433416566101102748762581073923891414781395443838716086492479426441511 (119 digits)
Tue Jan 01 14:32:23 2008  searching for 15-digit factors
Tue Jan 01 14:32:24 2008  commencing number field sieve (119-digit input)
Tue Jan 01 14:32:24 2008  R0: -44567640326363195900190045974568007
Tue Jan 01 14:32:24 2008  R1:  45474735088646411895751953125
Tue Jan 01 14:32:24 2008  A0:  1
Tue Jan 01 14:32:24 2008  A1:  1
Tue Jan 01 14:32:24 2008  A2:  1
Tue Jan 01 14:32:24 2008  A3:  1
Tue Jan 01 14:32:24 2008  A4:  1
Tue Jan 01 14:32:24 2008  size score = 6.994838e-014, Murphy alpha = 1.734084, combined = 3.495718e-014
Tue Jan 01 14:32:38 2008  restarting with 9138162 relations
Tue Jan 01 14:32:39 2008  factor base loaded:
Tue Jan 01 14:32:39 2008  230209 rational ideals (max prime = 3199997)
Tue Jan 01 14:32:39 2008  230189 algebraic ideals (max prime = 3199991)
Tue Jan 01 14:32:39 2008  added 57547 free relations
Tue Jan 01 14:32:40 2008  
Tue Jan 01 14:32:40 2008  commencing relation filtering
Tue Jan 01 14:32:40 2008  commencing duplicate removal, pass 1
Tue Jan 01 14:33:39 2008  found 369212 hash collisions in 9195709 relations
Tue Jan 01 14:33:39 2008  commencing duplicate removal, pass 2
Tue Jan 01 14:33:53 2008  found 221172 duplicates and 8974537 unique relations
Tue Jan 01 14:33:53 2008  memory use: 43.3 MB
Tue Jan 01 14:33:54 2008  ignoring smallest 256021 rational and 255837 algebraic ideals
Tue Jan 01 14:33:54 2008  filtering ideals above 3589414
Tue Jan 01 14:33:54 2008  need 870158 more relations than ideals
Tue Jan 01 14:33:54 2008  commencing singleton removal, pass 1
Tue Jan 01 14:34:54 2008  relations with 0 large ideals: 154589
Tue Jan 01 14:34:54 2008  relations with 1 large ideals: 731915
Tue Jan 01 14:34:54 2008  relations with 2 large ideals: 2241165
Tue Jan 01 14:34:54 2008  relations with 3 large ideals: 3239823
Tue Jan 01 14:34:54 2008  relations with 4 large ideals: 2119514
Tue Jan 01 14:34:54 2008  relations with 5 large ideals: 487531
Tue Jan 01 14:34:54 2008  relations with 6 large ideals: 0
Tue Jan 01 14:34:54 2008  relations with 7+ large ideals: 0
Tue Jan 01 14:34:54 2008  8974537 relations and about 5911834 large ideals
Tue Jan 01 14:34:54 2008  commencing singleton removal, pass 2
Tue Jan 01 14:35:55 2008  found 1736001 singletons
Tue Jan 01 14:35:55 2008  current dataset: 7238536 relations and about 4048813 large ideals
Tue Jan 01 14:35:55 2008  commencing singleton removal, pass 3
Tue Jan 01 14:36:46 2008  found 242108 singletons
Tue Jan 01 14:36:46 2008  current dataset: 6996428 relations and about 3803292 large ideals
Tue Jan 01 14:36:46 2008  commencing singleton removal, final pass
Tue Jan 01 14:37:38 2008  memory use: 221.0 MB
Tue Jan 01 14:37:38 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:38 2008  begin with 6996428 relations and 3921897 unique ideals
Tue Jan 01 14:37:42 2008  reduce to 6850984 relations and 3775636 ideals in 7 passes
Tue Jan 01 14:37:42 2008  max relations containing the same ideal: 158
Tue Jan 01 14:37:45 2008  removing 1175964 relations and 775964 ideals in 400000 cliques
Tue Jan 01 14:37:45 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:45 2008  begin with 5675020 relations and 3775636 unique ideals
Tue Jan 01 14:37:47 2008  reduce to 5580899 relations and 2899437 ideals in 5 passes
Tue Jan 01 14:37:47 2008  max relations containing the same ideal: 133
Tue Jan 01 14:37:49 2008  removing 922886 relations and 522886 ideals in 400000 cliques
Tue Jan 01 14:37:50 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:50 2008  begin with 4658013 relations and 2899437 unique ideals
Tue Jan 01 14:37:52 2008  reduce to 4583360 relations and 2296489 ideals in 6 passes
Tue Jan 01 14:37:52 2008  max relations containing the same ideal: 113
Tue Jan 01 14:37:53 2008  removing 866423 relations and 466423 ideals in 400000 cliques
Tue Jan 01 14:37:53 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:54 2008  begin with 3716937 relations and 2296489 unique ideals
Tue Jan 01 14:37:55 2008  reduce to 3657484 relations and 1766283 ideals in 5 passes
Tue Jan 01 14:37:55 2008  max relations containing the same ideal: 95
Tue Jan 01 14:37:56 2008  removing 839645 relations and 439645 ideals in 400000 cliques
Tue Jan 01 14:37:56 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:56 2008  begin with 2817839 relations and 1766283 unique ideals
Tue Jan 01 14:37:57 2008  reduce to 2777618 relations and 1283946 ideals in 5 passes
Tue Jan 01 14:37:57 2008  max relations containing the same ideal: 76
Tue Jan 01 14:37:58 2008  removing 630779 relations and 328631 ideals in 302148 cliques
Tue Jan 01 14:37:58 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:58 2008  begin with 2146839 relations and 1283946 unique ideals
Tue Jan 01 14:37:59 2008  reduce to 2124742 relations and 932178 ideals in 5 passes
Tue Jan 01 14:37:59 2008  max relations containing the same ideal: 63
Tue Jan 01 14:37:59 2008  removing 291390 relations and 153815 ideals in 137575 cliques
Tue Jan 01 14:37:59 2008  commencing in-memory singleton removal
Tue Jan 01 14:37:59 2008  begin with 1833352 relations and 932178 unique ideals
Tue Jan 01 14:37:59 2008  reduce to 1819811 relations and 764336 ideals in 4 passes
Tue Jan 01 14:37:59 2008  max relations containing the same ideal: 59
Tue Jan 01 14:37:59 2008  removing 215576 relations and 113036 ideals in 102540 cliques
Tue Jan 01 14:38:00 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:00 2008  begin with 1604235 relations and 764336 unique ideals
Tue Jan 01 14:38:00 2008  reduce to 1595524 relations and 642301 ideals in 4 passes
Tue Jan 01 14:38:00 2008  max relations containing the same ideal: 54
Tue Jan 01 14:38:00 2008  removing 163708 relations and 85212 ideals in 78496 cliques
Tue Jan 01 14:38:00 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:00 2008  begin with 1431816 relations and 642301 unique ideals
Tue Jan 01 14:38:00 2008  reduce to 1426383 relations and 551515 ideals in 4 passes
Tue Jan 01 14:38:00 2008  max relations containing the same ideal: 51
Tue Jan 01 14:38:00 2008  removing 12622 relations and 7913 ideals in 4709 cliques
Tue Jan 01 14:38:00 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:00 2008  begin with 1413761 relations and 551515 unique ideals
Tue Jan 01 14:38:00 2008  reduce to 1413622 relations and 543463 ideals in 3 passes
Tue Jan 01 14:38:00 2008  max relations containing the same ideal: 51
Tue Jan 01 14:38:01 2008  dataset has 70.0% excess relations
Tue Jan 01 14:38:01 2008  ignoring smallest 232271 rational and 232249 algebraic ideals
Tue Jan 01 14:38:01 2008  filtering ideals above 3230472
Tue Jan 01 14:38:01 2008  need 783143 more relations than ideals
Tue Jan 01 14:38:01 2008  commencing singleton removal, final pass
Tue Jan 01 14:38:17 2008  memory use: 44.0 MB
Tue Jan 01 14:38:17 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:17 2008  begin with 1413622 relations and 590508 unique ideals
Tue Jan 01 14:38:17 2008  reduce to 1412149 relations and 589035 ideals in 3 passes
Tue Jan 01 14:38:17 2008  max relations containing the same ideal: 51
Tue Jan 01 14:38:18 2008  removing 42630 relations and 22645 ideals in 19985 cliques
Tue Jan 01 14:38:18 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:18 2008  begin with 1369519 relations and 589035 unique ideals
Tue Jan 01 14:38:18 2008  reduce to 1368193 relations and 565046 ideals in 4 passes
Tue Jan 01 14:38:18 2008  max relations containing the same ideal: 48
Tue Jan 01 14:38:18 2008  removing 42729 relations and 22744 ideals in 19985 cliques
Tue Jan 01 14:38:18 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:18 2008  begin with 1325464 relations and 565046 unique ideals
Tue Jan 01 14:38:18 2008  reduce to 1324550 relations and 541385 ideals in 3 passes
Tue Jan 01 14:38:18 2008  max relations containing the same ideal: 47
Tue Jan 01 14:38:18 2008  dataset has 53.0% excess relations
Tue Jan 01 14:38:19 2008  ignoring smallest 208216 rational and 208081 algebraic ideals
Tue Jan 01 14:38:19 2008  filtering ideals above 2871531
Tue Jan 01 14:38:19 2008  need 626531 more relations than ideals
Tue Jan 01 14:38:19 2008  commencing singleton removal, final pass
Tue Jan 01 14:38:34 2008  memory use: 44.0 MB
Tue Jan 01 14:38:34 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:34 2008  begin with 1324550 relations and 589543 unique ideals
Tue Jan 01 14:38:35 2008  reduce to 1321637 relations and 586456 ideals in 5 passes
Tue Jan 01 14:38:35 2008  max relations containing the same ideal: 47
Tue Jan 01 14:38:35 2008  removing 112622 relations and 58297 ideals in 54325 cliques
Tue Jan 01 14:38:35 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:35 2008  begin with 1209015 relations and 586456 unique ideals
Tue Jan 01 14:38:35 2008  reduce to 1205334 relations and 524382 ideals in 3 passes
Tue Jan 01 14:38:35 2008  max relations containing the same ideal: 43
Tue Jan 01 14:38:35 2008  removing 111466 relations and 57141 ideals in 54325 cliques
Tue Jan 01 14:38:35 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:35 2008  begin with 1093868 relations and 524382 unique ideals
Tue Jan 01 14:38:35 2008  reduce to 1091286 relations and 464596 ideals in 4 passes
Tue Jan 01 14:38:35 2008  max relations containing the same ideal: 40
Tue Jan 01 14:38:35 2008  removing 566 relations and 408 ideals in 158 cliques
Tue Jan 01 14:38:35 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:35 2008  begin with 1090720 relations and 464596 unique ideals
Tue Jan 01 14:38:35 2008  reduce to 1090720 relations and 464188 ideals in 1 passes
Tue Jan 01 14:38:35 2008  max relations containing the same ideal: 40
Tue Jan 01 14:38:35 2008  dataset has 22.4% excess relations
Tue Jan 01 14:38:36 2008  ignoring smallest 183930 rational and 183929 algebraic ideals
Tue Jan 01 14:38:36 2008  filtering ideals above 2512589
Tue Jan 01 14:38:36 2008  need 552806 more relations than ideals
Tue Jan 01 14:38:36 2008  commencing singleton removal, final pass
Tue Jan 01 14:38:50 2008  memory use: 35.8 MB
Tue Jan 01 14:38:50 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:50 2008  begin with 1090720 relations and 512553 unique ideals
Tue Jan 01 14:38:50 2008  reduce to 1086977 relations and 508518 ideals in 5 passes
Tue Jan 01 14:38:50 2008  max relations containing the same ideal: 40
Tue Jan 01 14:38:50 2008  removing 29943 relations and 17117 ideals in 12826 cliques
Tue Jan 01 14:38:50 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:50 2008  begin with 1057034 relations and 508518 unique ideals
Tue Jan 01 14:38:50 2008  reduce to 1055964 relations and 490315 ideals in 3 passes
Tue Jan 01 14:38:50 2008  max relations containing the same ideal: 39
Tue Jan 01 14:38:51 2008  removing 28254 relations and 15428 ideals in 12826 cliques
Tue Jan 01 14:38:51 2008  commencing in-memory singleton removal
Tue Jan 01 14:38:51 2008  begin with 1027710 relations and 490315 unique ideals
Tue Jan 01 14:38:51 2008  reduce to 1026961 relations and 474129 ideals in 4 passes
Tue Jan 01 14:38:51 2008  max relations containing the same ideal: 39
Tue Jan 01 14:38:51 2008  dataset has 8.0% excess relations
Tue Jan 01 14:38:51 2008  relations with 0 large ideals: 45983
Tue Jan 01 14:38:51 2008  relations with 1 large ideals: 130372
Tue Jan 01 14:38:51 2008  relations with 2 large ideals: 354253
Tue Jan 01 14:38:51 2008  relations with 3 large ideals: 345380
Tue Jan 01 14:38:51 2008  relations with 4 large ideals: 125614
Tue Jan 01 14:38:51 2008  relations with 5 large ideals: 23344
Tue Jan 01 14:38:51 2008  relations with 6 large ideals: 1930
Tue Jan 01 14:38:51 2008  relations with 7+ large ideals: 85
Tue Jan 01 14:38:51 2008  commencing 2-way merge
Tue Jan 01 14:38:51 2008  reduce to 953821 relation sets and 400989 unique ideals
Tue Jan 01 14:38:51 2008  commencing full merge
Tue Jan 01 14:38:58 2008  found 558824 cycles, need 375059
Tue Jan 01 14:38:58 2008  weight of 375059 cycles is about 17447660 (46.52/cycle)
Tue Jan 01 14:38:58 2008  distribution of cycle lengths:
Tue Jan 01 14:38:58 2008  1 relations: 51707
Tue Jan 01 14:38:58 2008  2 relations: 73030
Tue Jan 01 14:38:58 2008  3 relations: 26797
Tue Jan 01 14:38:58 2008  4 relations: 68228
Tue Jan 01 14:38:58 2008  5 relations: 38765
Tue Jan 01 14:38:58 2008  6 relations: 54546
Tue Jan 01 14:38:58 2008  7 relations: 35165
Tue Jan 01 14:38:58 2008  8 relations: 26337
Tue Jan 01 14:38:58 2008  9 relations: 484
Tue Jan 01 14:38:58 2008  10+ relations: 0
Tue Jan 01 14:38:58 2008  heaviest cycle: 9 relations
Tue Jan 01 14:38:58 2008  matrix not dense enough, retrying
Tue Jan 01 14:38:59 2008  dataset has 8.0% excess relations
Tue Jan 01 14:38:59 2008  ignoring smallest 159502 rational and 159397 algebraic ideals
Tue Jan 01 14:38:59 2008  filtering ideals above 2153648
Tue Jan 01 14:38:59 2008  need 552806 more relations than ideals
Tue Jan 01 14:38:59 2008  commencing singleton removal, final pass
Tue Jan 01 14:39:13 2008  memory use: 35.8 MB
Tue Jan 01 14:39:13 2008  commencing in-memory singleton removal
Tue Jan 01 14:39:13 2008  begin with 1026961 relations and 523043 unique ideals
Tue Jan 01 14:39:13 2008  reduce to 1023946 relations and 519837 ideals in 5 passes
Tue Jan 01 14:39:13 2008  max relations containing the same ideal: 39
Tue Jan 01 14:39:13 2008  dataset has -1.5% excess relations
Tue Jan 01 14:39:13 2008  relations with 0 large ideals: 39850
Tue Jan 01 14:39:13 2008  relations with 1 large ideals: 97823
Tue Jan 01 14:39:13 2008  relations with 2 large ideals: 305740
Tue Jan 01 14:39:13 2008  relations with 3 large ideals: 354830
Tue Jan 01 14:39:13 2008  relations with 4 large ideals: 171790
Tue Jan 01 14:39:13 2008  relations with 5 large ideals: 48171
Tue Jan 01 14:39:13 2008  relations with 6 large ideals: 5324
Tue Jan 01 14:39:13 2008  relations with 7+ large ideals: 418
Tue Jan 01 14:39:13 2008  commencing 2-way merge
Tue Jan 01 14:39:13 2008  reduce to 944428 relation sets and 440319 unique ideals
Tue Jan 01 14:39:13 2008  commencing full merge
Tue Jan 01 14:39:21 2008  found 527009 cycles, need 343599
Tue Jan 01 14:39:21 2008  weight of 343599 cycles is about 15475288 (45.04/cycle)
Tue Jan 01 14:39:21 2008  distribution of cycle lengths:
Tue Jan 01 14:39:21 2008  1 relations: 60195
Tue Jan 01 14:39:21 2008  2 relations: 52479
Tue Jan 01 14:39:21 2008  3 relations: 41533
Tue Jan 01 14:39:21 2008  4 relations: 51498
Tue Jan 01 14:39:21 2008  5 relations: 45242
Tue Jan 01 14:39:21 2008  6 relations: 43081
Tue Jan 01 14:39:21 2008  7 relations: 34599
Tue Jan 01 14:39:21 2008  8 relations: 14771
Tue Jan 01 14:39:21 2008  9 relations: 199
Tue Jan 01 14:39:21 2008  10+ relations: 2
Tue Jan 01 14:39:21 2008  heaviest cycle: 10 relations
Tue Jan 01 14:39:21 2008  matrix not dense enough, retrying
Tue Jan 01 14:39:21 2008  dataset has -1.5% excess relations
Tue Jan 01 14:39:22 2008  ignoring smallest 134696 rational and 134573 algebraic ideals
Tue Jan 01 14:39:22 2008  filtering ideals above 1794706
Tue Jan 01 14:39:22 2008  need 552806 more relations than ideals
Tue Jan 01 14:39:22 2008  commencing singleton removal, final pass
Tue Jan 01 14:39:35 2008  memory use: 35.8 MB
Tue Jan 01 14:39:35 2008  commencing in-memory singleton removal
Tue Jan 01 14:39:35 2008  begin with 1026961 relations and 572649 unique ideals
Tue Jan 01 14:39:36 2008  reduce to 1022067 relations and 567481 ideals in 5 passes
Tue Jan 01 14:39:36 2008  max relations containing the same ideal: 39
Tue Jan 01 14:39:36 2008  dataset has -11.2% excess relations
Tue Jan 01 14:39:36 2008  relations with 0 large ideals: 33643
Tue Jan 01 14:39:36 2008  relations with 1 large ideals: 68490
Tue Jan 01 14:39:36 2008  relations with 2 large ideals: 252057
Tue Jan 01 14:39:36 2008  relations with 3 large ideals: 349994
Tue Jan 01 14:39:36 2008  relations with 4 large ideals: 220128
Tue Jan 01 14:39:36 2008  relations with 5 large ideals: 83309
Tue Jan 01 14:39:36 2008  relations with 6 large ideals: 12988
Tue Jan 01 14:39:36 2008  relations with 7+ large ideals: 1458
Tue Jan 01 14:39:36 2008  commencing 2-way merge
Tue Jan 01 14:39:36 2008  reduce to 937963 relation sets and 483377 unique ideals
Tue Jan 01 14:39:36 2008  commencing full merge
Tue Jan 01 14:39:44 2008  found 494408 cycles, need 312469
Tue Jan 01 14:39:44 2008  weight of 312469 cycles is about 14663799 (46.93/cycle)
Tue Jan 01 14:39:44 2008  distribution of cycle lengths:
Tue Jan 01 14:39:44 2008  1 relations: 58689
Tue Jan 01 14:39:44 2008  2 relations: 39492
Tue Jan 01 14:39:44 2008  3 relations: 40123
Tue Jan 01 14:39:44 2008  4 relations: 41915
Tue Jan 01 14:39:44 2008  5 relations: 40061
Tue Jan 01 14:39:44 2008  6 relations: 37158
Tue Jan 01 14:39:44 2008  7 relations: 32276
Tue Jan 01 14:39:44 2008  8 relations: 21083
Tue Jan 01 14:39:44 2008  9 relations: 1645
Tue Jan 01 14:39:44 2008  10+ relations: 27
Tue Jan 01 14:39:44 2008  heaviest cycle: 10 relations
Tue Jan 01 14:39:44 2008  matrix not dense enough, retrying
Tue Jan 01 14:39:45 2008  dataset has -11.2% excess relations
Tue Jan 01 14:39:45 2008  ignoring smallest 109629 rational and 109461 algebraic ideals
Tue Jan 01 14:39:45 2008  filtering ideals above 1435765
Tue Jan 01 14:39:45 2008  need 552806 more relations than ideals
Tue Jan 01 14:39:45 2008  commencing singleton removal, final pass
Tue Jan 01 14:39:59 2008  memory use: 44.0 MB
Tue Jan 01 14:39:59 2008  commencing in-memory singleton removal
Tue Jan 01 14:39:59 2008  begin with 1026961 relations and 622821 unique ideals
Tue Jan 01 14:39:59 2008  reduce to 1021171 relations and 616740 ideals in 5 passes
Tue Jan 01 14:39:59 2008  max relations containing the same ideal: 39
Tue Jan 01 14:39:59 2008  dataset has -21.0% excess relations
Tue Jan 01 14:39:59 2008  relations with 0 large ideals: 27365
Tue Jan 01 14:39:59 2008  relations with 1 large ideals: 43781
Tue Jan 01 14:39:59 2008  relations with 2 large ideals: 192961
Tue Jan 01 14:39:59 2008  relations with 3 large ideals: 326978
Tue Jan 01 14:39:59 2008  relations with 4 large ideals: 265111
Tue Jan 01 14:39:59 2008  relations with 5 large ideals: 132218
Tue Jan 01 14:39:59 2008  relations with 6 large ideals: 28408
Tue Jan 01 14:39:59 2008  relations with 7+ large ideals: 4349
Tue Jan 01 14:39:59 2008  commencing 2-way merge
Tue Jan 01 14:39:59 2008  reduce to 934250 relation sets and 529819 unique ideals
Tue Jan 01 14:39:59 2008  commencing full merge
Tue Jan 01 14:40:09 2008  found 459506 cycles, need 281790
Tue Jan 01 14:40:09 2008  weight of 281790 cycles is about 14994401 (53.21/cycle)
Tue Jan 01 14:40:09 2008  distribution of cycle lengths:
Tue Jan 01 14:40:09 2008  1 relations: 49229
Tue Jan 01 14:40:09 2008  2 relations: 28711
Tue Jan 01 14:40:09 2008  3 relations: 32073
Tue Jan 01 14:40:09 2008  4 relations: 33176
Tue Jan 01 14:40:09 2008  5 relations: 33002
Tue Jan 01 14:40:09 2008  6 relations: 31466
Tue Jan 01 14:40:09 2008  7 relations: 28892
Tue Jan 01 14:40:09 2008  8 relations: 25102
Tue Jan 01 14:40:09 2008  9 relations: 17387
Tue Jan 01 14:40:09 2008  10+ relations: 2752
Tue Jan 01 14:40:09 2008  heaviest cycle: 12 relations
Tue Jan 01 14:40:09 2008  matrix not dense enough, retrying
Tue Jan 01 14:40:10 2008  dataset has -21.0% excess relations
Tue Jan 01 14:40:10 2008  ignoring smallest 84047 rational and 84009 algebraic ideals
Tue Jan 01 14:40:10 2008  filtering ideals above 1076824
Tue Jan 01 14:40:10 2008  need 552806 more relations than ideals
Tue Jan 01 14:40:10 2008  commencing singleton removal, final pass
Tue Jan 01 14:40:24 2008  memory use: 51.4 MB
Tue Jan 01 14:40:24 2008  commencing in-memory singleton removal
Tue Jan 01 14:40:24 2008  begin with 1026961 relations and 673854 unique ideals
Tue Jan 01 14:40:24 2008  reduce to 1020849 relations and 667445 ideals in 5 passes
Tue Jan 01 14:40:24 2008  max relations containing the same ideal: 39
Tue Jan 01 14:40:24 2008  dataset has -31.0% excess relations
Tue Jan 01 14:40:24 2008  relations with 0 large ideals: 21002
Tue Jan 01 14:40:24 2008  relations with 1 large ideals: 23918
Tue Jan 01 14:40:24 2008  relations with 2 large ideals: 130781
Tue Jan 01 14:40:24 2008  relations with 3 large ideals: 280254
Tue Jan 01 14:40:24 2008  relations with 4 large ideals: 296836
Tue Jan 01 14:40:24 2008  relations with 5 large ideals: 196798
Tue Jan 01 14:40:24 2008  relations with 6 large ideals: 58563
Tue Jan 01 14:40:24 2008  relations with 7+ large ideals: 12697
Tue Jan 01 14:40:24 2008  commencing 2-way merge
Tue Jan 01 14:40:25 2008  reduce to 932550 relation sets and 579146 unique ideals
Tue Jan 01 14:40:25 2008  commencing full merge
Tue Jan 01 14:40:37 2008  found 415488 cycles, need 251346
Tue Jan 01 14:40:37 2008  weight of 251346 cycles is about 16835964 (66.98/cycle)
Tue Jan 01 14:40:37 2008  distribution of cycle lengths:
Tue Jan 01 14:40:37 2008  1 relations: 36082
Tue Jan 01 14:40:37 2008  2 relations: 18355
Tue Jan 01 14:40:37 2008  3 relations: 21684
Tue Jan 01 14:40:37 2008  4 relations: 23229
Tue Jan 01 14:40:37 2008  5 relations: 24024
Tue Jan 01 14:40:37 2008  6 relations: 23868
Tue Jan 01 14:40:37 2008  7 relations: 23467
Tue Jan 01 14:40:37 2008  8 relations: 22597
Tue Jan 01 14:40:37 2008  9 relations: 20878
Tue Jan 01 14:40:37 2008  10+ relations: 37162
Tue Jan 01 14:40:37 2008  heaviest cycle: 14 relations
Tue Jan 01 14:40:37 2008  commencing cycle optimization
Tue Jan 01 14:40:37 2008  start with 1423445 relations
Tue Jan 01 14:40:40 2008  pruned 77253 relations
Tue Jan 01 14:40:40 2008  distribution of cycle lengths:
Tue Jan 01 14:40:40 2008  1 relations: 36082
Tue Jan 01 14:40:40 2008  2 relations: 19201
Tue Jan 01 14:40:40 2008  3 relations: 23573
Tue Jan 01 14:40:40 2008  4 relations: 25470
Tue Jan 01 14:40:40 2008  5 relations: 26856
Tue Jan 01 14:40:40 2008  6 relations: 26683
Tue Jan 01 14:40:40 2008  7 relations: 25732
Tue Jan 01 14:40:40 2008  8 relations: 23338
Tue Jan 01 14:40:40 2008  9 relations: 19555
Tue Jan 01 14:40:40 2008  10+ relations: 24856
Tue Jan 01 14:40:40 2008  heaviest cycle: 14 relations
Tue Jan 01 14:40:40 2008  
Tue Jan 01 14:40:40 2008  commencing linear algebra
Tue Jan 01 14:40:41 2008  read 251346 cycles
Tue Jan 01 14:40:41 2008  cycles contain 619371 unique relations
Tue Jan 01 14:40:51 2008  read 619371 relations
Tue Jan 01 14:40:52 2008  using 32 quadratic characters above 66962852
Tue Jan 01 14:41:08 2008  read 251346 cycles
Tue Jan 01 14:41:08 2008  matrix is 251074 x 251346 with weight 21872762 (avg 87.02/col)
Tue Jan 01 14:41:10 2008  filtering completed in 3 passes
Tue Jan 01 14:41:10 2008  matrix is 248400 x 248600 with weight 21758354 (avg 87.52/col)
Tue Jan 01 14:41:12 2008  read 248600 cycles
Tue Jan 01 14:41:12 2008  matrix is 248400 x 248600 with weight 21758354 (avg 87.52/col)
Tue Jan 01 14:41:12 2008  saving the first 48 matrix rows for later
Tue Jan 01 14:41:12 2008  matrix is 248352 x 248600 with weight 16374861 (avg 65.87/col)
Tue Jan 01 14:41:12 2008  matrix includes 64 packed rows
Tue Jan 01 14:41:12 2008  using block size 65536 for processor cache size 4096 kB
Tue Jan 01 14:41:14 2008  commencing Lanczos iteration
Tue Jan 01 14:47:14 2008  lanczos halted after 3928 iterations (dim = 248352)
Tue Jan 01 14:47:14 2008  recovered 49 nontrivial dependencies
Tue Jan 01 14:47:14 2008  
Tue Jan 01 14:47:14 2008  commencing square root phase
Tue Jan 01 14:47:14 2008  reading relations for dependency 1
Tue Jan 01 14:47:15 2008  read 124512 cycles
Tue Jan 01 14:47:15 2008  cycles contain 390983 unique relations
Tue Jan 01 14:47:24 2008  read 390983 relations
Tue Jan 01 14:47:25 2008  multiplying 671940 relations
Tue Jan 01 14:47:46 2008  multiply complete, coefficients have about 14.68 million bits
Tue Jan 01 14:47:46 2008  initial square root is modulo 270687427
Tue Jan 01 14:48:27 2008  reading relations for dependency 2
Tue Jan 01 14:48:27 2008  read 124447 cycles
Tue Jan 01 14:48:27 2008  cycles contain 391232 unique relations
Tue Jan 01 14:48:36 2008  read 391232 relations
Tue Jan 01 14:48:38 2008  multiplying 671618 relations
Tue Jan 01 14:48:59 2008  multiply complete, coefficients have about 14.67 million bits
Tue Jan 01 14:48:59 2008  initial square root is modulo 268853573
Tue Jan 01 14:49:39 2008  prp58 factor: 9873294020445605937884222927707767247696587114238136245061
Tue Jan 01 14:49:39 2008  prp61 factor: 5551815667874952073437499971611223228873637274238861674179451
Tue Jan 01 14:49:39 2008  elapsed time 00:17:17

jasonp · 2008-01-02, 03:31

Quote:

Originally Posted by jbristow

I threw a bit too much at this overnight run on a tiny number, but I thought it might be interesting to share the log file. The first run ended when it was unable to allocate sufficient memory at the last step. I then reran it with half the relations and it finished fine.

This is a failure mode I haven't thought about; the clique processing ordinarily reduces the amount of excess to a specified limit, but yours is the first factorization with so much initial excess that the cliques ran out before the excess did :)

It turns out the clique processing code is over-engineered enough that generalizing it to work correctly when this happens is fairly easy. If you can keep the dataset around and take this to email, let me know and I can send you a test windows binary.

akruppa · 2008-01-02, 08:16

On a mostly unrelated note, "clique algorithm" is a rather bad misnomer. They are not cliques at all, they are connected components of a graph - and a good thing, too, as finding the former is NP complete in general. I'm a little surprised that "cliques" survived for so long in CWI's software, for example.

In my experience with grossly oversieved projects, reducing the heuristic gain threshold in CWI's filter to 2 always reduces excess enough (it can throw out any relations which contain prime ideals of frequency 2) but I never got any valid dependencies out in the end. I never found out what exactly caused this, but I suspect the matrix was too sparse for BL to converge properly, a problem other have reported here on several occasions.

Alex

jasonp · 2008-01-02, 13:54

Isn't a clique a fully connected subcomponent of the graph? Or is there an additional property to cliques that isn't needed here?

Chris Card · 2008-01-02, 16:47

Quote:

Originally Posted by jasonp

Isn't a clique a fully connected subcomponent of the graph? Or is there an additional property to cliques that isn't needed here?

From wikipedia:

Quote:

In graph theory, a clique in an undirected graph G is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. Alternatively, a clique is a graph in which every vertex is connected to every other vertex in the graph. This is equivalent to saying that the subgraph induced by V is a complete graph. The size of a clique is the number of vertices it contains.

Which isn't quite the same as the "cliques" we use in filtering. But clique is a nice short word and much easier to say than "connected component".

Chris

jasonp · 2008-01-02, 17:40

I read the wikipedia entry, but still don't see how that's different from what we get with NFS filtering. Would a collection of relations be a clique if they only contained ideals that appeared in two relations?

Chris Card · 2008-01-02, 17:44

Quote:

Originally Posted by jasonp

I read the wikipedia entry, but still don't see how that's different from what we get with NFS filtering. Would a collection of relations be a clique if they only contained ideals that appeared in two relations?

In an "NFS clique" (for want of a better word) we only insist that every node (relation) is connected to every other node indirectly, i.e. that the nodes form a connected graph. We don't insist that the graph is fully connected (i.e. every node directly connected to every other node).
At least I think that's what the difference is.

Chris

jasonp · 2008-01-02, 17:56

Quote:

Originally Posted by Chris Card

We don't insist that the graph is fully connected (i.e. every node directly connected to every other node).

<smacks head>

Looks like some documentation needs updating.

akruppa · 2008-01-02, 21:43

Quote:

Originally Posted by Chris Card

At least I think that's what the difference is.

Exactly, in a connected component with n relations, removing that component removes n relations and at least n-1 ideals, so the excess drops by at most 1. If they were a clique, it would remove n(n-1)/2 ideals, but true cliques of more than two relations will be very rare.

Alex

2008-01-02, 13:54	#4
jasonp Tribal Bullet Oct 2004 3,541 Posts	Isn't a clique a fully connected subcomponent of the graph? Or is there an additional property to cliques that isn't needed here? Last fiddled with by jasonp on 2008-01-02 at 13:55

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Oversieving	chris2be8	Msieve	7	2010-03-13 21:51
Oversieving + estimate of relations needed	RedGolpe	Msieve	10	2009-06-15 15:32
v1.40 patch for massive NFS oversieving	jasonp	Msieve	18	2009-04-09 03:20
Has anyone tried some of these extreme ...	petrw1	Hardware	1	2008-08-28 16:23
Oversieving in msieve	fivemack	Msieve	1	2007-09-28 18:26

2008-01-02, 08:16	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	On a mostly unrelated note, "clique algorithm" is a rather bad misnomer. They are not cliques at all, they are connected components of a graph - and a good thing, too, as finding the former is NP complete in general. I'm a little surprised that "cliques" survived for so long in CWI's software, for example. In my experience with grossly oversieved projects, reducing the heuristic gain threshold in CWI's filter to 2 always reduces excess enough (it can throw out any relations which contain prime ideals of frequency 2) but I never got any valid dependencies out in the end. I never found out what exactly caused this, but I suspect the matrix was too sparse for BL to converge properly, a problem other have reported here on several occasions. Alex

2008-01-02, 17:40	#6
jasonp Tribal Bullet Oct 2004 3,541 Posts	I read the wikipedia entry, but still don't see how that's different from what we get with NFS filtering. Would a collection of relations be a clique if they only contained ideals that appeared in two relations?