Show simple item record

dc.contributor.advisorRamanan, Prakash
dc.contributor.authorNagar, Ashita
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.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

Files in this item


This item appears in the following Collection(s)

  • CE Theses and Dissertations
    Doctoral and Master's theses authored by the College of Engineering graduate students
  • EECS Theses and Dissertations
    Collection of Master's theses and Ph.D. dissertations completed at the Dept. of Electrical Engineering and Computer Science
  • Master's Theses
    This collection includes Master's theses completed at the Wichita State University Graduate School (Fall 2005 -- current) as well as selected historical theses.

Show simple item record