Sparse matrix computations on the hypercube and related networks (Q1328088)

The author shows how some parallel techniques which have been proposed for matrix addition, matrix multiplication, Gauss elimination and other related computations on sparse matrices, algorithms which run on shared memory MIMD computers, can be modified for an implementation on local memory machines. These new algorithms are designed for the hypercube and related networks. An algorithm is described for solving the vector equation \(Ax= b\), where \(A\) is a sparse matrix. It is shown that, under certain assumptions, on a hypercube with \(p\) processors these algorithms achieve a speedup proportional to \(p/\log p\).