Deakin University
Browse
li-parallelizingstrassens-1995.pdf (955.9 kB)

Parallelizing Strassen's method for matrix multiplication on distributed-memory MIMD architectures

Download (955.9 kB)
Version 2 2024-06-04, 01:53
Version 1 2019-07-22, 09:53
journal contribution
posted on 2024-06-04, 01:53 authored by CC Chou, YF Deng, Gang LiGang Li, Y Wang
We 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 applications

Volume

30

Pagination

49-69

Location

Amsterdam, The Netherlands

ISSN

0898-1221

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

1995, Elsevier Ltd

Issue

2

Publisher

Elsevier

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC