Posts
 |
| Volker Strassen in 2009. Photo: Wikipedia |
Introduction
Suppose that you have two real n x n matrices A and B, and you want to compute the n x n matrix C = AB that is the product of A and B. By definition, if we denote by a(i,j) the element of matrix A that is in the i-th row and j-th column, and, similarly for B and C, we have that the element c(i,j) of C is equal to
It is natural to ask now about the time needed to compute matrix C. By observing the above definition, one can immediately come up with the following straightforward algorithm, which we describe in pseudo-code...
In this article, we will discuss the first algorithm that broke the O(n³) barrier. Named after its creator, Volker Strassen, Strassen’s algorithm, which appeared in 1969, uses the Divide-And-Conquer technique in a very clever way that results in an improved running time...
Conclusion
Strassen’s algorithm was a major breakthrough and was the starting point of a long line of research that is still ongoing to this day. The big open question is whether there exists a Matrix Multiplication algorithm with running time O(n²). Since the input and output have size n², this is clearly a lower bound, and one cannot hope to go lower than that. Given the significance of the problem, the constant in the exponent of the best (optimal) Matrix Multiplication algorithm is denoted as ω.
Source: Medium
