Why only three large primes

[R.D. Silverman]

Originally Posted by jasonp

I understand that (you can't code it up and not realize that). But I think it's valid to ask if there are ways to tweak NFS parameters that speed up the algorithm for input sizes of interest.

Of course there are ways. That's what my recent paper was all about.

[xilman]

Originally Posted by jasonp

It's a sign of my ignorance that I don't consider filtering to be easy at all :)

I belive Bob to have been guilty of a terminolgical inexactitude. Filtering is "easy" in the sense that it takes much less computation than either sieving or linear algebra.

In my experience, creating and implementing efficient filtering algorithms is far from easy. The simple algorithms are either not very good at filtering or very memory inefficient or both. Most implementations of good algorithms use far too much memory, IMO, and I've spent some time tweaking the CWI filter code to make it run on commonly available machines.

Paul

[R.D. Silverman]

Originally Posted by xilman

I belive Bob to have been guilty of a terminolgical inexactitude. Filtering is "easy" in the sense that it takes much less computation than either sieving or linear algebra.

In my experience, creating and implementing efficient filtering algorithms is far from easy. The simple algorithms are either not very good at filtering or very memory inefficient or both. Most implementations of good algorithms use far too much memory, IMO, and I've spent some time tweaking the CWI filter code to make it run on commonly available machines.

Paul

I agree that implementations of good algorithms (e.g. clique methods) take
tons of memory. But they take so little TIME that one can afford to do
an out-of-core implementation using temporary files for storage.

[fivemack]

What I'm saying is:

Suppose I have sieved against significantly too large a factor base size; say the n(L) primes less than L.

What happens if I run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? If I sieved allowing two large primes plus the special-Q, I will have lots of relations in which I have two large primes, plus the special-Q, plus one or two primes between S and L; the primes between S and L will seldom be singletons because the number of relations is significantly greater than n(L).

I wasn't sure whether the answer would be 'you get a uselessly dense matrix' or 'you don't get a matrix'; doing the runs using the ggnfs matrix-building is tending not to give me a matrix at all, but I am losing huge numbers of relations because they're not allowed to have more than three large algebraic primes.

I know that, asymptotically, filtering is cheap.


I may be confused by the sequence of events when you use the GGNFS suite; that *does* distinguish between factor-base primes and other primes, until it has built a matrix of height the size of the requested factor base, and then 'prunes' that matrix. You're describing filtering, as far as I can tell, as a process which takes a pile of relations and gives you a matrix, without ggnfs/matbuild's two-phase structure.

I'm using 'factor-base primes' to mean 'primes which label the rows of the matrix'; they have nothing to do with the sieving phase.

[R.D. Silverman]

Originally Posted by fivemack

What I'm saying is:

Suppose I have sieved against significantly too large a factor base size; say the n(L) primes less than L.

What happens if I run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S?



If I sieved allowing two large primes plus the special-Q, I will have lots of relations in which I have two large primes, plus the special-Q, plus one or two primes between S and L; the primes between S and L will seldom be singletons because the number of relations is significantly greater than n(L).

I wasn't sure whether the answer would be 'you get a uselessly dense matrix' or 'you don't get a matrix'; doing the runs using the ggnfs matrix-building is tending not to give me a matrix at all, but I am losing huge numbers of relations because they're not allowed to have more than three large algebraic primes.

I know that, asymptotically, filtering is cheap.

What does " run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? " MEAN??

I can't make sense of it. Do you mean that while filtering, you
throw away relations that have (say) 3 or more primes larger than some
fixed bound? I can't imagine why such a thing should be necessary.
Once you start filtering, a relation is a relation is a relation.
The distinction between factor base primes and large primes VANISHES.
Why is this so hard?

You say "they're not allowed to have more than three large algebraic primes."
I ask: why not? Is this a restriction of the particular implementation you
are using? If so, then FIX IT. This restriction is not necessary. Indeed,
I can't think why it might even be put in filter code. The filtering code
SHOULD NOT CARE about the sizes of primes that appear in relations.
They should all be treated identically/

Are you complaining about limitations of your software or asking about
how to select parameters for good performance??

If GGNFS has unnecessary restrictions, then FIX them. You sound more as if
you are complaining about some brain dead restrictions of GGNFS than you
are asking about parameterizations.

[jasonp]

Originally Posted by R.D. Silverman

What does " run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? " MEAN??

He means 'choose a factor base for sieving that is very large, then run the filtering for all primes whose size is some number that happens to be smaller than the largest factor base prime'.

Tom, you don't need a two-phase process to construct a matrix; you really can start with a pile of relations and produce a matrix directly. It's useful to have a two-phase process because filtering only deals implicitly with big primes, and the matrix can be squeezed down a little after it is formed and you can count the number of empty rows.

Whether a factor base exists in the background is a detail that is specific to the implementation, i.e. GGNFS has a relation structure that separates the primes found by sieving from those found by nonsieving means, and it has entries for three of the latter only.

[fivemack]

As far as I can see, GGNFS does not build the matrix from the input relations by filtering according to the model in Cavallar's paper of 2000; it uses an entirely different procedure, in which small primes and large primes are treated separately, and in which all the data structures are set up such that a relation can have no more than three 'large' primes on either side. I suspect what it's doing is closer to the 'structured Gaussian elimination' of the 1990s large sparse linear algebra papers.

The small-prime bound for this procedure is a configurable parameter, usually set to the factor-base bound for the sieving, and I was just wondering what happened if you changed that parameter.

I'm afraid we've been talking at cross purposes, and am sorry to have wasted your time; I agree that Cavallar's algorithm does not depend on the size of the primes appearing in the relation. The correct response to ggnfs's limitations is almost-surely to use msieve instead, and msieve's relationset->matrix step is something like Cavallar's algorithm, in which the parameter I was seeking to optimise in ggnfs's implementation doesn't exist.

[fivemack]

Sorry to have bothered you all; the more I look into this, the deeper the deficiencies of ggnfs's relations -> matrix stage look. It seems that substantial oversieving causes some very nasty slowdown in the matrix-tidying phase, which can't be sensible.

All glory to Jason for implementing something more capable!