|
Since V2.28, a parallel version of the main algorithm to compute
the (ideal) class group of an
algebraic number field is available.
The main feature of the new algorithm is that the gathering of relations
is fully parallelised: each worker does an independent random walk
with short products of random ideals and searches for smooth relations
in terms of the factor basis (the set of prime ideals with norm up to
some bound). When enough relations are gathered, the master process
uses linear algebra operations on the large integer relation matrix to
compute the class group.
The relation matrix is now also represented internally by the sparse
matrix type, which allows much larger factor bases than could be handled
previously, because the memory usage is much less than before, and this
is particularly important when there are many workers each of which
handles its own local relation matrix.
Although the relation gathering generally dominates the computation,
the linear algebra phase at the end can be very non-trivial too,
as it involves integer matrix algorithms operating on the relation
matrix, which can be huge. (For some inputs, the relation gathering
may be relatively much quicker than usual.)
As usual, one first uses SetNthreads and optionally StartWorkers
to select the number of cores/workers. Then the ClassGroup function
can be called on a number field or order.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|