@inproceedings{efaf773f1d6d466682685484fd01da2f,
title = "On matrix multiplication using array processors",
abstract = "Array processor models in the past have assumed constant storage per processor. Such an assumption leads to a lower bound of Ω(n2) time complexity to multiply two n×n matrices on a one-dimensional array processor. In this paper it is shown that relaxing the restriction of constant storage per processor leads to a lower bound of Ω(n√n) time complexity to multiply two n×n matrices on a one-dimensional array processor. Furthermore, an optimal matrix multiplication algorithm is described for such an array that uses O(n√n) processors and requires O(n√n) time. The algorithm is well suited for fault-tolerant VLSI implementation.",
author = "Varman, \{P. J.\} and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} 1985, Springer-Verlag.; 12th International Colloquium on Automata, Languages and Programming, ALP 1985 ; Conference date: 15-07-1985 Through 19-07-1985",
year = "1985",
doi = "10.1007/BFb0015774",
language = "English",
isbn = "9783540156505",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "487--496",
editor = "Wilfried Brauer",
booktitle = "Automata, Languages and Programming - 12th Colloquium",
}