Hypercube matrix multiplication

DOI10.1016/0167-8191(93)90064-RMaRDI QIDQ686633zbMATH OpenFDO

Authors P. A. Nelson

Publication date 10 October 1993

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(93)90064-R

zbMATH Keywords

hypercubesmatrix multiplication algorithmparallel computersperformance

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Review text

A matrix multiplication algorithm for parallel computers (hypercubes) is given. The algorithm has running times of \(O(n)\) and \(O(\log n)\) for \(n^ 2\) and \(n^ 3/2\) processors. The sub matrices are sent in a single communication to directly connected processors in the hypercube and are also involved in sequential matrix multiplication at each processor. Experimental evidence is provided, showing that the proposed algorithm performs well on both \(iPSC/1\) and \(iPSC/2\) hypercubes.

Recommendations

• Communication-efficient matrix multiplication on hypercubes
• PARALLEL MATRIX MULTIPLICATION ON THE CONNECTION MACHINE
• Parallel algorithms and architectures for matrix multiplication
• Sparse matrix computations on the hypercube and related networks
• Matrix and vector operations on hypercube parallel processors

Cited in

(19)

• A method for exploiting communication/computation overlap in hypercubes
• Distributed evaluation of an iterative function for all object pairs on an SIMD hypercube
• Parallel matrix inversion on a subcube-grid
• Sparse matrix computations on the hypercube and related networks
• Parallel algorithms and architectures for matrix multiplication
• Transposition of banded matrices in hypercubes: A nearly isotropic task
• PARALLEL MATRIX MULTIPLICATION ON THE CONNECTION MACHINE
• Measuring the performance for parallel matrix multiplication algorithm
• scientific article; zbMATH DE number 4096756 (Why is no real title available?)
• scientific article; zbMATH DE number 44563 (Why is no real title available?)
• A RECURRENCE-FREE VARIANT OF STRASSEN'S ALGORITHM ON HYPERCUBE∗
• scientific article; zbMATH DE number 852332 (Why is no real title available?)
• Parallel Algorithms and Subcube Embedding on a Hypercube
• scientific article; zbMATH DE number 278851 (Why is no real title available?)
• Hypercubes As Direct Products
• Matrix and vector operations on hypercube parallel processors
• On the performance of parallel matrix factorisation on the hypermesh
• Communication-efficient matrix multiplication on hypercubes
• An algorithm for multiplication of concatenated matrices

This page was built for publication: Hypercube matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686633)