mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-11-06, 16:12   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353810 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:	159
Size:	5.5 KB
ID:	5878  

Last fiddled with by jasonp on 2010-11-06 at 16:17
jasonp is offline   Reply With Quote
Old 2010-11-08, 13:06   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.

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 .......
R.D. Silverman is offline   Reply With Quote
Old 2010-11-08, 13:34   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

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 10-15 factors wide :)
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Connectivity Matrix Xyzzy Lounge 13 2017-02-21 18:29
12+256 matrix job fivemack Factoring 11 2009-08-18 17:39
GF(2) Matrix request oslik Factoring 22 2008-11-02 12:53
[Need help] about Matrix Polynomial buan Homework Help 3 2007-07-17 15:07
CWI Matrix Solver R.D. Silverman NFSNET Discussion 6 2006-03-19 17:56

All times are UTC. The time now is 08:47.

Sun May 16 08:47:52 UTC 2021 up 38 days, 3:28, 0 users, load averages: 1.19, 1.67, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.