• Login
    View Item 
    •   Shocker Open Access Repository Home
    • Graduate Student Research
    • ETD: Electronic Theses and Dissertations
    • Master's Theses
    • View Item
    •   Shocker Open Access Repository Home
    • Graduate Student Research
    • ETD: Electronic Theses and Dissertations
    • Master's Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Mapreduce implementation of Strassen's algorithm for matrix multiplication

    View/Open
    Thesis (186.0Kb)
    Date
    2017-05
    Author
    Deng, Minhao
    Advisor
    Ramanan, Prakash
    Metadata
    Show full item record
    Abstract
    Consider 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.
    Description
    Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
    URI
    http://hdl.handle.net/10057/14465
    Collections
    • CE Theses and Dissertations
    • EECS Theses and Dissertations
    • Master's Theses

    Browse

    All of Shocker Open Access RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsBy TypeThis CollectionBy Issue DateAuthorsTitlesSubjectsBy Type

    My Account

    LoginRegister

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV