20090312, 18:03  #1 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Error: "matrix must have more columns than rows"
While doing postprocessing for a 143digit SNFS number with SNFS difficulty of 163 digits, I encountered an error message stating "matrix must have more columns than rows" during the linear algebra phase of postprocessing. This happened twice, first when factMsieve.pl ran msieve to postprocess this job, and again when I reran msieve on the same msieve.dat file manually.
Is this a bug? Or is it a "normal" error inherent to how NFS postprocessing works? The log file is attached, and I can provide any of the necessary files (relations, msieve.dat.mat, msieve.dat.s, etc.), though be forewarned that if you do need the relations, they're almost 1 GB so I'd need some FTP/SCP space somewhere in order to send them. 
20090312, 18:32  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
It's a known problem; it's a sideeffect of oversieving. Throw away a million random relations and try again; if you want to be clever, do your own duplicate and singleton removal, then throw away relations containing large primesthatonlyappeartwice and singletonremove again.

20090312, 18:46  #3  
A Sunny Moo
Aug 2007
USA (GMT5)
1869_{16} Posts 
Quote:
Last fiddled with by mdettweiler on 20090312 at 18:46 

20090312, 19:36  #4  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011100010_{2} Posts 
Quote:


20090312, 20:04  #5 
Nov 2008
2322_{10} Posts 

20090312, 21:44  #6 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Okayafter a bunch of fiddling around with just how many relations to discard (1 million turned out to be a bit too much, though ditching about .4 million worked), I finally got msieve to process the matrix and finish the factorization correctly!
Code:
prp41 factor: 16992883783519846308764066577664900740967 prp103 factor: 1979092671373367048595934073451965110198678986743029049601958788254140099138182740089543592879492970011 
20090316, 19:04  #7 
Sep 2008
Krefeld, Germany
346_{8} Posts 
Postprocessing an C115 GNFS gives me the same error, but discarding relations didnt help. Here is the log with all relations:
msieve s 5.dat l 5.log i 5.ini v nf 5.fb t 4 nc1 Code:
Msieve v. 1.40 Mon Mar 16 19:21:00 2009 random seeds: 8b2fd9bc 33931d5b factoring 8147621547643445045902415398551635946770374997957739600121158565901700158478695850547132717897702224121402628140657 (115 digits) searching for 15digit factors commencing number field sieve (115digit input) R0: 11210342640088154820318 R1: 1152064867141 A0: 5619434984954391401650872275 A1: 147039079147542754444018 A2: 16511393449404336585 A3: 194916914191114 A4: 10517704834 A5: 46020 skew 43450.30, size 5.341165e11, alpha 6.332467, combined = 5.355583e10 commencing relation filtering commencing duplicate removal, pass 1 found 988996 hash collisions in 8200371 relations added 547 free relations commencing duplicate removal, pass 2 found 1152947 duplicates and 7047971 unique relations memory use: 50.6 MB reading rational ideals above 3080192 reading algebraic ideals above 3080192 commencing singleton removal, pass 1 relations with 0 large ideals: 83791 relations with 1 large ideals: 727769 relations with 2 large ideals: 2225571 relations with 3 large ideals: 2769755 relations with 4 large ideals: 1159024 relations with 5 large ideals: 25987 relations with 6 large ideals: 56074 relations with 7+ large ideals: 0 7047971 relations and about 7328172 large ideals commencing singleton removal, pass 2 found 3478503 singletons current dataset: 3569468 relations and about 3086283 large ideals commencing singleton removal, pass 3 found 730953 singletons current dataset: 2838515 relations and about 2295820 large ideals commencing singleton removal, pass 4 found 228515 singletons current dataset: 2610000 relations and about 2059989 large ideals commencing singleton removal, final pass memory use: 43.0 MB commencing inmemory singleton removal begin with 2610000 relations and 2163302 unique ideals reduce to 2173315 relations and 1716152 ideals in 17 passes max relations containing the same ideal: 17 reading rational ideals above 720000 reading algebraic ideals above 720000 commencing singleton removal, final pass keeping 2175688 ideals with weight <= 20, new excess is 238267 memory use: 66.2 MB commencing inmemory singleton removal begin with 2372681 relations and 2175688 unique ideals reduce to 2230299 relations and 1917092 ideals in 10 passes max relations containing the same ideal: 20 removing 200749 relations and 182340 ideals in 18409 cliques commencing inmemory singleton removal begin with 2029550 relations and 1917092 unique ideals reduce to 2016533 relations and 1721579 ideals in 8 passes max relations containing the same ideal: 20 removing 147136 relations and 128727 ideals in 18409 cliques commencing inmemory singleton removal begin with 1869397 relations and 1721579 unique ideals reduce to 1861185 relations and 1584547 ideals in 8 passes max relations containing the same ideal: 20 relations with 0 large ideals: 19403 relations with 1 large ideals: 142367 relations with 2 large ideals: 426417 relations with 3 large ideals: 627473 relations with 4 large ideals: 459771 relations with 5 large ideals: 156049 relations with 6 large ideals: 27606 relations with 7+ large ideals: 2099 commencing 2way merge reduce to 1116194 relation sets and 839024 unique ideals commencing full merge memory use: 70.1 MB found 497123 cycles, need 465224 weight of 465224 cycles is about 32850674 (70.61/cycle) distribution of cycle lengths: 1 relations: 43720 2 relations: 98300 3 relations: 39729 4 relations: 36939 5 relations: 34385 6 relations: 30839 7 relations: 27792 8 relations: 24804 9 relations: 21565 10+ relations: 107151 heaviest cycle: 20 relations commencing cycle optimization start with 2851263 relations pruned 72042 relations memory use: 95.3 MB distribution of cycle lengths: 1 relations: 43720 2 relations: 99841 3 relations: 40834 4 relations: 37830 5 relations: 35358 6 relations: 31492 7 relations: 28284 8 relations: 25079 9 relations: 21791 10+ relations: 100995 heaviest cycle: 20 relations RelProcTime: 253 elapsed time 00:04:20 > Doing matrix solving step... =>nice n 10 "../../bin/msieve" s 5.dat l ggnfs.log i 5.ini v nf 5.fb t 4 nc2 Msieve v. 1.40 Mon Mar 16 19:25:20 2009 random seeds: d9e00d07 063a8c15 factoring 8147621547643445045902415398551635946770374997957739600121158565901700158478695850547132717897702224121402628140657 (115 digits) searching for 15digit factors commencing number field sieve (115digit input) R0: 11210342640088154820318 R1: 1152064867141 A0: 5619434984954391401650872275 A1: 147039079147542754444018 A2: 16511393449404336585 A3: 194916914191114 A4: 10517704834 A5: 46020 skew 43450.30, size 5.341165e11, alpha 6.332467, combined = 5.355583e10 commencing linear algebra read 465224 cycles cycles contain 1590526 unique relations read 1590526 relations using 20 quadratic characters above 134217618 building initial matrix memory use: 200.0 MB read 465224 cycles matrix is 464780 x 465224 (136.1 MB) with weight 42187650 (90.68/col) sparse part has weight 30099287 (64.70/col) filtering completed in 2 passes matrix is 459116 x 399829 (132.3 MB) with weight 41783464 (104.50/col) sparse part has weight 29881760 (74.74/col) read 399829 cycles matrix is 459116 x 399829 (132.3 MB) with weight 41783464 (104.50/col) sparse part has weight 29881760 (74.74/col) matrix must have more columns than rows Return value 65280. Terminating... Code:
Msieve v. 1.40 Mon Mar 16 19:52:50 2009 random seeds: 4df61d88 067f2d71 factoring 8147621547643445045902415398551635946770374997957739600121158565901700158478695850547132717897702224121402628140657 (115 digits) searching for 15digit factors commencing number field sieve (115digit input) R0: 11210342640088154820318 R1: 1152064867141 A0: 5619434984954391401650872275 A1: 147039079147542754444018 A2: 16511393449404336585 A3: 194916914191114 A4: 10517704834 A5: 46020 skew 43450.30, size 5.341165e11, alpha 6.332467, combined = 5.355583e10 commencing relation filtering commencing duplicate removal, pass 1 found 925604 hash collisions in 8001596 relations added 547 free relations commencing duplicate removal, pass 2 found 954172 duplicates and 7047971 unique relations memory use: 50.6 MB reading rational ideals above 3080192 reading algebraic ideals above 3080192 commencing singleton removal, pass 1 relations with 0 large ideals: 83791 relations with 1 large ideals: 727769 relations with 2 large ideals: 2225571 relations with 3 large ideals: 2769755 relations with 4 large ideals: 1159024 relations with 5 large ideals: 25987 relations with 6 large ideals: 56074 relations with 7+ large ideals: 0 7047971 relations and about 7328172 large ideals commencing singleton removal, pass 2 found 3478503 singletons current dataset: 3569468 relations and about 3086283 large ideals commencing singleton removal, pass 3 found 730953 singletons current dataset: 2838515 relations and about 2295820 large ideals commencing singleton removal, pass 4 found 228515 singletons current dataset: 2610000 relations and about 2059989 large ideals commencing singleton removal, final pass memory use: 43.0 MB commencing inmemory singleton removal begin with 2610000 relations and 2163302 unique ideals reduce to 2173315 relations and 1716152 ideals in 17 passes max relations containing the same ideal: 17 reading rational ideals above 720000 reading algebraic ideals above 720000 commencing singleton removal, final pass keeping 1934701 ideals with weight <= 20, new excess is 228654 memory use: 65.2 MB commencing inmemory singleton removal begin with 2173906 relations and 1934701 unique ideals reduce to 2167809 relations and 1925856 ideals in 12 passes max relations containing the same ideal: 20 filtering wants 69855 more relations elapsed time 00:04:58 
20090316, 19:17  #8 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011100010_{2} Posts 
discard less relations than the first time

20090316, 20:44  #9 
Sep 2008
Krefeld, Germany
2×5×23 Posts 
Thanks henryzz!
After several tries msieve had the right number of relations to give the factorization, prp54 factor: 372902330334429972736115370208916075494099188132845393 prp62 factor: 21849210597145944734625965124826298662905059102934029973314849 
20090316, 22:34  #10 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Yeah, that's what I had to do, too...I'm somewhat surprised at the relatively small margin of error that these particular numbers had. (Maybe that's why they caused msieve to fail with the "matrix must have more columns than rows" error? Because mine had been sieved with factMsieve.pl, which can sometimes slightly end up oversieving, but isn't going to do so by an overly huge margin for nontiny numbers.)

20090317, 02:38  #11 
Tribal Bullet
Oct 2004
3^{3}×131 Posts 
Oversieving was not the problem here, the matrix is dense enough. The problem actually seems to be that you had very slightly more relations than you needed, and the final matrix required that many columns had only two relations in them (see the final tally at the end of the filtering). When the linear algebra starts, many of these columns are probably merged together and wind up empty, which cuts too many columns out of the matrix. I suspect if you had a few more excess relations, or the filtering removed singletons after the heavy columns are deleted, that the job would finish without problems.
Postprocessing problems come in many shapes and sizes, and they can still occaisionally surprise me. I think it's a wonder that the default choices work correctly as often as they do :) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
"lanczos error: only trivial dependencies found" with massive oversieving  eigma  Msieve  21  20150528 03:27 
"ERROR: Unable to open spool file."  no1hasdisid  Software  1  20130506 05:24 
matrix needs more columns than rows  ryanp  Msieve  2  20130502 00:02 
matrix needs more columns than rows  wreck  Msieve  7  20100907 10:03 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 