|
Extreme oversieving and msieve
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] [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 [/code] |
[QUOTE=jbristow;121924]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.
[/QUOTE] 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. |
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 |
Isn't a clique a fully connected subcomponent of the graph? Or is there an additional property to cliques that isn't needed here?
|
[QUOTE=jasonp;121970]Isn't a clique a fully connected subcomponent of the graph? Or is there an additional property to cliques that isn't needed here?[/QUOTE]
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. [/QUOTE] 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 |
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 [i]only[/i] contained ideals that appeared in two relations?
|
[QUOTE=jasonp;122001]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 [i]only[/i] contained ideals that appeared in two relations?[/QUOTE]
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 |
[QUOTE=Chris Card;122002]We don't insist that the graph is fully connected (i.e. every node directly connected to every other node).
[/QUOTE] <smacks head> Looks like some documentation needs updating. |
[QUOTE=Chris Card;122002]
At least I think that's what the difference is. [/QUOTE] Exactly, in a connected component with [I]n[/I] relations, removing that component removes [I]n[/I] relations and at least [I]n[/I]-1 ideals, so the excess drops by at most 1. If they were a clique, it would remove [I]n[/I]([I]n[/I]-1)/2 ideals, but true cliques of more than two relations will be very rare. Alex |
| All times are UTC. The time now is 01:30. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.