PARALLEL COMPUTATION OF Ax AND ATx
Venkat N. Venkatakrishnan · International Journal of High Speed Computing · 1994
This paper describes how to carry out the matrix-vector multiplications Ax and ATx on parallel computers where A is a sparse matrix arising from the discretization of partial differential equations. Two partitionings of the sparse matrix suitable for parallel computers are discussed. They are derived by interpreting the sparse matrix as a graph. One of the techniques partitions the graph of the matrix by finding edge separators. The other technique partitions the graph by finding vertex separators. We claim that in either case computing ATx is no more complex than computing Ax. Results from the implementation of the matrix-vector multiplications on the Intel iPSC/860 are presented which substantiate the claim. Results from an efficient implementation on the Cray Y-MP/1 are also presented for comparison.