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

dc.contributor.advisorRamanan, Prakash
dc.contributor.authorNagar, Ashita
dc.date.accessioned2016-06-15T16:56:25Z
dc.date.available2016-06-15T16:56:25Z
dc.date.issued2015-12
dc.descriptionThesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
dc.description.abstractMapReduce 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.
dc.format.extentviii, 23 p
dc.identifier.othert15081
dc.identifier.urihttp://hdl.handle.net/10057/12109
dc.language.isoen_US
dc.publisherWichita State University
dc.rightsAshita Nagar
dc.rightsCopyright 2015 Ashita Nagar
dc.subject.lcshElectronic thesis
dc.titleTight bounds on one-pass map-reduce algorithms for matrix multiplication
dc.typeThesis
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
t15081_Nagar.pdf
Size:
555.04 KB
Format:
Adobe Portable Document Format
Description: