Parallel complexity of matrix multiplication
Matrix multiplication is a kernel of many numerical algorithms, thus finding efficient and parallel solution to this problem is one of the most important topics in scientific computing. In this paper, the parallel complexity of multiplying two matrices (using the standard row/column method) on parallel distributed-memory computers is studied. The author considers three basic aspects of designing distributed algorithms, namely local computational tasks, the initial data layout, and the communication schedule with respect to LogP, the well known theoretical model of parallel distributed-memory computers, which allows to consider the basic characteristics of an interconnection network regardless of its physical structure. The main result describes the lower bounds on running time of distributed matrix multiplication. Then several algorithms with running times within a constant factor of the lower bounds are described and analyzed. It should be pointed out that this excellent paper provides some important facts about designing optimal distributed-memory parallel algorithms. For example it defines several classes of algorithms, data layouts and communication schedules which collectively produce the optimal running times.
- PARALLEL MATRIX MULTIPLICATION ON THE CONNECTION MACHINE
- Scalable parallel matrix multiplication on distributed memory parallel computers
- Communication lower bounds for distributed-memory matrix multiplication
- Parallel matrix multiplication: a systematic journey
- scientific article; zbMATH DE number 4072257
- Matrix-vector multiplication: Parallel algorithms and architectures
- A balanced submatrix merging algorithm for multiprocessor architectures
- How to express a parallel sum of k matrices
- Scalable parallel matrix multiplication on distributed memory parallel computers
- Parallel algorithms and architectures for matrix multiplication
- Communication lower bounds for distributed-memory matrix multiplication
- Parallelizing Strassen's method for matrix multiplication on distributed-memory MIMD architectures
- Automatic parallelization of cycles with two-dimensional arrays for distributed memory supercomputers (on the example of matrix multiplication)
- To the role of decomposition strategy in high parallel algorithms
- Parallel matrix multiplication: a systematic journey
- Studying and implementing parallel matrix multiplication algorithms
- PARALLEL MATRIX MULTIPLICATION ON THE CONNECTION MACHINE
- On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
- scientific article; zbMATH DE number 4215271 (Why is no real title available?)
- Your favorite parallel algorithms might not be as fast as you think
- scientific article; zbMATH DE number 4072257 (Why is no real title available?)
- scientific article; zbMATH DE number 1223727 (Why is no real title available?)
- scientific article; zbMATH DE number 1275860 (Why is no real title available?)
- scientific article; zbMATH DE number 741169 (Why is no real title available?)
- scientific article; zbMATH DE number 4003520 (Why is no real title available?)
- Work-Preserving Speed-Up of Parallel Matrix Computations
- Experimental evaluation of automatic array alignment in parallelized matlab
- Locality estimation of parallel algorithm for distributed memory computers
- Communication-efficient matrix multiplication on hypercubes
- Communication complexity of PRAMs
This page was built for publication: Parallel complexity of matrix multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404305)
