{"id":4912,"date":"2013-04-23T17:29:10","date_gmt":"2013-04-23T16:29:10","guid":{"rendered":"http:\/\/www.walkingrandomly.com\/?p=4912"},"modified":"2013-04-29T14:44:26","modified_gmt":"2013-04-29T13:44:26","slug":"matrix-multiplication-speed-up-trick-on-matlab","status":"publish","type":"post","link":"https:\/\/walkingrandomly.com\/?p=4912","title":{"rendered":"Matrix multiplication speed-up trick on MATLAB"},"content":{"rendered":"<p>I was recently working on some <a href=\"http:\/\/www.mathworks.co.uk\/products\/matlab\/\">MATLAB<\/a> code with Manchester University&#8217;s David McCormick.\u00a0 Buried deep within this code was a function that was called many,many times&#8230;taking up a significant amount of overall run time.\u00a0 We managed to speed up an important part of this function by almost a factor of two (on his machine) <strong>simply by inserting two brackets<\/strong>&#8230;.a new personal record in overall application performance improvement per number of keystrokes.<\/p>\n<p>The code in question is hugely complex, but the trick we used is really very simple.\u00a0 Consider the following MATLAB code<\/p>\n<pre>&gt;&gt; a=rand(4000);\r\n&gt;&gt; c=12.3;\r\n&gt;&gt; tic;res1=c*a*a';toc\r\nElapsed time is 1.472930 seconds.<\/pre>\n<p>With the insertion of just two brackets, this runs quite a bit faster on my Ivy Bridge quad-core desktop.<\/p>\n<pre>&gt;&gt; tic;res2=c*(a*a');toc\r\nElapsed time is 0.907086 seconds.<\/pre>\n<p>So, what&#8217;s going on? Well, we think that in the first version of the code, MATLAB first calculates <strong>c*a<\/strong> to form a temporary matrix (let&#8217;s call it temp here) and then goes on to find<strong> temp*a&#8217;<\/strong>.\u00a0 However, in the second version, we think that MATLAB calculates <strong>a*a&#8217;<\/strong> first and in doing so it takes advantage of the fact that <a href=\"http:\/\/math.stackexchange.com\/questions\/28395\/is-it-faster-to-multiply-a-matrix-by-its-transpose-than-ordinary-matrix-multipli\">the result of multiplying a matrix by its transpose will be symmetric<\/a> which is where we get the speedup.<\/p>\n<p>Another demonstration of this phenomena can be seen as follows<\/p>\n<pre>&gt;&gt; a=rand(4000);\r\n&gt;&gt; b=rand(4000);\r\n&gt;&gt; tic;a*a';toc \r\nElapsed time is 0.887524 seconds.\r\n&gt;&gt; tic;a*b;toc  \r\nElapsed time is 1.473208 seconds.\r\n&gt;&gt; tic;b*b';toc\r\nElapsed time is 0.966085 seconds.<\/pre>\n<p>Note that the symmetric matrix-matrix multiplications are faster than the general, non-symmetric one.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I was recently working on some MATLAB code with Manchester University&#8217;s David McCormick.\u00a0 Buried deep within this code was a function that was called many,many times&#8230;taking up a significant amount of overall run time.\u00a0 We managed to speed up an important part of this function by almost a factor of two (on his machine) simply [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[53,11,7],"tags":[],"class_list":["post-4912","post","type-post","status-publish","format-standard","hentry","category-making-matlab-faster","category-matlab","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3swhs-1he","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/4912","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4912"}],"version-history":[{"count":8,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/4912\/revisions"}],"predecessor-version":[{"id":4925,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=\/wp\/v2\/posts\/4912\/revisions\/4925"}],"wp:attachment":[{"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4912"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4912"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/walkingrandomly.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4912"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}