{"id":25954,"date":"2017-05-31T15:08:14","date_gmt":"2017-05-31T09:38:14","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25954"},"modified":"2017-05-31T15:08:14","modified_gmt":"2017-05-31T09:38:14","slug":"strassens-matrix-multiplication","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/strassens-matrix-multiplication\/","title":{"rendered":"Strassen\u2019s Matrix Multiplication"},"content":{"rendered":"

Given two square matrices <\/a>A and B of size n x n each, find their Strassen\u2019s Matrix Multiplication.<\/span><\/p>\n

Naive Method<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dvoid%20multiply(int%20A%5B%5D%5BN%5D%2C%20int%20B%5B%5D%5BN%5D%2C%20int%20C%5B%5D%5BN%5D)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20k%20%3D%200%3B%20k%20%3C%20N%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%2B%3D%20A%5Bi%5D%5Bk%5D*B%5Bk%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity of above method is O(N3<\/sup>).<\/p>\n[ad type=\u201dbanner\u201d]\n

Divide and Conquer<\/strong><\/p>\n

Following is simple Divide and Conquer method to multiply two square matrices.<\/p>\n

    \n
  1. Divide matrices A and B in 4 sub-matrices of size N\/2 x N\/2 as shown in the below diagram.<\/li>\n
  2. Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.<\/li>\n<\/ol>\n

    \"Strassen\u2019s<\/p>\n

    In the above method, we do 8 multiplications for matrices of size N\/2 x N\/2 and 4 additions. Addition of two matrices takes O(N2<\/sup>) time. So the time complexity can be written as<\/p>\n

    T(N) = 8T(N\/2) + O(N2<\/sup>)  \r\n\r\nFrom Master's Theorem, time complexity of above method is O(N3<\/sup>)\r\nwhich is unfortunately same as the above naive method.<\/pre>\n
    Simple Divide and Conquer also leads to O(N3<\/sup>), can there be a better way?<\/strong><\/p>\n[ad type=\u201dbanner\u201d]\nIn the above divide and conquer method, the main component for high time complexity is 8 recursive calls. The idea of Strassen\u2019s method<\/strong> is to reduce the number of recursive calls to 7. Strassen\u2019s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N\/2 x N\/2 as shown in the above diagram, but in Strassen\u2019s method, the four sub-matrices of result are calculated using following formulae.<\/p>\n
    \"Strassen\u2019s<\/p>\n
    Time Complexity of Strassen\u2019s Method<\/strong>
    \nAddition and Subtraction of two matrices takes O(N2<\/sup>) time. So time complexity can be written as<\/p>\n
    T(N) = 7T(N\/2) +  O(N2<\/sup>)\r\n\r\nFrom Master's Theorem, time complexity of above method is \r\nO(NLog7<\/sup>) which is approximately O(N2.8074<\/sup>)\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n
    Generally Strassen\u2019s Matrix Multiplication Method is not preferred for practical applications for following reasons<\/p>\n
      \n
    1. The constants used in Strassen\u2019s method are high and for a typical application Naive method works better.<\/li>\n
    2. For Sparse matrices, there are better methods especially designed for them.<\/li>\n
    3. The submatrices in recursion take extra space.<\/li>\n
    4. Because of the limited precision of computer arithmetic on noninteger values, larger errors accumulate in Strassen\u2019s algorithm than in Naive Method<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
      Strassen\u2019s Matrix Multiplication-Divide and Conquer-Given two square matrices A and B of size n x n each, find their multiplication .<\/p>\n","protected":false},"author":1,"featured_media":26233,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73719],"tags":[76351,76343,76346,76344,76347,76338,76342,76339,76340,76352,76350,76348,76341,76349,76345],"class_list":["post-25954","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-divide-and-conquer","tag-c-source-code-for-strassens-matrix-multiplication","tag-how-to-remember-strassens-matrix-multiplication","tag-strassen-matrix-multiplication-4-4-example","tag-strassen-matrix-multiplication-algorithm","tag-strassen-matrix-multiplication-for-4x4","tag-strassens-algorithm-pseudocode","tag-strassens-matrix-multiplication-3x3-example","tag-strassens-matrix-multiplication-4x4-example","tag-strassens-matrix-multiplication-algorithm","tag-strassens-matrix-multiplication-algorithm-implementation","tag-strassens-matrix-multiplication-for-4x4-matrix-example-in-c","tag-strassens-matrix-multiplication-for-nxn-matrix-in-c","tag-strassens-matrix-multiplication-program-in-c","tag-strassens-matrix-multiplication-program-in-c-using-divide-and-conquer","tag-strassens-matrix-multiplication-program-in-c-using-recursion"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25954","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25954"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25954\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/26233"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25954"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25954"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25954"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}