I get

[code]
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (4 threads)
memory use: 879.8 MB
linear algebra at 0.0%, ETA 17h49m46197 dimensions (0.0%, ETA 17h49m)
linear algebra completed 2845775 of 2846197 dimensions (100.0%, ETA 0h 0m)
lanczos halted after 45009 iterations (dim = 2845971)
recovered 32 nontrivial dependencies
BLanczosTime: 60345
[/code]

using a version of msieve obtained by downloading lanczos-opt.tgz from msieve.sourceforge.org and building it. So no messages about the partitioning, and a couple of percent slower than the last time I ran this matrix.

There is a lanczos-opt directory at the top level that should not be there; are you sure you zipped up branches/lanczos-opt ? (The note about the partitioning should occur right after the initial matrix build and right before the text you quote)

I also spent some time yesterday feeding the matrix to a high-quality graph partitioning library (Metis is really nice), and it appeared to do quite a good job. Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.

[QUOTE=jasonp;204169]There is a lanczos-opt directory at the top level that should not be there; are you sure you zipped up branches/lanczos-opt ? (The note about the partitioning should occur right after the initial matrix build and right before the text you quote)

I also spent some time yesterday feeding the matrix to a high-quality graph partitioning library (Metis is really nice), and it appeared to do quite a good job. Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.[/QUOTE]

Do you mean SVN184 which should not be there?

Is SVN185 part of the lanczos-opt brach or is it the main "branch"?

SVN 185 was a fix to branches/lanczos-opt; the repository copy in SVN 184 actually does not have the reordering code at all.

You can go to 'SVN Browse' in the 'Develop' menu on sourceforge, then click on a particular revision number and see exactly which files in the repository are affected.

matrix step of a c133 with 1.43:

[CODE]
Fri Feb 5 06:41:40 2010 Msieve v. 1.43
Fri Feb 5 06:41:40 2010 random seeds: 35296e5c f31b436b
Fri Feb 5 06:41:40 2010 factoring 5335366387062594103281599506619078830675568770597674764072096981029494235489350569590888813457656823560321885511353040519174462222557 (133 digits)
Fri Feb 5 06:41:41 2010 no P-1/P+1/ECM available, skipping
Fri Feb 5 06:41:41 2010 commencing number field sieve (133-digit input)
Fri Feb 5 06:41:41 2010 R0: -43590657298344915874817701
Fri Feb 5 06:41:41 2010 R1: 467844431521753
Fri Feb 5 06:41:41 2010 A0: 3052516397340263636960237838715200
Fri Feb 5 06:41:41 2010 A1: 29100578051888094818724416280
Fri Feb 5 06:41:41 2010 A2: 36523592624186545117942
Fri Feb 5 06:41:41 2010 A3: -123602480596394341
Fri Feb 5 06:41:41 2010 A4: -18461007596
Fri Feb 5 06:41:41 2010 A5: 33900
Fri Feb 5 06:41:41 2010 skew 863842.14, size 7.089820e-13, alpha -7.025253, combined = 4.837199e-11
Fri Feb 5 06:41:41 2010
Fri Feb 5 06:41:41 2010 commencing relation filtering
Fri Feb 5 06:41:41 2010 estimated available RAM is 1985.8 MB
Fri Feb 5 06:41:41 2010 commencing duplicate removal, pass 1
Fri Feb 5 06:44:27 2010 found 3339904 hash collisions in 14676617 relations
Fri Feb 5 06:45:06 2010 added 62981 free relations
Fri Feb 5 06:45:06 2010 commencing duplicate removal, pass 2
Fri Feb 5 06:45:46 2010 found 3492350 duplicates and 11247248 unique relations

<snip>

Feb 5 06:55:03 2010 commencing linear algebra
Fri Feb 5 06:55:04 2010 read 1428636 cycles
Fri Feb 5 06:55:08 2010 cycles contain 4538304 unique relations
Fri Feb 5 06:56:02 2010 read 4538304 relations
Fri Feb 5 06:56:10 2010 using 20 quadratic characters above 134217690
Fri Feb 5 06:56:42 2010 building initial matrix
Fri Feb 5 06:58:32 2010 memory use: 595.5 MB
Fri Feb 5 06:58:34 2010 read 1428636 cycles
Fri Feb 5 06:58:42 2010 matrix is 1428459 x 1428636 (435.0 MB) with weight 135788023 (95.05/col)
Fri Feb 5 06:58:42 2010 sparse part has weight 96885657 (67.82/col)
Fri Feb 5 06:59:07 2010 filtering completed in 2 passes
Fri Feb 5 06:59:07 2010 matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb 5 06:59:07 2010 sparse part has weight 96880921 (67.84/col)
Fri Feb 5 06:59:24 2010 read 1428021 cycles
Fri Feb 5 06:59:26 2010 matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb 5 06:59:26 2010 sparse part has weight 96880921 (67.84/col)
Fri Feb 5 06:59:26 2010 saving the first 48 matrix rows for later
Fri Feb 5 06:59:27 2010 matrix is 1427796 x 1428021 (418.5 MB) with weight 108661836 (76.09/col)
Fri Feb 5 06:59:27 2010 sparse part has weight 95415355 (66.82/col)
Fri Feb 5 06:59:27 2010 matrix includes 64 packed rows
Fri Feb 5 06:59:27 2010 using block size 65536 for processor cache size 4096 kB
Fri Feb 5 06:59:36 2010 commencing Lanczos iteration (2 threads)
Fri Feb 5 06:59:36 2010 memory use: 415.9 MB
Fri Feb 5 06:59:47 2010 linear algebra at 0.1%, ETA 5h13m
Fri Feb 5 12:58:11 2010 lanczos halted after 22580 iterations (dim = 1427795)
Fri Feb 5 12:58:15 2010 recovered 29 nontrivial dependencies
Fri Feb 5 12:58:15 2010 [B]BLanczosTime: 21792[/B][/CODE]

Same c133 on the same C2D laptop with SVN185:

[CODE]Fri Feb 5 22:20:34 2010 Msieve v. 1.44
Fri Feb 5 22:20:34 2010 random seeds: eeced92d 786ed506
Fri Feb 5 22:20:34 2010 factoring 5335366387062594103281599506619078830675568770597674764072096981029494235489350569590888813457656823560321885511353040519174462222557 (133 digits)

<snip>

Fri Feb 5 22:33:54 2010 commencing linear algebra
Fri Feb 5 22:33:55 2010 read 1428636 cycles
Fri Feb 5 22:33:59 2010 cycles contain 4538304 unique relations
Fri Feb 5 22:34:53 2010 read 4538304 relations
Fri Feb 5 22:35:02 2010 using 20 quadratic characters above 134217690
Fri Feb 5 22:35:34 2010 building initial matrix
Fri Feb 5 22:37:25 2010 memory use: 595.5 MB
Fri Feb 5 22:37:27 2010 read 1428636 cycles
Fri Feb 5 22:37:35 2010 matrix is 1428459 x 1428636 (435.0 MB) with weight 135788023 (95.05/col)
Fri Feb 5 22:37:35 2010 sparse part has weight 96885657 (67.82/col)
Fri Feb 5 22:38:00 2010 filtering completed in 2 passes
Fri Feb 5 22:38:00 2010 matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb 5 22:38:00 2010 sparse part has weight 96880921 (67.84/col)
Fri Feb 5 22:38:18 2010 read 1428021 cycles
Fri Feb 5 22:38:19 2010 matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb 5 22:38:19 2010 sparse part has weight 96880921 (67.84/col)
Fri Feb 5 22:38:19 2010 saving the first 48 matrix rows for later
Fri Feb 5 22:38:20 2010 matrix is 1427796 x 1428021 (418.5 MB) with weight 108661836 (76.09/col)
Fri Feb 5 22:38:20 2010 sparse part has weight 95415355 (66.82/col)
Fri Feb 5 22:38:20 2010 matrix includes 64 packed rows
Fri Feb 5 22:38:20 2010 using block size 65536 for processor cache size 4096 kB
Fri Feb 5 22:38:29 2010 commencing Lanczos iteration (2 threads)
Fri Feb 5 22:38:29 2010 memory use: 415.9 MB
Fri Feb 5 22:38:40 2010 linear algebra at 0.1%, ETA 5h12m
Sat Feb 6 04:44:09 2010 lanczos halted after 22579 iterations (dim = 1427795)
Sat Feb 6 04:44:14 2010 recovered 29 nontrivial dependencies
Sat Feb 6 04:44:14 2010 [B]BLanczosTime: 22220[/B]
[/CODE]

Seems SVN185 is slower.

I made some tests on C149_113_58 (SNFS difficulty 200) on Core 2 Duo T7200, 2 GB RAM (but that didn't work out, see below) and Core 2 Duo T7600, 3 GB RAM:

SVN185:
[code]Msieve v. 1.44
Thu Feb 4 18:02:13 2010
random seeds: c08d3a90 82f55b5b
factoring 58726049878536391557011831786679470473096960150546862137088288968129115887237799139638233172513763094056500204963331970846586616031413324264998772683 (149 digits)
searching for 15-digit factors
commencing number field sieve (149-digit input)
R0: -624332378391008467754527498760580235264
R1: 38358611506121121577937
A0: 1442897
A1: 0
A2: 0
A3: 0
A4: 0
A5: 195112
skew 1.49, size 1.169368e-14, alpha -1.135403, combined = 6.064487e-12

commencing linear algebra
read 3259953 cycles
cycles contain 10103761 unique relations
read 10103761 relations
using 20 quadratic characters above 536870768
building initial matrix
memory use: 1326.4 MB
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
filtering completed in 1 passes
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
permuting matrix for faster multiplies
matrix is 3259753 x 3259953
sparse core is 2313986 x 1549672
graph has 11341062 edges
memory use: 160.22 MB
max edge weight is 36
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
saving the first 48 matrix rows for later
matrix is 3259705 x 3259953 (960.0 MB) with weight 242856059 (74.50/col)
sparse part has weight 219071221 (67.20/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (2 threads)
memory use: 975.0 MB
linear algebra at 0.0%, ETA 33h37m59953 dimensions (0.0%, ETA 33h37m)
^Cnear algebra completed 6836 of 3259953 dimensions (0.2%, ETA 33h18m)
received signal 2; shutting down

lanczos halted after 111 iterations (dim = 7024)
BLanczosTime: 976
elapsed time 00:16:17[/code]

trunk (SVN 189, I think):

[code]Msieve v. 1.44
Thu Feb 4 18:19:19 2010
random seeds: 4c27aea9 6f01d9ad
factoring 58726049878536391557011831786679470473096960150546862137088288968129115887237799139638233172513763094056500204963331970846586616031413324264998772683 (149 digits)
searching for 15-digit factors
commencing number field sieve (149-digit input)
R0: -624332378391008467754527498760580235264
R1: 38358611506121121577937
A0: 1442897
A1: 0
A2: 0
A3: 0
A4: 0
A5: 195112
skew 1.49, size 1.169368e-14, alpha -1.135403, combined = 6.064487e-12

commencing linear algebra
read 3259953 cycles
cycles contain 10103761 unique relations
read 10103761 relations
using 20 quadratic characters above 536870768
building initial matrix
memory use: 1326.4 MB
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
filtering completed in 1 passes
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
saving the first 48 matrix rows for later
matrix is 3259705 x 3259953 (960.0 MB) with weight 242856059 (74.50/col)
sparse part has weight 219071221 (67.20/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (2 threads)
memory use: 974.9 MB
linear algebra at 0.0%, ETA 33h18m59953 dimensions (0.0%, ETA 33h18m)
^Cnear algebra completed 7343 of 3259953 dimensions (0.2%, ETA 33h35m)
received signal 2; shutting down

lanczos halted after 119 iterations (dim = 7530)
BLanczosTime: 806
elapsed time 00:13:28[/code]

I guess I need to mention that despite the "memory use: 974.9 MB" and "memory use: 975.0 MB"; traces, consistent wrt. each other, the memory consumption of the reordering-enabled binary was at least 700 MB (!) higher than that of the other binary.
On the T7200 with 2 GB RAM, the reordering-enabled binary was killed by Linux's OOM killer before it could display "commencing Lanczos iteration (2 threads)", so I switched to the T7600.

jasonp, if you think that it would be useful for testing the algorithm (all of our tasks are beyond 2M cycles), I can send you how to get the raw sieving data of the RSALS grid :smile:

For some reason, I can't seem to be allowed to edit my own posts (even after logging out and logging back in), so I'm creating a new post.
[EDIT: the Edit button appears on this post right after I've made it - is there a time limit ?]


[quote]Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.[/quote]If the total memory requirements of the other graph partitioning code are lower than the requirements of the rest of the msieve LA pass, it can remain a valid option (barring e.g. licensing issues, of course).

[QUOTE=debrouxl;204761][EDIT: the Edit button appears on this post right after I've made it - is there a time limit ?][/QUOTE]

Yes there is: 1 hour (unless you're a moderator).