Communication and Matrix Computations on Large Message Passing Systems

This paper is concerned with the consequences for matrix computations of having a rather large number of general purpose processors, say ten or twenty thousand, connected in a network in such a way that a processor can communicate only with its immediate neighbors. Certain communication tasks associated with most matrix algorithms are defined and formulas developed for the time required to perform them under several communication regimes. The results are compared with the times for a nominal $n^3$ floating point operations. The results suggest that it is possible to use a large number of processors to solve matrix problems at a relatively fine granularity, provided fine grain communication is available. Additional figures are available at ftp thales.cs.umd.edu in the directory pub/reports (Also cross-referenced as UMIACS-TR-88-81