Parallel p-adic method for solving linear systems of equations

✍ Scribed by Ç.K. Koç

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 488 KB
• Volume: 23
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(97)00062-8

✦ Synopsis

We present a parallel algorithm for an exact solution of an integer linear system of equations using the single modulus p-adic expansion technique. More specifically, we parallelize an algorithm of Dixon, and present our implementation results on a distributed-memory multiprocessor. The parallel algorithm presented here can be used together with the multiple moduli algorithms and parallel Chinese remainder algorithms for fast computation of the exact solution of a system of linear equations with integer entries. 0 1997 Elsevier Science B.V.