20101106, 16:12  #1 
Tribal Bullet
Oct 2004
3538_{10} Posts 
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 worstcase error will alternately overshoot and undershoot a true value. Last fiddled with by jasonp on 20101106 at 16:17 
20101108, 13:06  #2  
Nov 2003
7460_{10} Posts 
Quote:
Keep in mind that for the algebraic norms, not every prime is in the factor base. The algebraic polynomial must have a root mod p. Some primes are excluded ....... 

20101108, 13:34  #3 
Tribal Bullet
Oct 2004
2·29·61 Posts 
A more pedestrian explanation would be that most relations have about the same number of factors, but only whole relations are merged together to form matrix columns, so it makes sense that there are large numbers of matrix columns with about the same weight, separated by troughs that are 1015 factors wide :)

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Connectivity Matrix  Xyzzy  Lounge  13  20170221 18:29 
12+256 matrix job  fivemack  Factoring  11  20090818 17:39 
GF(2) Matrix request  oslik  Factoring  22  20081102 12:53 
[Need help] about Matrix Polynomial  buan  Homework Help  3  20070717 15:07 
CWI Matrix Solver  R.D. Silverman  NFSNET Discussion  6  20060319 17:56 