Efficient parallel solution of sparse systems of linear diophantine equations
Mark W. Giesbrecht · 1997
. An efficient new algorithm is presented for solving large sparse systems of linear Diophantine equations which is substantially and provably faster than those previously known in both a sequential and parallel implementation. This is accomplished by reducing the problem of finding an integer solution to that of finding a very small number of rational solutions of Toeplitz perturbations of the original system. We then employ the Block-Wiedemann algorithm to solve these perturbed systems efficiently in parallel. On an input matrix A 2 Z n\\Thetan of rank r and w 2 Z n\\Theta1 , the algorithm finds a v 2 Z n\\Theta1 such that Av = w with about O(r(r log kAk \\Delta + log kwk \\Delta )=N) matrix-vector products by A modulo single-word primes, on N r(r log kAk \\Delta +log kwk \\Delta ) processors. Here kAk \\Delta = max ij jA ij j and kwk \\Delta = max i jw i j. Additionally, about O ` r 2 + rn(r log kAk \\Delta + log kwk \\Delta ) N + n(r log kAk \\Delta + log kwk \\Delta ) min(n; N)...