{"id":4789,"date":"2023-09-11T11:50:24","date_gmt":"2023-09-11T06:20:24","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4789"},"modified":"2023-09-11T11:50:26","modified_gmt":"2023-09-11T06:20:26","slug":"strassens-matrix-multiplication","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/strassens-matrix-multiplication\/","title":{"rendered":"Strassen\u2019s Matrix Multiplication"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-strassens-submatrix\">Approach: Strassen&#8217;s Submatrix<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#pseudocode-of-strassen\u2019s-multiplication\">Pseudocode of Strassen\u2019s multiplication<\/a><\/li><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#applications\">Applications<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Why Strassen&#8217;s matrix algorithm is better than normal matrix multiplication and How to multiply two matrices using Strassen&#8217;s matrix multiplication algorithm?<\/p>\n\n\n\n<p>So the main idea is to use the divide and conquer technique in this algorithm &#8211; <strong>divide matrix A &amp; matrix B into 8 submatrices and then recursively compute the submatrices of C<\/strong>.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Consider the following matrices A and B:\n\nA = |a b|,  B = |e f| and we know A*B = matrix C = |ae+bg af+bh| \n    |c d|       |g h|                              |ce+dg cf+dh|\n\nThere will be 8 recursive calls:\n\na * e\nb * g\na * f\nb * h\nc * e\nd * g\nc * f\nd * h<\/code><\/pre>\n\n\n\n<p>The above strategy is the basic O(N^3) strategy<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"379\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4791 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-1024x379.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-1024x379.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-300x111.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-768x284.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-380x141.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-550x204.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-800x296.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy-1160x429.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Strategy.png 1240w\" ><\/figure>\n\n\n\n<p>Using the Master Theorem with <strong>T(n) = 8T(n\/2) + O(n^2)<\/strong> we still get a runtime of <strong>O(n^3)<\/strong>.<\/p>\n\n\n\n<p>But Strassen came up with a solution where we don\u2019t need 8 recursive calls but can be done in only 7 calls and some extra addition and subtraction operations.<\/p>\n\n\n\n<p>Strassen&#8217;s 7 calls are as follows:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>a * (f - h)\n(a + b) * h\n(c + d) * e\nd * (g - e)\n(a + d) * (e + h)\n(b - d) * (g + h)\n(a - c) * (e + f)<\/code><\/pre>\n\n\n\n<p>Our new matrix C&#8217;s new quadrants<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>matrix C = |p5+p4-p2+p6    p1+p2   |\n           |   p3+p4    p1+p5-p3-p7| <\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"642\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4792 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-1024x642.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-1024x642.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-768x482.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-550x345.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-800x502.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants-1160x728.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/New-quadrants.png 1240w\" ><\/figure>\n\n\n\n<h2 id=\"approach-strassens-submatrix\">Approach: Strassen&#8217;s Submatrix<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>p5+p4-p2+p6 = (a+d)*(e+h) + d*(g-e) - (a+b)*h + (b-d)*(g+h)\n            = (ae+de+ah+dh) + (dg-de) - (ah+bh) + (bg-dg+bh-dh)\n            = ae+bg\n p1+p2 = a*(f-h) + (a+b)*h\n       = (af-ah) + (ah+bh)\n       = af+bh\n p3+p4 = (c+d)*e + d*(g-e)\n       = (ce+de) + (dg-de)\n       = ce+dg \n p1+p5-p3-p7 = a*(f-h) + (a+d)*(e+h) - (c+d)*e - (a-c)*(e+f)\n             = (af-ah) + (ae+de+ah+dh) -(ce+de) - (ae-ce+af-cf)\n             = cf+dh<\/code><\/pre>\n\n\n\n<p>The time complexity using the Master Theorem.<\/p>\n\n\n\n<p><strong>T(n) = 7T(n\/2) + O(n^2)<\/strong> = <strong>O(n^log(7))<\/strong> runtime.<\/p>\n\n\n\n<p>Approximately <strong>O(n^2.8074)<\/strong> which is better than O(n^3)<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"823\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4793 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-1024x823.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-1024x823.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-300x241.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-768x617.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-380x305.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-550x442.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance-800x643.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Performance.png 1079w\" ><\/figure>\n\n\n\n<h3 id=\"pseudocode-of-strassen\u2019s-multiplication\"><span id=\"pseudocode-of-strassens-multiplication\">Pseudocode of Strassen\u2019s multiplication<\/span><\/h3>\n\n\n\n<ul><li>Divide matrix A and matrix B in 4 sub-matrices of size N\/2 x N\/2 as shown in the above diagram.<\/li><li>Calculate the 7 matrix multiplications recursively.<\/li><li>Compute the submatrices of C.<\/li><li>Combine these submatrices into our new matrix C<\/li><\/ul>\n\n\n\n<p><strong>Complexity<\/strong>:<\/p>\n\n\n\n<ul><li>Worst case time complexity: <strong>\u0398(n^2.8074)<\/strong><\/li><li>Best case time complexity: <strong>\u0398(1)<\/strong><\/li><li>Space complexity: <strong>\u0398(logn)<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/6089da2a35aec0a35252 title='Interviewbit Ide snippet\/6089da2a35aec0a35252' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/8c6ae93eaabd8e95f0b4 title='Interviewbit Ide snippet\/8c6ae93eaabd8e95f0b4' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/18c07f43622716e5fd3b title='Interviewbit Ide snippet\/18c07f43622716e5fd3b' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h2 id=\"applications\">Applications<\/h2>\n\n\n\n<p>Generally, Strassen\u2019s Method is not preferred for practical applications for the following reasons.<\/p>\n\n\n\n<ul><li>The constants used in Strassen\u2019s method are high and for a typical application Naive method works better.<\/li><li>For Sparse matrices, there are better methods especially designed for them.<\/li><li>The submatrices in recursion take extra space.<\/li><li>Because of the limited precision of computer arithmetic on noninteger values, larger errors accumulate in Strassen\u2019s algorithm than in Naive Method<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Why Strassen&#8217;s matrix algorithm is better than normal matrix multiplication and How to multiply two matrices&hellip;\n","protected":false},"author":5,"featured_media":4794,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[651],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4789"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4789"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4789\/revisions"}],"predecessor-version":[{"id":23779,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4789\/revisions\/23779"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4794"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4789"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4789"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4789"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}