Ideal Class Group of Algebraic Number Fields

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.

V2.28, 13 July 2023