Error: "matrix must have more columns than rows"

mdettweiler · 2009-03-12, 18:03

While doing postprocessing for a 143-digit 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 re-ran 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.

fivemack · 2009-03-12, 18:32

It's a known problem; it's a side-effect of over-sieving. 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 primes-that-only-appear-twice and singleton-remove again.

mdettweiler · 2009-03-12, 18:46

Quote:

Originally Posted by fivemack

It's a known problem; it's a side-effect of over-sieving. 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 primes-that-only-appear-twice and singleton-remove again.

Ah, I see. In that case, I'll just chop off a million relations from the end of the file; I'm nowhere near experienced enough with this stuff to even know where the heck the large primes are in each relation, so manual duplicate/singleton removal is out of the question.

henryzz · 2009-03-12, 19:36

Quote:

Originally Posted by fivemack

It's a known problem; it's a side-effect of over-sieving. 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 primes-that-only-appear-twice and singleton-remove again.

are there programs/scripts that are publicly available to do manual singleton and duplicate removal?

10metreh · 2009-03-12, 20:04

Quote:

Originally Posted by henryzz

are there programs/scripts that are publicly available to do manual singleton and duplicate removal?

I don't know about ones that can do that but not the rest, but they're not manual if they're programs or scripts.

mdettweiler · 2009-03-12, 21:44

Okay--after 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

Thanks fivemack for the tips!

Syd · 2009-03-16, 19:04

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 15-digit factors
commencing number field sieve (115-digit input)
R0: -11210342640088154820318
R1:  1152064867141
A0: -5619434984954391401650872275
A1:  147039079147542754444018
A2:  16511393449404336585
A3: -194916914191114
A4: -10517704834
A5:  46020
skew 43450.30, size 5.341165e-11, alpha -6.332467, combined = 5.355583e-10

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 in-memory 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 in-memory 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 in-memory 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 in-memory 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 2-way 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 15-digit factors
commencing number field sieve (115-digit input)
R0: -11210342640088154820318
R1:  1152064867141
A0: -5619434984954391401650872275
A1:  147039079147542754444018
A2:  16511393449404336585
A3: -194916914191114
A4: -10517704834
A5:  46020
skew 43450.30, size 5.341165e-11, alpha -6.332467, combined = 5.355583e-10

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...

Discarded some relations after this. Now i get:

Code:

Msieve v. 1.40
Mon Mar 16 19:52:50 2009
random seeds: 4df61d88 067f2d71
factoring 8147621547643445045902415398551635946770374997957739600121158565901700158478695850547132717897702224121402628140657 (115 digits)
searching for 15-digit factors
commencing number field sieve (115-digit input)
R0: -11210342640088154820318
R1:  1152064867141
A0: -5619434984954391401650872275
A1:  147039079147542754444018
A2:  16511393449404336585
A3: -194916914191114
A4: -10517704834
A5:  46020
skew 43450.30, size 5.341165e-11, alpha -6.332467, combined = 5.355583e-10

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 in-memory 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 in-memory 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

Any ideas?

henryzz · 2009-03-16, 19:17

discard less relations than the first time

Syd · 2009-03-16, 20:44

Thanks henryzz!

After several tries msieve had the right number of relations to give the factorization,

prp54 factor: 372902330334429972736115370208916075494099188132845393
prp62 factor: 21849210597145944734625965124826298662905059102934029973314849

mdettweiler · 2009-03-16, 22:34

Quote:

Originally Posted by henryzz

discard less relations than the first time

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 non-tiny numbers.)

jasonp · 2009-03-17, 02:38

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 :)

2009-03-12, 21:44	#6
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	Okay--after 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 Thanks fivemack for the tips!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
"lanczos error: only trivial dependencies found" with massive oversieving	eigma	Msieve	21	2015-05-28 03:27
"ERROR: Unable to open spool file."	no1hasdisid	Software	1	2013-05-06 05:24
matrix needs more columns than rows	ryanp	Msieve	2	2013-05-02 00:02
matrix needs more columns than rows	wreck	Msieve	7	2010-09-07 10:03
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2009-03-12, 18:32	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	It's a known problem; it's a side-effect of over-sieving. 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 primes-that-only-appear-twice and singleton-remove again.

2009-03-16, 19:17	#8
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³×3×5×7² Posts	discard less relations than the first time

2009-03-16, 20:44	#9
Syd 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

2009-03-17, 02:38	#11
jasonp Tribal Bullet Oct 2004 3541₁₀ 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 :)