Cited By
View all- Misra CBhattacharya SGhosh S(2022)Stark: Fast and Scalable Strassen’s Matrix Multiplication Using Apache SparkIEEE Transactions on Big Data10.1109/TBDATA.2020.29773268:3(699-710)Online publication date: 1-Jun-2022
Six Pass MapReduce Implementation of Strassen's Algorithm for Matrix Multiplication
Article No.: 7, Pages 1 - 6
Abstract
Consider the multiplication of two n x n matrices. A straight-forward sequential algorithm for computing the product takes Θ(n3) time. Strassen [21] presented an algorithm that takes Θ(nlg 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81.
Now, consider the implementation of these two algorithms (straightforward and Strassen) in the mapReduce framework. Several papers have studied mapReduce implementations of the straight-forward algorithm; this algorithm can be implemented using a constant number (typically, one or two) of mapReduce passes. In this paper, we study the mapReduce implementation of Strassen's algorithm.
If we unwind the recursion, Strassen's algorithm consists of three parts, Parts I--III. Direct mapReduce implementations of the three parts take lg n, 1 and lg n passes, respectively; total number of passes is 2 lg n + 1. In a previous paper [7], we showed that Part I can be implemented in 2 passes, with total work Θ(nlg 7), and reducer size and reducer workload o(n). In this paper, we show that Part III can be implemented in three passes. So, overall, Strassen's algorithm can be implemented in six passes, with total work Θ(nlg 7), and reducer size and reducer workload o(n).
References
[1]
F. N. Afrati, A. D. Sarma, S. Salihoglu and J. D. Ullman. Upper and Lower Bounds on the Cost of a MapReduce Computation, VLDB, 2013, pp. 277--288.
[2]
Amazon Elastic Compute Cloud (Amazon EC2), Amazon Inc, 2008.
[3]
G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz. Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds, Proc. SPAA, 2012, pp. 77--79.
[4]
G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, and O. Schwartz. Communication Optimal Parallel Algorithm for Strassen's Matrix Multiplication, Proc. SPAA, 2012, pp. 193--204.
[5]
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, MIT Press, 2009.
[6]
J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters, CACM, 51 (2008), pp. 107--113.
[7]
M. Deng and P. Ramanan. MapReduce Implementation of Strassen's Algorithm for Matrix Multiplication, BeyondMR, 2017.
[8]
S. Ghemawat, H. Gobioff and S-T. Leung. The Google File System, ACM SIGOPS Review, 37 (2003), pp. 29--43.
[9]
W. Hasan and R. Motwani. Optimization Algorithms for Exploiting the Parallelism--Communication Tradeoff in Pipelined Parallelism, VLDB, 1994, pp. 36--47.
[10]
C-H. Huang, J. R. Johnson and R. W. Johnson. A Tensor Product Formulation of Strassen's Matrix Multiplication Algorithm, Appl. Math. Lett., 3 (1990), pp. 67--71.
[11]
D. Irony, S. Toledo and A. Tiskin. Communication Lower Bounds for Distributed-Memory Matrix Multiplication, J. Parallel and Distributed Computing, 64 (2004), pp. 1017--1026.
[12]
J. Jájá. An Introduction to Parallel Algorithms. Addison--Wesley, 1992.
[13]
H. J. Karloff, S. Suri and S. Vassilvitskii. A Model of Computation for MapReduce, ACM SODA, 2010, pp. 938--948.
[14]
M. Krishnan and J. Nieplocha. SRUMMA: A Matrix Multiplication Algorithm Suitable for Clusters and Scalable Shared Memory Systems, Proc. Parallel and Distributed Processing Symp., 2004, pp. 70--71.
[15]
R. Lämmel. Google's MapReduce Programming Model Revisited, Sci. Computer Programming, 70 (2008), pp. 1--30.
[16]
J. Leskovec, A. Rajaraman and J. D. Ullman. Mining of Massive Datasets. Cambridge Univ. Press, 2014.
[17]
B. Lipshitz, G. Ballard, J. Demmel, and O. Schwartz. Communication-Avoiding Parallel Strassen: Implementation and Performance, Proc. Super Computing, 2012.
[18]
A. Pietracaprina, G. Pucci, M. Riondato, F. Silvestri and E. Upfal. Space-Round Tradeoffs for MapReduce Computations, ACM Supercomputing, 2012, pp. 235--244.
[19]
P. Ramanan and A. Nagar. Tight Bounds on One- and Two-Pass MapReduce Algorithms for Matrix Multiplication, BeyondMR, 2016.
[20]
K. Shvachko, H. Kuang, S. Radia and R. Chansler. The Hadoop Distributed File System, Mass Storage Systems and Technologies (MSST), 2010, pp. 1--10.
[21]
V. Strassen. Gaussian Elimination is not Optimal, Numer. Math. 13 (1969), pp. 354--356.
[22]
J. D. Ullman. Designing Good MapReduce Algorithms, XRDS: Crossroads, 19 (2012), pp. 30--34.
[23]
T. White. Hadoop--The Definitive Guide: Storage and Analysis at Internet Scale, 2nd ed, O'Reilly, 2011.
Index Terms
- Six Pass MapReduce Implementation of Strassen's Algorithm for Matrix Multiplication
Recommendations
MapReduce Implementation of Strassen's Algorithm for Matrix Multiplication
BeyondMR'17: Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and BeyondConsider the multiplication of two n×n matrices. A straight-forward sequential algorithm for computing the product takes Θ(n3) time. Strassen [20] presented an algorithm that takes Θ(n1g 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81.
...
Implementation of Strassen's algorithm for matrix multiplication
Supercomputing '96: Proceedings of the 1996 ACM/IEEE conference on SupercomputingIn this paper we report on the development of an efficient and portable implementation of Strassen's matrix multiplication algorithm for matrices of arbitrary size. Our technique for defining the criterion which stops the recursions is more detailed ...
Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication
AbstractAs proposed by Karppa and Kaski (in: Proceedings 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019) a novel “broken" or "opportunistic" matrix multiplication algorithm, based on a variant of Strassen’s algorithm, and used this to develop ...
Comments
Information & Contributors
Information
Published In
June 2018
54 pages
ISBN:9781450357036
DOI:10.1145/3206333
- Conference Chairs:
- Foto Afrati,
- Jacek Sroka,
- Program Chair:
- Ke Yi,
- Publications Chair:
- Jan Hidders
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 15 June 2018
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SIGMOD/PODS '18
Sponsor:
Acceptance Rates
Overall Acceptance Rate 19 of 36 submissions, 53%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 123Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
Cited By
View all- Misra CBhattacharya SGhosh S(2022)Stark: Fast and Scalable Strassen’s Matrix Multiplication Using Apache SparkIEEE Transactions on Big Data10.1109/TBDATA.2020.29773268:3(699-710)Online publication date: 1-Jun-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in