Show simple item record

dc.contributor.advisorRamanan, Prakash
dc.contributor.authorDeng, Minhao
dc.descriptionThesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
dc.description.abstractConsider the multiplication C = A x B of two n x n matrices. A straight-forward sequential algorithm for computing the product takes ?(n 3 ) time. Strassen [17] presented an algorithm that takes ?(n lg 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81. Now, consider the implementation of these two algorithms (straight-forward 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) mapReduce passes. In this thesis, 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, for a total of 2 lg n + 1 passes. We show that Part I can be implemented in 2 passes, with total work ?(n lg 7), and reducer size and reducer workload o(n). We believe that Part III can also be implemented, with small reducer size and workload, in a constant number of passes (possibly 4 passes); this is future work.
dc.format.extentx, 34 pages
dc.publisherWichita State University
dc.rightsCopyright 2017 by Minhao Deng All Rights Reserved
dc.subject.lcshElectronic dissertation
dc.titleMapreduce implementation of Strassen's algorithm 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 --)

Show simple item record