Cohn, Kleinberg, Szegedy, and Umans provided a group theoretic approach to this task that re-derives an earlier algorithm for it that Virginia Williams improved upon in 2011.
Cohn, Kleinberg, Szegedy, and Umans provided a group theoretic approach to this task that re-derives an earlier algorithm for it that Virginia Williams improved upon in 2011. However, that algorithm is useless in practice since it is only faster than other algorithms for impractically large inputs. The Coppersmith–Winograd algorithm is for this task. A divide-and-conquer algorithm for this task that relies on partitions was extended to give a runtime of n to the log-base-2-of-7 by Strassen. Since performing this task by definition requires one to find n-squared elements consisting of the sum of n products, this task can be performed naïvely in big-theta of n-cubed time. For 10 points, name this operation that requires the number of columns of the first input to equal the number of rows of the second input.
Cohn, Kleinberg, Szegedy, and Umans provided a group theoretic approach to this task that re-derives an earlier algorithm for it that Virginia Williams improved upon in 2011.
matrix multiplication [accept equivalents like multiplying matrices; do not accept or prompt on "multiplication" or "multiplying numbers"] &lt;Overman&gt;