Parallel solution of arbitrarily sparse linear systems (Q1823617)

A system of linear algebraic equations \(Kx=f\), which is rewritten into the form \(x=Ax+c\), is iteratively solved by a parallel algorithm using the formula \(x^{(i+1)}=Ax^{(i)}+c.\) K, A are large arbitrarily sparse \(N\times N\) matrices and x, f are N vectors. It is supposed that the sequence of iterates converges to the solution. The usefulness of a network of processing elements (PE's) equal in number to the total number of non-zero elements in A is shown. Supposing that the communication time between PE's grows slowly with the number of messages simultaneously in a network, the iteration time grows as the logarithm of the number of PE's. A comparison of the results and the improvement of the algorithm by \textit{D. A. Reed} and \textit{M. L. Patrick} [ibid. 2, 45-67 (1985; Zbl 0599.65017)] is presented. The performance of three proposed networks of PE's on this algorithm is analyzed. All networks have the topology of the cube connected cycles graph. The comparison indicates that the Boolean vector machine network would have the superior performance to other two parallel networks.