Singular

D.15.13 modular_lib

Library:

modular.lib

Purpose:

An abstraction layer for modular techniques

Author:

Andreas Steenpass, e-mail: [email protected]

Overview:

This library is an abstraction layer for modular techniques which are well-known to speed up many computations and to be easy parallelizable.
The basic idea is to execute some computation modulo several primes and then to lift the result back to characteristic zero via the farey rational map and chinese remaindering. It is thus possible to overcome the often problematic coefficient swell and to run the modular computations in parallel.
In Singular, modular techniques have been quite successfully employed for several applications. A first implementation was done for Groebner bases in Singular's modstd_lib, a pioneering work by Stefan Steidel. Since the algorithm is basically the same for all applications, this library aims at preventing library authors from writing the same code over and over again by providing an appropriate abstraction layer. It also offers one-line commands for ordinary Singular users who want to take advantage of modular techniques for their own calculations. Thus modular techniques can be regarded as a parallel skeleton of their own.
The terminology (such as 'pTest' and 'finalTest') follows Singular's modstd_lib and [1].

References:

[1] Nazeran Idrees, Gerhard Pfister, Stefan Steidel: Parallelization of Modular Algorithms. Journal of Symbolic Computation 46, 672-684 (2011). http://arxiv.org/abs/1005.5663

Procedures:

D.15.13.1 modular

execute a command modulo several primes and lift the result back to characteristic zero