Parallel matrix multiplication on a linear array with a reconfigurable pipelined bus system
Keqin Li, Victor Ya. Pan · IEEE Transactions on Computers · 2001
The known fast sequential algorithms for multiplying two NxN matrices (over an arbitrary ring) have time complexity O(Nα), where 2α, multiplying two NxN matrices can be performed on a p-processor linear array with a reconfigurable pipelined bus system (LARPBS) in O(Nm/P+(N2/p2α/)log p) time. This is currently the fastest parallelization of the best known sequential matrix multiplication algorithm on a distributed memory parallel system. In particular, for all 12.3755, multiplying two NxN matrices can be performed on a p-processor LARPBS in O(N2.3755/p+(N2)/p0.8419log p) time and linear speedup can be achieved for p as large as O(N2.3755/(log N)6.3262). Furthermore, multiplying two NxN matrices can be performed on an LARPBS with O(Nα) processors in O(log N) time. This compares favorably with the performance on a PRAM.