-   Msieve (
-   -   Msieve announcements (

jasonp 2007-08-02 13:31

Msieve v1.26
Now available. This is primarily to propagate a fix for a fairly major NFS filtering bug. There's also a bug in the linear algebra for people using MSVC (reported by Timmy above), and I'm working on a fix.

The polynomial selection work is ongoing, and harder than I expected. The NFS poly generation code hasn't changed in this released, since the improved stuff isn't close to ready.

Happy factoring,

jasonp 2007-10-02 05:51

Msieve v1.27
Now available. Highlights include:

- increased the allowed input size to 235 digits (MAX_MP_WORDS=25). No more recompiles to handle big SNFS jobs

- added memory and performance optimizations to the linear algebra code. The result should use 15% less memory and should be slightly (~2%) faster

- a lot more messing around with GNFS polynomial selection, but nothing ready for testing yet

- fixes for a few little things

People have spent a lot of time pounding on the NFS postprocessing code in the last few months, so I think I should spend more time trying to improve it. The square root should be more efficient and multithreaded, I'll look at 64-bit optimizations for the linear algebra, and the NFS filtering has to go on a memory diet. There are also some interesting algorithmic tricks from the sparse matrix literature that I want to explore.

Happy factoring,

jasonp 2007-10-04 03:41

Msieve v1.28
I just posted this emergency release. It fixes the bug referenced above as well as some 64-bit compile errors.

jasonp 2007-10-28 16:35

Msieve v1.29
Now available. Highlights include:

- Major changes to the Lanczos routines. The new version incorporates linear algebra checkpoint and restart; checkpoints happen for large matrices only, once every 2-3 hours and whenever the library is interrupted. The demo binary can restart from a previous checkpoint with the -ncr instead of the -nc2 option. The updated source is also slightly faster

- Major overhaul of the NFS linear algebra driver. Nothing visible at the user level, but it's a lot better now. If you want to use this library version with a previously-completed factorization, you should redo any postprocessing from scratch

- Allowed the large prime bound, and the number of relations used, in the NFS filtering to be specified from the command line. See the new usage in the demo binary

- Miscellaneous fixes all over

The plan for the next version is the same. People are starting to throw NFSNET-size jobs at the NFS postprocessing, and this is quite close to the limit of what the current library can handle. It needs to scale much better, and that means incorporating industrial-strength external libraries instead of my stupid toy subroutines.

- the linear algebra also needs to move to a thread-pool type implementation instead of spawn-and-join. I also will be experimenting with matrix-reordering techniques that should isolate very small dense matrix blocks, and if there are enough of these in the typical matrix then the code can be made much faster and more memory efficient

- the NFS filtering is near the limit of what it can handle. The memory use is terrible on 64-bit systems because pointers are twice as large, and filtering is taking forever because the data structures used are sized suboptimally and have bad worst-case behavior. I'll be experimenting with the Judy library to fix this

- (if time allows) optimize/multithread the FFTs used in the NFS square root. I would love to use FFTW but it's not worth changing the license

Please be on the lookout for suspicious behavior from the new code.

Happy factoring,

jasonp 2007-11-16 08:23

Msieve v1.30
Now available. This is a bug fix release, since an unusually large number of fixes have piled up in the last week or so. The only new feature is the more efficient NFS filtering embodied in the code I posted earlier.

The goals for the next version have not changed.

Happy factoring,

jasonp 2007-12-14 05:39

Msieve v1.31
Now available. Highlights include:

- Provision is made for compiling and running GMP-ECM. If you have the GMP and GMP-ECM libraries, and run make with 'ECM=1' at the end, then the demo will compile a wrapper and link those libraries to it. All factoring inputs will get P+-1 and ECM to the 15-digit level (it takes about 1 second), and running the msieve binary with '-e' will cause it to expend more P+-1 and ECM effort (up to the 35 digit level) before aborting and running the main QS code. The cutoffs are somewhat tuned to give up as early as possible, and to scale the amount of work done so that ECM never takes up more than about 10% of the total runtime. The official binary uses GMP 4.2.2 compiled with --enable-fat, so it should run at high speed on any x86 system (but watch out for crashes, in case I did something wrong and your system is incompatible with my test rig).

- A lot of work on NFS line sieving. The new line siever implements the optimizations described [url=""]here[/url] and has been reformatted to be more readable. Some of this stuff is still experimental

- Lots of internal library changes and cleanups

Based on discussions in the GGNFS mailing list, the next step is going to involve merging part of this msieve version into the GGNFS codebase. The standalone msieve library will still contain NFS code (I will probably prefer to use it for testing), but it's time to merge these two development efforts. GGNFS contains highly efficient NFS polynomial selection and sieving, while msieve has very good postprocessing, and it would be a waste of everyone's time to reinvent the things each package doesn't have. Plus, the GGNFS project has many (>>1) developers, who should be able to continue maintaining my code if I ever put it down. Once that's done, the next step is to make the NFS square root require less memory (than the linear algebra, at least). Doing this right is going to be harder than I thought, so it may take a while.

Happy factoring,

jasonp 2007-12-16 18:52

Msieve v1.32
Now available. I wanted to get this out the door because another NFSNET job is imminent, and there's a potential for a big linear algebra speedup in this version. The windows binary probably will not be much faster, and my 2-CPU linux box is only 4% faster, but multi-core linux machines are reported to be enormously sped up using multithreaded lanczos with this patch.

The GGNFS codebase uses this version of msieve as a baseline.

Happy factoring,

jasonp 2008-01-13 19:47

Msieve v1.33
Now available. Highlights include:

- optimizations in the early stages of NFS filtering
- fixes for handling savefiles larger than 4GB in windows
- a lot of bug fixes all over the library
- a new extra-cool web page (now using Web 1.0 technology)

Be on the lookout for suspicious behavior with this new version, it
has many invasive changes.

Happy factoring,

jasonp 2008-03-23 04:49

Msieve 1.34
Now available. Highlights include:

- Added a native port of the NFS polynomial selection tools from GGNFS. This is a major work in progress, and has a lot of rough edges right now, but it should allow equivalent polynomials to what GGNFS can manage. Note that I've removed the assembly code and many of the obscure parts of the original version; on the plus side, this allows full optimization and makes the code thread-safe, but on the minus side it's currently 2.5x slower than the version in GGNFS. The extra code gets compiled if you use 'make' with ECM=1

- Added tweaks to the NFS filtering that many of you have been kind enough to test out

- Forced the NFS square root to always use IEEE double precision, since trying to guess whether you're using 53-bit or 64-bit registers has caused too many painful debugging episodes. Also added what I think is a fix for the NFS square root problems people have reported, when building with 64-bit MSVC (it's in related code). Can somebody try a square root with the latest version?

- Added many QS cleanups (not faster, just less hackish)

- Added a number of fixes and tweaks from several contributors

Assuming nobody discovers an emergency problem, I'm going to be either working on miscellaneous long-range msieve things, or not.

Happy factoring,

jasonp 2008-04-14 05:03

Msieve v1.35
Now available. Highlights include

- A lot of work on NFS polynomial selection (still a major work in progress)

- A bunch of fixes for Visual Studio. This should fix porting problems in the last version, upgrade the build project to use MSVC 9.0, and should also fix a bug in the NFS square root that showed up in MSVC but also occurs with gcc (thanks to the MSVC users for helping out with this one).

Future work will continue the overhaul of the polynomial selection, and if time allows I'll experiment with using 128-bit vectors to speed up the linear algebra.

Please post followups in one of the other threads in this subforum. Happy factoring,


jasonp 2008-05-17 20:26

Msieve v1.36
Now available. Highlights include:

- a lot of work on NFS polynomial selection; all polynomials are now saved in a file, though none of the other features (limited ranges, limited time) is supported yet

- a lot of NFS fixes and tweaks

- improved cache size detection

I've tried to change the linear algebra to use vectors wider than 64 bits, but could not get the runtime to be faster than the 64-bit time.

The next version should continue current work, and should incorporate GMP-ECM v6.2

Happy factoring,

All times are UTC. The time now is 09:12.

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