Linear algebra crashes

10metreh · 2009-02-01, 18:23

This happened while I was doing a C98 GNFS:

Code:

Sun Feb 01 17:43:58 2009  
Sun Feb 01 17:43:59 2009  
Sun Feb 01 17:43:59 2009  Msieve v. 1.38
Sun Feb 01 17:43:59 2009  random seeds: d28ee430 785d3dd1
Sun Feb 01 17:43:59 2009  factoring 24367117790956463802518784721086469758348217714621421913479699935812740500302971121469928726788073 (98 digits)
Sun Feb 01 17:43:59 2009  commencing number field sieve (98-digit input)
Sun Feb 01 17:44:00 2009  
Sun Feb 01 17:44:00 2009  commencing relation filtering
Sun Feb 01 17:44:00 2009  commencing duplicate removal, pass 1
Sun Feb 01 17:46:19 2009  found 23062 hash collisions in 3536807 relations
Sun Feb 01 17:47:27 2009  added 29894 free relations
Sun Feb 01 17:47:27 2009  commencing duplicate removal, pass 2
Sun Feb 01 17:48:26 2009  found 0 duplicates and 3566701 unique relations
Sun Feb 01 17:48:30 2009  memory use: 36.9 MB
Sun Feb 01 17:48:31 2009  reading rational ideals above 1245184
Sun Feb 01 17:48:31 2009  reading algebraic ideals above 1245184
Sun Feb 01 17:48:31 2009  commencing singleton removal, pass 1
Sun Feb 01 17:53:02 2009  relations with 0 large ideals: 35164
Sun Feb 01 17:53:10 2009  relations with 1 large ideals: 317086
Sun Feb 01 17:53:10 2009  relations with 2 large ideals: 1017654
Sun Feb 01 17:53:11 2009  relations with 3 large ideals: 1370059
Sun Feb 01 17:53:11 2009  relations with 4 large ideals: 692933
Sun Feb 01 17:53:11 2009  relations with 5 large ideals: 101197
Sun Feb 01 17:53:11 2009  relations with 6 large ideals: 32601
Sun Feb 01 17:53:11 2009  relations with 7+ large ideals: 7
Sun Feb 01 17:53:11 2009  3566701 relations and about 3780403 large ideals
Sun Feb 01 17:53:11 2009  commencing singleton removal, pass 2
Sun Feb 01 17:56:31 2009  found 1815843 singletons
Sun Feb 01 17:56:44 2009  current dataset: 1750858 relations and about 1536493 large ideals
Sun Feb 01 17:56:50 2009  commencing singleton removal, pass 3
Sun Feb 01 17:58:48 2009  found 396833 singletons
Sun Feb 01 17:59:10 2009  current dataset: 1354025 relations and about 1104104 large ideals
Sun Feb 01 17:59:18 2009  commencing singleton removal, final pass
Sun Feb 01 18:01:35 2009  memory use: 23.1 MB
Sun Feb 01 18:01:39 2009  commencing in-memory singleton removal
Sun Feb 01 18:01:39 2009  begin with 1354025 relations and 1131195 unique ideals
Sun Feb 01 18:01:46 2009  reduce to 1076190 relations and 843622 ideals in 18 passes
Sun Feb 01 18:01:46 2009  max relations containing the same ideal: 66
Sun Feb 01 18:01:51 2009  reading rational ideals above 622592
Sun Feb 01 18:01:51 2009  reading algebraic ideals above 622592
Sun Feb 01 18:01:51 2009  commencing singleton removal, final pass
Sun Feb 01 18:05:36 2009  keeping 929635 ideals with weight <= 20, new excess is 131683
Sun Feb 01 18:06:08 2009  memory use: 24.6 MB
Sun Feb 01 18:06:13 2009  commencing in-memory singleton removal
Sun Feb 01 18:06:14 2009  begin with 1080449 relations and 929635 unique ideals
Sun Feb 01 18:06:17 2009  reduce to 1074558 relations and 902763 ideals in 8 passes
Sun Feb 01 18:06:17 2009  max relations containing the same ideal: 20
Sun Feb 01 18:06:20 2009  removing 106028 relations and 96507 ideals in 9521 cliques
Sun Feb 01 18:06:20 2009  commencing in-memory singleton removal
Sun Feb 01 18:06:20 2009  begin with 968530 relations and 902763 unique ideals
Sun Feb 01 18:06:23 2009  reduce to 960877 relations and 798520 ideals in 8 passes
Sun Feb 01 18:06:23 2009  max relations containing the same ideal: 20
Sun Feb 01 18:06:25 2009  removing 76991 relations and 67470 ideals in 9521 cliques
Sun Feb 01 18:06:25 2009  commencing in-memory singleton removal
Sun Feb 01 18:06:26 2009  begin with 883886 relations and 798520 unique ideals
Sun Feb 01 18:06:28 2009  reduce to 879041 relations and 726156 ideals in 6 passes
Sun Feb 01 18:06:28 2009  max relations containing the same ideal: 20
Sun Feb 01 18:06:30 2009  relations with 0 large ideals: 17549
Sun Feb 01 18:06:30 2009  relations with 1 large ideals: 107096
Sun Feb 01 18:06:30 2009  relations with 2 large ideals: 263167
Sun Feb 01 18:06:30 2009  relations with 3 large ideals: 298044
Sun Feb 01 18:06:30 2009  relations with 4 large ideals: 154425
Sun Feb 01 18:06:30 2009  relations with 5 large ideals: 33938
Sun Feb 01 18:06:30 2009  relations with 6 large ideals: 4648
Sun Feb 01 18:06:30 2009  relations with 7+ large ideals: 174
Sun Feb 01 18:06:30 2009  commencing 2-way merge
Sun Feb 01 18:06:33 2009  reduce to 500226 relation sets and 347341 unique ideals
Sun Feb 01 18:06:33 2009  commencing full merge
Sun Feb 01 18:06:48 2009  memory use: 23.2 MB
Sun Feb 01 18:06:49 2009  found 225320 cycles, need 207541
Sun Feb 01 18:06:49 2009  weight of 207541 cycles is about 14624266 (70.46/cycle)
Sun Feb 01 18:06:49 2009  distribution of cycle lengths:
Sun Feb 01 18:06:49 2009  1 relations: 25356
Sun Feb 01 18:06:49 2009  2 relations: 19934
Sun Feb 01 18:06:49 2009  3 relations: 19952
Sun Feb 01 18:06:49 2009  4 relations: 18523
Sun Feb 01 18:06:49 2009  5 relations: 17232
Sun Feb 01 18:06:49 2009  6 relations: 15306
Sun Feb 01 18:06:49 2009  7 relations: 13982
Sun Feb 01 18:06:49 2009  8 relations: 12308
Sun Feb 01 18:06:49 2009  9 relations: 11046
Sun Feb 01 18:06:49 2009  10+ relations: 53902
Sun Feb 01 18:06:49 2009  heaviest cycle: 20 relations
Sun Feb 01 18:06:49 2009  commencing cycle optimization
Sun Feb 01 18:06:50 2009  start with 1372875 relations
Sun Feb 01 18:07:02 2009  pruned 41307 relations
Sun Feb 01 18:07:02 2009  memory use: 35.6 MB
Sun Feb 01 18:07:02 2009  distribution of cycle lengths:
Sun Feb 01 18:07:02 2009  1 relations: 25356
Sun Feb 01 18:07:02 2009  2 relations: 20504
Sun Feb 01 18:07:02 2009  3 relations: 20804
Sun Feb 01 18:07:02 2009  4 relations: 19061
Sun Feb 01 18:07:02 2009  5 relations: 17827
Sun Feb 01 18:07:02 2009  6 relations: 15740
Sun Feb 01 18:07:02 2009  7 relations: 14272
Sun Feb 01 18:07:02 2009  8 relations: 12474
Sun Feb 01 18:07:02 2009  9 relations: 11151
Sun Feb 01 18:07:02 2009  10+ relations: 50352
Sun Feb 01 18:07:02 2009  heaviest cycle: 19 relations
Sun Feb 01 18:07:05 2009  
Sun Feb 01 18:07:05 2009  commencing linear algebra
Sun Feb 01 18:07:05 2009  read 207541 cycles
Sun Feb 01 18:07:06 2009  cycles contain 746133 unique relations
Sun Feb 01 18:10:24 2009  read 746133 relations
Sun Feb 01 18:10:57 2009  using 32 quadratic characters above 67105850
Sun Feb 01 18:11:29 2009  building initial matrix
Sun Feb 01 18:11:57 2009  memory use: 88.7 MB
Sun Feb 01 18:12:14 2009  read 207541 cycles
Sun Feb 01 18:12:49 2009  matrix is 207294 x 207541 (59.0 MB) with weight 20787556 (100.16/col)
Sun Feb 01 18:12:50 2009  sparse part has weight 13810266 (66.54/col)
Sun Feb 01 18:13:17 2009  filtering completed in 3 passes
Sun Feb 01 18:13:18 2009  matrix is 205147 x 205347 (58.6 MB) with weight 20614870 (100.39/col)
Sun Feb 01 18:13:19 2009  sparse part has weight 13718903 (66.81/col)
Sun Feb 01 18:13:33 2009  read 205347 cycles
Sun Feb 01 18:13:54 2009  matrix is 205147 x 205347 (58.6 MB) with weight 20614870 (100.39/col)
Sun Feb 01 18:13:54 2009  sparse part has weight 13718903 (66.81/col)
Sun Feb 01 18:13:54 2009  saving the first 48 matrix rows for later
Sun Feb 01 18:13:55 2009  matrix is 205099 x 205347 (56.0 MB) with weight 15973973 (77.79/col)
Sun Feb 01 18:13:55 2009  sparse part has weight 13453473 (65.52/col)
Sun Feb 01 18:13:55 2009  matrix includes 64 packed rows
Sun Feb 01 18:13:55 2009  using block size 10922 for processor cache size 256 kB
Sun Feb 01 18:14:00 2009  commencing Lanczos iteration
Sun Feb 01 18:14:00 2009  memory use: 53.9 MB

Here msieve crashed. It was nothing to do with running out of memory. I will now try with the GGNFS postprocessing tools.

jasonp · 2009-02-01, 21:03

Can you retry the linear algebra with v1.39? That version had more sanity checking included.

10metreh · 2009-02-02, 07:36

Quote:

Originally Posted by jasonp

Can you retry the linear algebra with v1.39? That version had more sanity checking included.

I have no idea why I used 1.38 for that one! Now I'll try 1.39, which is what I used for all my other (successful) GNFS postprocessings.

10metreh · 2009-02-02, 08:34

Success!

Code:

Mon Feb 02 07:37:52 2009  
Mon Feb 02 07:37:52 2009  
Mon Feb 02 07:37:52 2009  Msieve v. 1.39
Mon Feb 02 07:37:52 2009  random seeds: 3550bf80 fdadfd90
Mon Feb 02 07:37:52 2009  factoring 24367117790956463802518784721086469758348217714621421913479699935812740500302971121469928726788073 (98 digits)
Mon Feb 02 07:37:54 2009  searching for 15-digit factors
Mon Feb 02 07:37:57 2009  commencing number field sieve (98-digit input)
Mon Feb 02 07:37:57 2009  R0: -6463540024746743410
Mon Feb 02 07:37:57 2009  R1:  8373273499
Mon Feb 02 07:37:57 2009  A0: -531626976148681332872733
Mon Feb 02 07:37:57 2009  A1:  123005448554502138104
Mon Feb 02 07:37:57 2009  A2:  5599299139790838
Mon Feb 02 07:37:57 2009  A3: -1037433187864
Mon Feb 02 07:37:57 2009  A4: -6912425
Mon Feb 02 07:37:57 2009  A5:  2160
Mon Feb 02 07:37:57 2009  skew 1.00, size 5.178705e-010, alpha -4.856955, combined = 2.614192e-009
Mon Feb 02 07:37:58 2009  
Mon Feb 02 07:37:58 2009  commencing relation filtering
Mon Feb 02 07:37:58 2009  commencing duplicate removal, pass 1
Mon Feb 02 07:39:18 2009  found 23957 hash collisions in 3602682 relations
Mon Feb 02 07:40:01 2009  commencing duplicate removal, pass 2
Mon Feb 02 07:40:20 2009  found 0 duplicates and 3602682 unique relations
Mon Feb 02 07:40:20 2009  memory use: 36.9 MB
Mon Feb 02 07:40:20 2009  reading rational ideals above 1245184
Mon Feb 02 07:40:20 2009  reading algebraic ideals above 1245184
Mon Feb 02 07:40:20 2009  commencing singleton removal, pass 1
Mon Feb 02 07:41:51 2009  relations with 0 large ideals: 35164
Mon Feb 02 07:41:51 2009  relations with 1 large ideals: 317444
Mon Feb 02 07:41:51 2009  relations with 2 large ideals: 1020799
Mon Feb 02 07:41:51 2009  relations with 3 large ideals: 1380723
Mon Feb 02 07:41:51 2009  relations with 4 large ideals: 707776
Mon Feb 02 07:41:51 2009  relations with 5 large ideals: 107701
Mon Feb 02 07:41:51 2009  relations with 6 large ideals: 33064
Mon Feb 02 07:41:51 2009  relations with 7+ large ideals: 11
Mon Feb 02 07:41:51 2009  3602682 relations and about 3799926 large ideals
Mon Feb 02 07:41:51 2009  commencing singleton removal, pass 2
Mon Feb 02 07:43:13 2009  found 1821533 singletons
Mon Feb 02 07:43:13 2009  current dataset: 1781149 relations and about 1554000 large ideals
Mon Feb 02 07:43:14 2009  commencing singleton removal, pass 3
Mon Feb 02 07:44:19 2009  found 395560 singletons
Mon Feb 02 07:44:19 2009  current dataset: 1385589 relations and about 1123922 large ideals
Mon Feb 02 07:44:19 2009  commencing singleton removal, final pass
Mon Feb 02 07:45:10 2009  memory use: 23.7 MB
Mon Feb 02 07:45:11 2009  commencing in-memory singleton removal
Mon Feb 02 07:45:11 2009  begin with 1385589 relations and 1151677 unique ideals
Mon Feb 02 07:45:17 2009  reduce to 1112526 relations and 869308 ideals in 18 passes
Mon Feb 02 07:45:17 2009  max relations containing the same ideal: 67
Mon Feb 02 07:45:20 2009  reading rational ideals above 622592
Mon Feb 02 07:45:20 2009  reading algebraic ideals above 622592
Mon Feb 02 07:45:20 2009  commencing singleton removal, final pass
Mon Feb 02 07:45:54 2009  keeping 954761 ideals with weight <= 20, new excess is 132345
Mon Feb 02 07:45:56 2009  memory use: 24.7 MB
Mon Feb 02 07:45:56 2009  commencing in-memory singleton removal
Mon Feb 02 07:45:57 2009  begin with 1116802 relations and 954761 unique ideals
Mon Feb 02 07:46:00 2009  reduce to 1111080 relations and 927987 ideals in 9 passes
Mon Feb 02 07:46:00 2009  max relations containing the same ideal: 20
Mon Feb 02 07:46:02 2009  removing 140159 relations and 125373 ideals in 14786 cliques
Mon Feb 02 07:46:02 2009  commencing in-memory singleton removal
Mon Feb 02 07:46:03 2009  begin with 970921 relations and 927987 unique ideals
Mon Feb 02 07:46:06 2009  reduce to 958303 relations and 789796 ideals in 9 passes
Mon Feb 02 07:46:06 2009  max relations containing the same ideal: 20
Mon Feb 02 07:46:07 2009  removing 103542 relations and 88756 ideals in 14786 cliques
Mon Feb 02 07:46:07 2009  commencing in-memory singleton removal
Mon Feb 02 07:46:08 2009  begin with 854761 relations and 789796 unique ideals
Mon Feb 02 07:46:10 2009  reduce to 846506 relations and 692642 ideals in 7 passes
Mon Feb 02 07:46:10 2009  max relations containing the same ideal: 20
Mon Feb 02 07:46:11 2009  relations with 0 large ideals: 17975
Mon Feb 02 07:46:11 2009  relations with 1 large ideals: 107681
Mon Feb 02 07:46:11 2009  relations with 2 large ideals: 258373
Mon Feb 02 07:46:11 2009  relations with 3 large ideals: 284618
Mon Feb 02 07:46:11 2009  relations with 4 large ideals: 142982
Mon Feb 02 07:46:11 2009  relations with 5 large ideals: 30603
Mon Feb 02 07:46:11 2009  relations with 6 large ideals: 4129
Mon Feb 02 07:46:11 2009  relations with 7+ large ideals: 145
Mon Feb 02 07:46:11 2009  commencing 2-way merge
Mon Feb 02 07:46:14 2009  reduce to 487522 relation sets and 333658 unique ideals
Mon Feb 02 07:46:14 2009  commencing full merge
Mon Feb 02 07:46:28 2009  memory use: 22.3 MB
Mon Feb 02 07:46:28 2009  found 220266 cycles, need 201858
Mon Feb 02 07:46:28 2009  weight of 201858 cycles is about 14279870 (70.74/cycle)
Mon Feb 02 07:46:28 2009  distribution of cycle lengths:
Mon Feb 02 07:46:28 2009  1 relations: 24730
Mon Feb 02 07:46:28 2009  2 relations: 18890
Mon Feb 02 07:46:28 2009  3 relations: 18907
Mon Feb 02 07:46:28 2009  4 relations: 17717
Mon Feb 02 07:46:28 2009  5 relations: 16549
Mon Feb 02 07:46:28 2009  6 relations: 15178
Mon Feb 02 07:46:28 2009  7 relations: 13749
Mon Feb 02 07:46:28 2009  8 relations: 12155
Mon Feb 02 07:46:28 2009  9 relations: 11017
Mon Feb 02 07:46:28 2009  10+ relations: 52966
Mon Feb 02 07:46:28 2009  heaviest cycle: 19 relations
Mon Feb 02 07:46:28 2009  commencing cycle optimization
Mon Feb 02 07:46:30 2009  start with 1337951 relations
Mon Feb 02 07:46:40 2009  pruned 41993 relations
Mon Feb 02 07:46:40 2009  memory use: 34.5 MB
Mon Feb 02 07:46:40 2009  distribution of cycle lengths:
Mon Feb 02 07:46:40 2009  1 relations: 24730
Mon Feb 02 07:46:40 2009  2 relations: 19417
Mon Feb 02 07:46:41 2009  3 relations: 19753
Mon Feb 02 07:46:41 2009  4 relations: 18357
Mon Feb 02 07:46:41 2009  5 relations: 17127
Mon Feb 02 07:46:41 2009  6 relations: 15612
Mon Feb 02 07:46:41 2009  7 relations: 14042
Mon Feb 02 07:46:41 2009  8 relations: 12342
Mon Feb 02 07:46:41 2009  9 relations: 11255
Mon Feb 02 07:46:41 2009  10+ relations: 49223
Mon Feb 02 07:46:41 2009  heaviest cycle: 19 relations
Mon Feb 02 07:46:42 2009  
Mon Feb 02 07:46:42 2009  commencing linear algebra
Mon Feb 02 07:46:42 2009  read 201858 cycles
Mon Feb 02 07:46:44 2009  cycles contain 719851 unique relations
Mon Feb 02 07:47:10 2009  read 719851 relations
Mon Feb 02 07:47:13 2009  using 20 quadratic characters above 67106592
Mon Feb 02 07:47:26 2009  building initial matrix
Mon Feb 02 07:47:47 2009  memory use: 86.1 MB
Mon Feb 02 07:47:48 2009  read 201858 cycles
Mon Feb 02 07:47:53 2009  matrix is 201607 x 201858 (56.7 MB) with weight 19042492 (94.34/col)
Mon Feb 02 07:47:53 2009  sparse part has weight 13457186 (66.67/col)
Mon Feb 02 07:48:15 2009  filtering completed in 3 passes
Mon Feb 02 07:48:15 2009  matrix is 199823 x 200023 (56.4 MB) with weight 18905265 (94.52/col)
Mon Feb 02 07:48:15 2009  sparse part has weight 13376877 (66.88/col)
Mon Feb 02 07:48:29 2009  read 200023 cycles
Mon Feb 02 07:48:48 2009  matrix is 199823 x 200023 (56.4 MB) with weight 18905265 (94.52/col)
Mon Feb 02 07:48:48 2009  sparse part has weight 13376877 (66.88/col)
Mon Feb 02 07:48:48 2009  saving the first 48 matrix rows for later
Mon Feb 02 07:48:48 2009  matrix is 199775 x 200023 (53.8 MB) with weight 14842494 (74.20/col)
Mon Feb 02 07:48:48 2009  sparse part has weight 12904466 (64.51/col)
Mon Feb 02 07:48:48 2009  matrix includes 64 packed rows
Mon Feb 02 07:48:48 2009  using block size 10922 for processor cache size 256 kB
Mon Feb 02 07:48:52 2009  commencing Lanczos iteration
Mon Feb 02 07:48:52 2009  memory use: 52.1 MB
Mon Feb 02 08:06:45 2009  lanczos halted after 3160 iterations (dim = 199775)
Mon Feb 02 08:06:46 2009  recovered 33 nontrivial dependencies
Mon Feb 02 08:06:47 2009  
Mon Feb 02 08:06:47 2009  commencing square root phase
Mon Feb 02 08:06:47 2009  reading relations for dependency 1
Mon Feb 02 08:06:47 2009  read 100209 cycles
Mon Feb 02 08:06:48 2009  cycles contain 441513 unique relations
Mon Feb 02 08:07:14 2009  read 441513 relations
Mon Feb 02 08:07:20 2009  multiplying 358598 relations
Mon Feb 02 08:09:54 2009  multiply complete, coefficients have about 13.42 million bits
Mon Feb 02 08:09:55 2009  initial square root is modulo 51526051
Mon Feb 02 08:14:42 2009  reading relations for dependency 2
Mon Feb 02 08:14:42 2009  read 99867 cycles
Mon Feb 02 08:14:43 2009  cycles contain 441211 unique relations
Mon Feb 02 08:15:09 2009  read 441211 relations
Mon Feb 02 08:15:16 2009  multiplying 358348 relations
Mon Feb 02 08:17:49 2009  multiply complete, coefficients have about 13.41 million bits
Mon Feb 02 08:17:51 2009  initial square root is modulo 50816681
Mon Feb 02 08:22:38 2009  reading relations for dependency 3
Mon Feb 02 08:22:39 2009  read 100094 cycles
Mon Feb 02 08:22:39 2009  cycles contain 440628 unique relations
Mon Feb 02 08:24:18 2009  read 440628 relations
Mon Feb 02 08:24:25 2009  multiplying 357530 relations
Mon Feb 02 08:26:58 2009  multiply complete, coefficients have about 13.38 million bits
Mon Feb 02 08:27:00 2009  initial square root is modulo 48902813
Mon Feb 02 08:31:47 2009  prp42 factor: 392943207419599073442783167696604677679361
Mon Feb 02 08:31:47 2009  prp56 factor: 62011805601556989454691046155135272551312330328483407593
Mon Feb 02 08:31:47 2009  elapsed time 00:53:55

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
restarting nfs linear algebra	cubaq	YAFU	2	2017-04-02 11:35
Restarting linear algebra	wombatman	Msieve	2	2013-10-09 15:54
Linear algebra at 600%	CRGreathouse	Msieve	8	2009-08-05 07:25
Linear algebra proof	Damian	Math	8	2007-02-12 22:25
Linear algebra in MPQS	R1zZ1	Factoring	2	2007-02-02 06:45

2009-02-01, 21:03	#2
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	Can you retry the linear algebra with v1.39? That version had more sanity checking included.