Some Complexity Results for Matrix Computations on Parallel Processors

Abstract

In this paper it is shown how data movement, rather than arithmetic operations, can be the hmltmg factor in the performance of parallel computers on matrix computations In particular it is proved that for machines with two-dimensional rectangular grid connectivity (such as ILLIAC IV), muittphcatlon and inversion of NxN matrices inherently require O(N) steps, even if the processing elements are not constrained to execute identical instructions.