Filtering - Page 2

Sleepy · 2011-07-14, 05:52

THANKS! I have understood the code! Didn't realize that x/log(x) was the approximation for PI(x). And yeah i have read the pdf file that you wrote. =D Anyway is 40.0 a value found through experimentation?

jasonp · 2011-07-14, 10:45

I admit that I did not play with it all that much, and suspect the exact value used doesn't matter that much either. Primarily the 40 is used because other code used to start with a weight of 20 and increase the weight by a little at a time before going to the merge phase.

Sleepy · 2011-07-15, 08:56

Okok! Thanks!

Sleepy · 2011-07-20, 07:35

Hmm, did you use any assumption for the merging steps?

jasonp · 2011-07-20, 11:15

The entire merge phase relies on several assumptions :)

Merging really is sparse Gauss elimination, and choosing an order to merge the rows in the matrix so that the final result is as sparse as possible is (I think) an NP-hard problem. So there is a huge variety of heuristic methods that try to get a good result anyway. Msieve implements several of the simplest of these methods, since the more complex ones are rocket science (if you don't believe me, put your thinking cap on and read some modern papers on sparse direct solvers for linear systems :)

Perhaps the most critical assumption is that the running time of the linear algebra is minimized if the filtering builds a matrix that minimizes (size of matrix) * (number of nonzero matrix entries). Experiments show that for large problems this isn't true, the size of the matrix matters much more than its density, but it isn't clear how to modify that estimate, especially to account for parallel linear algebra.

Sleepy · 2011-07-21, 09:03

Ok thats true, i got it! Hmm is there a way that a "relation number" can get corrupted? Because sometimes when i run the merging step, it gives me a segmentation fault. I manged to find that the relation number got corrupted (became a rubbish value > than the number of relations), thus accessing an invalid location.

jasonp · 2011-07-21, 13:07

The dataset is not corrupted intentionally :)

If a case where this happens is not too large, can you upload to rapidshare or similar for me to look at?

Sleepy · 2011-08-02, 03:30

Its ok! I solved the problem! Turns out that one of my relation is corrupted. It has 2 similar large ideal. =x Anyway, which square root algorithm is implemented in msieve? And do you have any reference that describes the algorithm because i would like to read up on that haha.

jasonp · 2011-08-02, 11:29

A corrupted relation should not have caused a crash; big jobs often have dozens to hundreds of them.

The algorithm used in the square root was first described in one of the original papers on GNFS, as printed in this book, unfortunately I haven't seen the paper reprinted anywhere else. See also the description in Per Leslie Jensen's Master's thesis on PGNFS, and the comments at the top of gnfs/sqrt/sqrt_a.c

MsieveBug · 2011-08-03, 16:58

Quote:

Originally Posted by jasonp

unfortunately I haven't seen the paper reprinted anywhere else.

Sleepy: try http://www.sendspace.com/file/zdnu5g

ET_ · 2011-08-04, 07:49

Quote:

Originally Posted by MsieveBug

Sleepy: try http://www.sendspace.com/file/zdnu5g

What's djvu extension? :surprised

Luigi

2011-07-20, 11:15	#16
jasonp Tribal Bullet Oct 2004 3,541 Posts	The entire merge phase relies on several assumptions :) Merging really is sparse Gauss elimination, and choosing an order to merge the rows in the matrix so that the final result is as sparse as possible is (I think) an NP-hard problem. So there is a huge variety of heuristic methods that try to get a good result anyway. Msieve implements several of the simplest of these methods, since the more complex ones are rocket science (if you don't believe me, put your thinking cap on and read some modern papers on sparse direct solvers for linear systems :) Perhaps the most critical assumption is that the running time of the linear algebra is minimized if the filtering builds a matrix that minimizes (size of matrix) * (number of nonzero matrix entries). Experiments show that for large problems this isn't true, the size of the matrix matters much more than its density, but it isn't clear how to modify that estimate, especially to account for parallel linear algebra. Last fiddled with by jasonp on 2011-07-20 at 11:19

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
NFS filtering in the era of big data	jasonp	Msieve	36	2018-05-07 19:55
NFS filtering error...	Stargate38	YAFU	4	2016-04-20 16:53
The big filtering bug strikes again (I think)	Dubslow	Msieve	20	2016-02-05 14:00
Filtering Error	richs	Msieve	8	2015-01-18 17:40
Filtering	R.D. Silverman	Cunningham Tables	14	2010-08-05 08:30

2011-07-14, 05:52	#12
Sleepy May 2011 23 Posts	THANKS! I have understood the code! Didn't realize that x/log(x) was the approximation for PI(x). And yeah i have read the pdf file that you wrote. =D Anyway is 40.0 a value found through experimentation?

2011-07-14, 10:45	#13
jasonp Tribal Bullet Oct 2004 3,541 Posts	I admit that I did not play with it all that much, and suspect the exact value used doesn't matter that much either. Primarily the 40 is used because other code used to start with a weight of 20 and increase the weight by a little at a time before going to the merge phase.

2011-07-20, 07:35	#15
Sleepy May 2011 23 Posts	Hmm, did you use any assumption for the merging steps?

2011-07-21, 09:03	#17
Sleepy May 2011 23 Posts	Ok thats true, i got it! Hmm is there a way that a "relation number" can get corrupted? Because sometimes when i run the merging step, it gives me a segmentation fault. I manged to find that the relation number got corrupted (became a rubbish value > than the number of relations), thus accessing an invalid location.

2011-07-21, 13:07	#18
jasonp Tribal Bullet Oct 2004 3,541 Posts	The dataset is not corrupted intentionally :) If a case where this happens is not too large, can you upload to rapidshare or similar for me to look at?

2011-08-02, 03:30	#19
Sleepy May 2011 10111₂ Posts	Its ok! I solved the problem! Turns out that one of my relation is corrupted. It has 2 similar large ideal. =x Anyway, which square root algorithm is implemented in msieve? And do you have any reference that describes the algorithm because i would like to read up on that haha.

2011-08-02, 11:29	#20
jasonp Tribal Bullet Oct 2004 3,541 Posts	A corrupted relation should not have caused a crash; big jobs often have dozens to hundreds of them. The algorithm used in the square root was first described in one of the original papers on GNFS, as printed in this book, unfortunately I haven't seen the paper reprinted anywhere else. See also the description in Per Leslie Jensen's Master's thesis on PGNFS, and the comments at the top of gnfs/sqrt/sqrt_a.c