<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Kamallesh U on Medium]]></title>
        <description><![CDATA[Stories by Kamallesh U on Medium]]></description>
        <link>https://medium.com/@kamalu211?source=rss-2693eaca3b62------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*5decASQpwjxLY-SF8df-DA.jpeg</url>
            <title>Stories by Kamallesh U on Medium</title>
            <link>https://medium.com/@kamalu211?source=rss-2693eaca3b62------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 00:04:03 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kamalu211/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Why Strassen’s algorithm is not used in Deep Learning]]></title>
            <link>https://medium.com/@kamalu211/why-strassens-algorithm-is-not-used-in-deep-learning-ca8f0932355f?source=rss-2693eaca3b62------2</link>
            <guid isPermaLink="false">https://medium.com/p/ca8f0932355f</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[time-complexity]]></category>
            <category><![CDATA[matrix-multiplication]]></category>
            <category><![CDATA[strassen]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Kamallesh U]]></dc:creator>
            <pubDate>Wed, 07 Aug 2024 08:46:37 GMT</pubDate>
            <atom:updated>2024-08-07T08:59:12.139Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Xz8FnqfO73_pt-WFl4KArA.png" /></figure><h3>Introduction</h3><p>Deep learning is a subset of machine learning that uses neural networks. To train neural networks, two steps of information transfer take place, feedforward followed by backpropagation. In both of these transfer techniques, a large number of multiplication operations is required. To quickly calculate these multiplications during training and prediction, matrix multiplication is used.</p><p>In 1968, German mathematician Volken Strassen managed to improve the traditional matrix multiplication and reduce its time complexity from O(n³) to O(n^ 2.803) by reducing the number of multiplications required. This might seem like a boon to the field of deep learning, especially given the size of modern neural networks, but turns out it is still better to use naive matrix multiplication over Strassen’s matrix multiplication in present-day applications.</p><h3>Naive Matrix Multiplication</h3><p>To multiply two matrices using naive matrix multiplication, we multiply each row of the first matrix with each column of the second matrix and sum the products to get each element of the resultant matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PormLDCj6oAKZqnUc1WP5A.png" /></figure><p>For matrix multiplication of two 2x2 matrices using the naive method, we require 8 multiplications and 4 additions. This can be generalized for two 2ⁿ x 2ⁿ matrices as 2³ⁿ multiplications and 2²ⁿ(2ⁿ-1) additions. We can see that this number exponentially scales up as the size of the matrix increases.</p><h3>Strassen’s Matrix Multiplication</h3><p>Strassen managed to reduce the number of multiplications required for 2x2 matrices down to 7, instead of 8. He had taken two matrices A and B, and calculated for the equations I to VII using the formulas given below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/772/1*27mTee-leq3XECXspSDJ3Q.png" /><figcaption>Formulas from Volker Strassen: Gaussian Elimination is not Optimal(1968)</figcaption></figure><p>Using the values derived from the above formulas for equations I to VII, he computed the elements of AB, i.e., matrix multiplication of A and B, which are shown as C₁₁, C₂₁, C₁₂, and C₂₂.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/656/1*lSjlcBtp3wdiAAWY_ew-vg.png" /><figcaption>Formulas from Volker Strassen: Gaussian Elimination is not Optimal(1968)</figcaption></figure><p>Upon considering all the operations, we can observe that there are only 7 multiplications but 18 additions (or subtractions). This reduces the theoretical time complexity because as the numbers get larger, Strassen’s algorithm takes much lesser time than the naive method.</p><p>However, one condition to note is the matrix has to be of dimensions 2ⁿx2ⁿ to go about implementing Strassen’s algorithm. The algorithm is applied recursively until it calculates for matrices of dimensions 2 x 2 and then works its way up from there. At each step of the recursion, it cuts out 1 multiplication, thus compounding its benefits and reducing the time taken.</p><h3>Disadvantages of using Strassen’s algorithm for Deep Learning</h3><h4>Size Mismatch</h4><p>The crossover point at which Strassen’s algorithm becomes significantly faster is generally around 10,000x10,000 or larger. The matrices at the individual layers of neural networks are mostly smaller as there are generally much lesser than 10,000 neurons in a layer.</p><p>Additionally, for fully connected layers, the matrices, that have to be multiplied, have the dimensions (batch_size x input_features) and (input_features x output_features). As the matrices are not of the same dimensions, they are either subdivided or padded to bring the dimensions to the form of 2ⁿ, which tends to take more time and resources.</p><h4>Memory</h4><p>Strassen’s algorithm requires additional memory allocation for its recursive calls. For large matrices, this significantly increases the memory usage. GPUs have limited memory bandwidth and Strassen’salgorithm requires frequent memory transfer between GPU and CPU. This increases the chance of cache misses and memory fragmentation.</p><h4>Precision and Stability</h4><p>As the number of additions and subtractions has increased, each operation increases the chance of small rounding errors due to the limitations of floating-point arithmetic. These errors can accumulate over time and result in larger numeric errors. This can cause divergence in training, reduce model accuracy, and give inconsistent results across different runs.</p><h4>Parallelization</h4><p>Strassen’s algorithm doesn’t map well to GPUs and here is why. GPUs excel at performing multiple simple operations in parallel, but the recursive nature of the algorithm and the dependence on previous operations, make it very complicated and inefficient to parallelize. The entire computing capability of the GPU is not utilized. The general structure of the algorithm doesn’t align with the SIMD (Single Instruction Mulitple Data) paradigm that GPUs use.</p><p>On the other hand, traditional matrix multiplication can easily be parallelized by breaking it down into parts and thus maps perfectly to the architecture of GPUs. GPUs are used widely in deep learning applications to speed up the training and prediction process and Strassen’s algorithm’s incompatibility with GPUs is a huge disadvantage.</p><p>In conclusion, while Strassen’s algorithm might be theoretically better, for the practical use cases of deep learning, standard matrix multiplication outperforms it cause of better accommodation of size mismatch, lesser memory requirement, better precision and stability, and most importantly, compatibility with GPUs.</p><h3>Beyond Strassen: Other Breakthroughs in Matrix Multiplication</h3><h4>Winograd’s algorithm (1971)</h4><p>Winograd’s algorithm slightly improved Strassen’s method by reducing the number of additions while maintaining the same O(n^ 2.807) time complexity.</p><h4>Karstadt and Schwarts algorithm (2017)</h4><p>Karstadt and Schwartz proved that matrix multiplication can be performed in O(n^ 2.373) time, providing a significant theoretical improvement over Strassen’s algorithm.</p><blockquote>As of April 2024, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(<em>n</em>2.371552) time, given by Williams, Xu, Xu, and Zhou. This improves on the bound of O(<em>n</em>2.3728596) time, given by Alman and Williams. However, this algorithm is a galactic algorithm because of the large constants and cannot be realized practically.⁵</blockquote><p>The current state of the art is O(n^ 2.371552) as obtained by Williams, Xu, Xu, and Zhou but similar to Strassen’s algorithms, this algorithm is also not practical.</p><h4>AlphaTensor (2022)</h4><p>DeepMind introduced AlphaTensor, a neural network that used Deep Reinforcement Learning to explore, invent, and prove novel matrix multiplication algorithms. It started with no knowledge of existing matrix multiplication algorithms and was trained in a self-play mode, which is traditionally observed in reinforcement learning. It managed to achieve admirable results and drove researchers to make further improvements to Strassen’s method.</p><blockquote>On 4x4 matrices, AlphaTensor unexpectedly discovered a solution with 47 multiplication steps, an improvement over the 49 required with Strassen’s algorithm of 1969, albeit restricted to mod 2 arithmetic. Similarly, AlphaTensor solved 5x5 matrices with 96 rather than Strassen’s 98 steps.⁵</blockquote><p>Alpha Tensor is a true testament to how AI systems can help push the boundaries of invention in the fields of mathematics, physics, and applied sciences.</p><h3>Final thoughts</h3><p>Strassen’s algorithm was recently mentioned in one of my undergrad lectures and it got me wondering about how it works. As I tried to dig deeper on how exactly it is used in neural networks, I realized that it is not being used and is infeasible.</p><p>As someone who loves building deep learning applications and understanding how it works under the hood, I was really fascinated by the amount of thought multiple mathematicians have put over the years into matrix multiplication. The AlphaTensor system has inspired me to use reinforcement learning to approach more innovations in constrained problem spaces.</p><p>I hope that as mathematicians and researchers continue to improve matrix multiplication algorithms and hardware engineers build more specialized hardware, one day we will manage to gain practical advantages from these algorithms on specialized hardware.</p><p>If you have any interesting thoughts or feedback to share, I’m all yours!</p><p>Kamallesh</p><p><em>[1]: Volker Strassen (1968). Gaussian Elimination is not Optimal</em></p><p><em>[2]: Winograd, Schmuel (1971). Linear Algebra and Its Applications. </em><strong><em>4</em></strong><em> (4): 381–388.</em></p><p><em>[3]: Karstadt, Elaye; Schwartz, Oded (2017). Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA ’17. pp. 101–110.</em></p><p><em>[4]: Eduardo Alvarez. </em><a href="https://towardsdatascience.com/a-i-mathematician-a-simplified-look-at-deepminds-alphatensor-feeeac90c9f3"><em>A.I. Mathematician? A Simplified Look at DeepMind’s AlphaTensor</em></a></p><p><em>[5]: Wikipedia. </em><a href="https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm"><em>https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm</em></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ca8f0932355f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>