Denser matrices save BL time

Batalov · 2010-01-07, 06:35

We have now gambled with a new msieve trick:
with a somewhat (but not a lot) oversieved project, trying to minimize wall clock time (and save resources, too, additional considerations - special Christmas timing, mini-vacations, hence, no additional oversieving), -
instead, raised the TARGET_DENSITY to 90, recompiled, filtered.

A few superficial conclusions so far:
1. It appears that density doesn't have an effect on the BL running time, while the size does (approximately quadratic).
2. Target density cannot be raised too much - the filtering doesn't readily converge (without additional code tweaks). With 110 and 100, the found cycles are much fewer than needed cycles and filtering bails.
3. There's no free lunch - the denser matrix of smaller size still uses practically the same amount of core relations, with more memory needed (because of how the matrix is stored). But for this particular project it was fine - either of the two matrices fits in 8Gb.
4. The less a project is oversieved, the less an area for experimenting with the density (i.e. if factMsieve.pl built a matrix for you, then the project is only sieved to converge with 70; need to sieve more to get convergence with 80, then more for 90, etc).

The full results will be available a week from now. The project in question is 3,551- (31-bit FBLIM, hence expected convergence at 180-200M unique relns). Briefly, in numbers, with 204M unique relations a 16.3M matrix was built with TARGET_DENSITY 70 (BL ETA was over 610hrs, with 4 threads on a Phenom 940), and a 14.9M matrix was built with TARGET_DENSITY 90 (BL ETA 504hrs). The ETA is now 133hrs, no problems yet (not a single restart). Of course, there's still a possibility that BL will fail to finish (but usually this happens for sparser matrices, not denser).

Batalov+Dodson

P.S. A digression: for some reason, this particular number wants more relations than usual. A very similar in SNFS complexity project produced a 13.8M matrix without any tricks with less relations (10,393+). I have a feeling that 3x⁶+-1 polynomial has bad properties. Similar projects were 3,509+ and 3,521+ and had the "no irreducible polynomials found" and a "sqrt mod 53" (sapienti sat), but the margins of this thread are too narrow to elaborate...

fivemack · 2010-01-14, 14:50

I still have the relations for 2^941-1 on fast disc, and the next job for the large-memory machine hasn't arrived yet, so I will try refiltering with 80/90/100 bounds and see what the matrix size and the iteration rate look like.

Batalov · 2010-01-29, 02:29

Tom, did it pan out? :curious:

fivemack · 2010-01-29, 10:02

Quote:

Originally Posted by Batalov

Tom, did it pan out? :curious:

A new job turned up fairly quickly; for M887, I filtered with the bond set to 70 and to 100.

With limit 70 I got

Code:

weight of 18749374 cycles is about 1312750683 (70.02/cycle)
matrix is 18719088 x 18719336 (5313.4 MB) with weight 1289369814 (68.88/col)
sparse part has weight 1205691632 (64.41/col)

and the Lanczos estimated time was about 700 hours.

With limit 100, I got

Code:

Fri Jan 15 19:46:45 2010  weight of 16745374 cycles is about 1674940954 (100.02/cycle)
Sat Jan 16 00:49:07 2010  matrix is 16730626 x 16730874 (6277.8 MB) with weight 1577539013 (94.29/col)
Sat Jan 16 00:49:07 2010  sparse part has weight 1478376722 (88.36/col)

and the estimated time was about 675 hours, so an advantage but not a terribly exciting one - it wasn't very over-sieved and with two data points I have no idea whether I've overshot the minimum. I am running the limit=100 matrix and it's about half done.

I clearly need to cut bits out of msieve to get a 'run 25 block-Lanczos iterations on projects/foo/bar/msieve.dat.mat and tell me how long it took' program.

Using the relations from M941, limit 70 got

Code:

Sat Nov 28 11:01:06 2009  weight of 24259228 cycles is about 1698245729 (70.00/cycle)
Sat Nov 28 11:49:47 2009  matrix is 24160385 x 24160633 (6716.4 MB) with weight 1620450280 (67.07/col)
Sat Nov 28 11:49:47 2009  sparse part has weight 1519048439 (62.87/col)

and limit 80 got

Code:

Fri Jan 15 08:56:42 2010  weight of 23461228 cycles is about 1877603952 (80.03/cycle)

but it fell over with out-of-memory issues while building the matrix, because I'd forgotten to re-enable swap space after the last reboot.

This will be job one for the New Machine, but at the moment I am in the limbo between payment and delivery on the New Machine.

bdodson · 2010-01-30, 05:35

Quote:

Originally Posted by fivemack

A new job turned up fairly quickly; for M887, I filtered ...

OK, so we know who's doing the postprocessing of the NFS@Home number
M887. Any chance someone here is willing to share info on who's working
on M889 (recently finished sieving; 16e siever.)? -Bruce

frmky · 2010-01-30, 07:39

Quote:

Originally Posted by bdodson

Any chance someone here is willing to share info on who's working on M889 (recently finished sieving; 16e siever.)? -Bruce

M889? It was factored long ago. M899, well, I know. But will I tell?

Yes, I'll tell. I'm doing it in-house.

bdodson · 2010-01-30, 22:35

Quote:

Originally Posted by frmky

M889? It was factored long ago. M899, well, I know. But will I tell?

Yes, I'll tell. I'm doing it in-house.

I've been razz'd! I was about to post a hypothesis that,
since no one else was commenting, it was most likely being
done "in-house". But that was before seeing the white paint.

Inquirying minds want more details, when they're available
(a rather difficult matrix? after 10p268 was scheduled to
finish rather quickly, it seemed). Ah, March 6th; also not
too bad?

On another NFS@Home number, looks like the memory upgrade
on 7p314 came through; with an updated due date of March 12.
-Bruce

frmky · 2010-01-31, 00:03

Quote:

Originally Posted by bdodson

Ah, March 6th; also not
too bad?

On another NFS@Home number, looks like the memory upgrade
on 7p314 came through; with an updated due date of March 12.
-Bruce

Not too bad, 14.1M matrix. Regarding 7p314, I gave up running it here and shipped it off to Jeff.

debrouxl · 2010-02-14, 11:39

After successful complete factorization of two or three RSALS integers filtered with TARGET_DENSITY of 72, I'm raising it to 77.

2010-01-07, 06:35	#1
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Denser matrices save BL time We have now gambled with a new msieve trick: with a somewhat (but not a lot) oversieved project, trying to minimize wall clock time (and save resources, too, additional considerations - special Christmas timing, mini-vacations, hence, no additional oversieving), - instead, raised the TARGET_DENSITY to 90, recompiled, filtered. A few superficial conclusions so far: 1. It appears that density doesn't have an effect on the BL running time, while the size does (approximately quadratic). 2. Target density cannot be raised too much - the filtering doesn't readily converge (without additional code tweaks). With 110 and 100, the found cycles are much fewer than needed cycles and filtering bails. 3. There's no free lunch - the denser matrix of smaller size still uses practically the same amount of core relations, with more memory needed (because of how the matrix is stored). But for this particular project it was fine - either of the two matrices fits in 8Gb. 4. The less a project is oversieved, the less an area for experimenting with the density (i.e. if factMsieve.pl built a matrix for you, then the project is only sieved to converge with 70; need to sieve more to get convergence with 80, then more for 90, etc). The full results will be available a week from now. The project in question is 3,551- (31-bit FBLIM, hence expected convergence at 180-200M unique relns). Briefly, in numbers, with 204M unique relations a 16.3M matrix was built with TARGET_DENSITY 70 (BL ETA was over 610hrs, with 4 threads on a Phenom 940), and a 14.9M matrix was built with TARGET_DENSITY 90 (BL ETA 504hrs). The ETA is now 133hrs, no problems yet (not a single restart). Of course, there's still a possibility that BL will fail to finish (but usually this happens for sparser matrices, not denser). Batalov+Dodson P.S. A digression: for some reason, this particular number wants more relations than usual. A very similar in SNFS complexity project produced a 13.8M matrix without any tricks with less relations (10,393+). I have a feeling that 3x⁶+-1 polynomial has bad properties. Similar projects were 3,509+ and 3,521+ and had the "no irreducible polynomials found" and a "sqrt mod 53" (sapienti sat), but the margins of this thread are too narrow to elaborate...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Plugging Matrices into Functions	Joshua2	Homework Help	50	2009-11-17 02:42
Count of Matrices	davar55	Puzzles	2	2007-06-13 20:46
matrices question	fuzzy	Miscellaneous Math	1	2005-03-19 11:12
P-1 save files didn't save work	outlnder	Software	1	2003-01-19 23:01
Does the LL test:s factorization save or waste CPU time?	svempasnake	Software	42	2002-10-24 19:27

2010-01-14, 14:50	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1913₁₆ Posts	I still have the relations for 2^941-1 on fast disc, and the next job for the large-memory machine hasn't arrived yet, so I will try refiltering with 80/90/100 bounds and see what the matrix size and the iteration rate look like.

2010-01-29, 02:29	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	Tom, did it pan out? :curious:

2010-02-14, 11:39	#9
debrouxl Sep 2009 977 Posts	After successful complete factorization of two or three RSALS integers filtered with TARGET_DENSITY of 72, I'm raising it to 77.