Revision 69df44f7b79e82ded025ccbee4b1153c8b844204 authored by Emmanuel Thomé on 24 November 2010, 11:15:57 UTC, committed by Emmanuel Thomé on 24 November 2010, 11:15:57 UTC
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/cado-nfs/trunk@441 3eaf19af-ecc0-40f6-b43f-672aa0c71c71
1 parent 879dcae
TODO
General:
========
* improve the use of free relations: currently we generate free relations
up to the algebraic factor base bound (alim). We can do much better:
(a) after the purge phase (removal of singletons), find all remaining
primes on the algebraic side
(b) determine those primes for which the algebraic polynomial completely
splits into linear factors
(c) add free relations for those primes
In particular when using the lattice siever, all special-q's for which f(x)
completely splits should appear in (b).
* portability: we should check improve portability on Win64, where
long has 32 bits (http://technet.microsoft.com/en-us/library/bb496995.aspx).
See http://gmplib.org/list-archives/gmp-discuss/2008-June/003243.html and
the 3 possible models (most C programs in CADO-NFS assume LP64):
* LP64 defines "int" as 32 bits and "long" as 64 bits.
* LLP64 defines "int" and "long" as 32 bits, and an additional type
(usually called "long long") as 64 bits.
* ILP64 defines "int" and "long" as 64 bits.
* reintroduce the "skip" parameter: the idea is that we remove some columns
corresponding to dense prime ideals before the linear algebra (or even
before merge or purge), and we "recover" those ideals with "characters".
Thus the matrix has smaller weight, and hopefully bwc will be faster.
Polyselect:
===========
* use the other definition of the E-value, see formula (5.8) page 87 of
Murphy's thesis. Currently CADO-NFS uses the definition on page 99,
where Murphy says that the former definition is more reliable.
Purge:
======
* in the first pass, we can identify all algebraic ideals corresponding to a
given prime p, and even identify them to the ideal p on the rational side,
to reduce the memory usage. Some singletons will not be identified in this
first pass, but later passes (with fewer remaining relations) will remove
them.
Sieve:
======
* An (a,b)-pair where the sieving leaves a value not exceeding the sieve
report threshold on both the rational side and the algebraic side
goes to the cofactorization phase. However, if on both sides the
remaining sieve value is just a little below the respective threshold,
then this (a,b)-pair has little chance of becoming a relation:
since the lambda value is increased a little to account for rounding
errors, one of the two cofactors may be too large, and even if they
aren't, we know they're both pretty large so it's unlikely that both
split completely into primes < lpb.
We can add another threshold, a combined lambda
clambda < alambda + rlambda
and add the condition that the sum of remaining values after sieving
must not exceed lpb^clambda.
That should reduce the number of sieve survivors that don't become
relations, thus reducing pressure on the cofactorization phase,
without losing too many relations.
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...