Tight bounds on one-pass map-reduce algorithms for matrix multiplication

Loading...
Thumbnail Image
Authors
Nagar, Ashita
Advisors
Ramanan, Prakash
Issue Date
2015-12
Type
Thesis
Keywords
Research Projects
Organizational Units
Journal Issue
Citation
Abstract

MapReduce is an effi t parallel computation model introduced by Google, for performing many large-scale computations, including matrix multiplication. Matrix multiplication can be done using either an one-pass or a two-pass MapReduce algorithm; these algorithms have been extensively studied. In this thesis, we studied the tradeoff between communication cost and parallelism, for one-pass algorithms for matrix multiplication. We measured communication cost using the replication rate r, as in the literature. We measured parallelism either by reducer size q as in the literature, or by a new parameter, namely, reducer workload w. First, we provided matching upper and lower bounds on qr, for the multi- plication of sparse rectangular matrices; this extends a previously-known result for dense square matrices. Then, we provided matching upper and lower bounds on wr2, for the multiplication of sparse rectangular matrices.

Table of Contents
Description
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
Publisher
Wichita State University
Journal
Book Title
Series
PubMed ID
DOI
ISSN
EISSN