View Single Post
Old 2010-11-06, 16:12   #1
Tribal Bullet
jasonp's Avatar
Oct 2004

DD216 Posts
Default Distribution of matrix nonzeros

A few months ago, frmky and I were looking for a new angle on matrix multiplies, and he noticed something peculiar when plotting a histogram of the column counts of nonzeros in the matrix for 2,1036+. You would expect a smooth distribution of light columns that peaks at the matrix average, and then trails off into a smaller number of heavier columns.

What we actually see is attached. Why do you think it is that we get 'beats' at the lowest column weights? The matrix average is 81 nonzeros per column; if I had to make up a reason, I would think that the relations that survive the filtering have a bias towards an odd or even number of ideals, and combining a small number of relations into a matrix column magnifies that bias. But it still mystifies me; really I'm worried that the NFS filtering in msieve is actually doing something dumb that I don't know about :)

I'm also reminded for some reason of the 'minimax' phenomenon in function approximation, where the approximation with the lowest worst-case error will alternately overshoot and undershoot a true value.
Attached Thumbnails
Click image for larger version

Name:	moz-screenshot-1.png
Views:	161
Size:	5.5 KB
ID:	5878  

Last fiddled with by jasonp on 2010-11-06 at 16:17
jasonp is offline   Reply With Quote