View article

The interrelationships among processors, storage within a processor, internal bandwidth, and time complexity of matrix multiplication of a model for a fault-tolerant VLSI matrix multiplier are discussed. Lower bounds on the time complexity and the number of processors required are determined as a function of the storage within a processor and the internal bandwidth. A generalized algorithm is employed to match these bounds for arbitrary storage within a processor and arbitrary bandwidth. It is found that the time and area complexities and the asymptotic complexity of the number of processors used in several previous linear-array algorithms can be obtained as special cases of the present generalized algorithm. (R.R.)