CALYPSO

We present a package of parallel algorithms for multiple precision arithmetic, implemented by using a message-passing model of computation. These algorithms are organized in an object oriented library and perform parallel arithmetic in $Z$, $Q$, and $Z_p$.\parThe library has a layered structure which provides portability and the possibility of extending the code easily. In the bottom layer we implement fundamental parallel algorithms which are machine dependent. Starting from integer multiplication, we developed different parallel Karatsuba-type and FFT-based schemes, including the integer 3-primes and floating-point FFT algorithms. These multiplication algorithms allowed us to design a parallel Newton method for division. Parallel algorithms for modular arithmetic result by using both Montgomery’s and classical arithmetic.\parWe designed these algorithms under a message-passing model of computation. These are implemented on different parallel platforms, targeting both distributed memory machines, such as massively parallel processing systems and networks of workstations, and shared memory architectures. We developed both architecture dependent and architecture independent algorithms by using standard interfaces such as the Message Passing Interface, MPI.\parOn top of this layer we provide a convenient interface to the user which allows a sequential programming style, while each algorithm is executed in parallel. At this level it is possible for the user to implement high level parallel algorithms, such as the GCD, which are machine independent. \parFinally we integrated our package in a computer algebra system, which uses a sequential frontend for interactive use, and a parllel backend for computation. \parWe have called this package CALYPSO, a sort of package acronym for Computer Algebra Library for Parallel Symbolic Computation.