li-parallelizingstrassens-1995.pdf (955.9 kB)
Parallelizing Strassen's method for matrix multiplication on distributed-memory MIMD architectures
journal contribution
posted on 1995-07-01, 00:00 authored by C C Chou, Y F Deng, Gang LiGang Li, Y WangWe present a parallel method for matrix multiplication on distributed-memory MIMD architectures based on Strassen's method. Our timing tests, performed on a 56-node Intel Paragon, demonstrate the realization of the potential of the Strassen's method with a complexity of 4.7 M2.807 at the system level rather than the node level at which several earlier works have been focused. The parallel efficiency is nearly perfect when the processor number is the power of 7. The parallelized Strassen's method seems always faster than the traditional matrix multiplication methods whose complexity is 2M3 coupled with the BMR method and the Ring method at the system level. The speed gain depends on matrix order M: 20% for M ≈ 1000 and more than 100% for M ≈ 5000.
History
Journal
Computers and mathematics with applicationsVolume
30Issue
2Pagination
49 - 69Publisher
ElsevierLocation
Amsterdam, The NetherlandsPublisher DOI
Link to full text
ISSN
0898-1221Language
engPublication classification
C1.1 Refereed article in a scholarly journalCopyright notice
1995, Elsevier LtdUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC