TY - JOUR
AU - Limongelli, C.
AU - Pirastu, R.
PY - 2012/03/07
Y2 - 2023/03/31
TI - p-adic Arithmetic and Parallel Symbolic Computation: An Implementation for Solving Linear Systems Over Rationals
JF - COMPUTING AND INFORMATICS
JA - Comput. Inform.
VL - 15
IS - 1
SE - Articles
DO -
UR - https://www.cai.sk/ojs/index.php/cai/article/view/710
SP - 35-62
AB - In this work we describe the use of truncated p-adic expansion of handling rational numbers by parallel algorithms for symbolic computation. As a case study we propose a parallel implementation for solving linear systems over the rationals. <br />The parallelization is based on a multiple homomorphic image technique and the result is recovered by a parallel version of the Chinese remainder algorithm. Using a MIMD machine, we compare the proposed implementation with the classical modular arithmetic, showing that truncated p-adic arithmetic is a feasible tool for solving systems of linear equations working directly over rational numbers. A safe algorithm for computing the p-adic division operation is proposed. <br />The implementation leads to a speedup of up to seven by ten processors with respect to the sequential implementation.
ER -