linear algebra and threshold phenomena

[jasonp]

ArXiv paper

Many have noticed that the linear algebra problem produced by the heavy-duty factoring algorithms behaves strangely when the problem size increases, and that it becomes impossible to solve if you are not careful. These guys actually analyze sparse Gauss elimination as a thermodynamic problem and work out thresholds beyond which Gauss elimination becomes hard. In particular, their work has implications for NFS filtering.

Unfortunately they work on a simplified version of the full problem, and it isn't obvious after a quick reading that there's anything here that msieve can use.

[R.D. Silverman]

Originally Posted by jasonp

ArXiv paper

Many have noticed that the linear algebra problem produced by the heavy-duty factoring algorithms behaves strangely when the problem size increases, and that it becomes impossible to solve if you are not careful. These guys actually analyze sparse Gauss elimination as a thermodynamic problem and work out thresholds beyond which Gauss elimination becomes hard. In particular, their work has implications for NFS filtering.

Unfortunately they work on a simplified version of the full problem, and it isn't obvious after a quick reading that there's anything here that msieve can use.

A long ago, I actually implemented Odlyzko's and LaMacchia'a ideas
about sparse Gaussian elimination in order to implement filtering.

I found that the clique methods developed by CWI produced better
results, so now I use their code instead.

[jasonp]

Originally Posted by R.D. Silverman

I found that the clique methods developed by CWI produced better
results, so now I use their code instead.

Those clique methods are a prelude to the merge phase, which looks exactly like Gauss elimination even in CWI's code. (More details in my CADO slides). So the results above could still be relevant.