Strassen’s Algorithm for Matrix Multiplication
Introduction
The Strassen algorithm which is named after Volker Strassen, is a Matrix Multiplication Algorithm in Linear Algebra. It is better than the naïve matrix multiplication algorithm and is usually used in practice for large matrices, but it is not recommended for extremely large matrix.
Strassen’s algorithm works for any ring, such as plus/multiply, but not all semirings, such as min-plus or Boolean algebra, where the naïve algorithm still works, and so called combinatorial matrix
Volker Strassen came out with his algorithm in 1969 and which showed that the usual method for matric multiplication can be optimized. Although the Strassen algorithm is very slightly better than that, but its publication paved the way for much more research about matrix multiplication that led to even better approaches than Strassen’s algorithm, such as the Coppersmith-Winograd algorithm.
Before Strassen
A. Naïve Method
To multiply two matrices, the number of columns of first matrix should be equal to the number of rows to second matrix. This program displays the error until the number of columns of first matrix is equal to the number of rows of second matrix.
Suppose that you simply have 2 real n x n matrices A and B, and you would like to figure the n x n matrix C = AB that’s the result of multiplication of A and B. By definition, if we tend to denote element of A by a(i,j) i.e., the part of matrix A that’s within the i-th row and j-th column, and same for B and C, then the part c(i,j) of C is equal to.
If we tend to assume, for simplicity, that additions, multiplications, and memory access operation take constant time, then it’s straightforward to visualize that the above algorithm requires roughly n³ steps, as we’ve got three for-loops, all nested within the others. Overall, we can say that the time complexity for this algorithm is n³.
B. Divide and Conquer.
Simple divide and conquer is another way to perform matrix multiplication. We divide the question into smaller parts, as the name implies, and solve the problem more efficiently than the naïve algorithm. It aids in the division of the problem into manageable chunks and provides a better understanding of the solution.
The following exposition of the algorithm, is only possible if we assume that all matrices have sizes that are powers of two (i.e. 2^n), but this is not always necessary — if the matrices A, B are not of type 2^n × 2^n we can think about padding the “missing” rows and columns with zeros to obtain matrices that will have the order of power of 2 though real implementations of the algorithm.
Suppose that we partition each of A,B and C(C is the resultant Matrix) into 4 n/2 x n/2 matrices.
So that we can rewrite the equation C = A.B as
Now, we can write elements of C in as
We recursively iterate this division process until the submatrices are reduced into numbers. If the original matrices do not have power of two than the resultant matrix will have zero rows and column just like A and B. Those zero rows must be removes to get the desired matrix i.e. C.
In the method shown above, we can see that we have to do a total no of 8 multiplication for matrices of size N/2 x N/2 and 4 addition. The time complexity for adding two matrices is O(N2). So, the Recursion relation can be written as
T(N) = 8T(N/2) + O(N2)
Using Masters Theorem, we can find the time complexity of this relation to be O(N3).Which is no better than the naïve method.
Strassen’s Algorithm
A more effective divide-and-conquer strategy. The main reason for the high tine complexity in the above-mentioned divide and conquer method is the 8 recursive calls. The primary goal of Strassen’s algorithm is to reduce those eight recursive calls to seven, lowering the time complexity slightly.
It uses the same method of dividing the matrix into N/2 x N/2 submatrices, however, the method of calculating the results of the submatrices using some derived formulas has changed.
only using 7 multiplications instead of 8. Now,
Implementation
Let’s take a look at the code for a question where you need to multiply two matrices A and B using Strassen’s matrix multiplication algorithm.
Functions for Basic Addition and Subtraction Operation can be written as:
The base case:
Declaring C and calculating dimension of sub-matrices:
Initializing sub-matrices and defining sub-matrices:
Calculating the product P1 to P7 and the resulting matrix C using formulas:
Copying values to C and returning C
The Code(Python V3.6)
As discussed earlier, Time complexity of addition and subtraction is O(N2). Hence we can write the recursion relation for Strassen's algorithm to be
T(N) = 8T(N/2) + O(N2)
From Master’s Theorem, time complexity of above method is
O(N^log(7)) which is approximately O(N^2.8074), which is better than classic divide and conquer(O(n³)).
This might not seem as a significant improvement but for large input sizes the difference is significant. We can see the difference in the graph below.
There is not much improvement in the time complexity for smaller matrices but for large size the difference is significant. The given below graph shows how Strassen’s Algorithm works better for larger matrices
We can see that as you the input becomes larger the time complexity has much greater rise in naïve method than Strassen’s algorithm .In other words, Strassen’s algorithm shows a performance increase compared to the naïve algorithm. Strassen’s algorithm can be further improved by parallelizing it like the naïve algorithm.
Disadvantages of Strassen’s Algorithm
Generally, Strassen’s Method is not used for practical applications due to following reasons.
1. For a typical application Naïve method works fine due to high number of constants in Strassen’s method.
2. For Sparse matrices, we use some other methods which are best for them and are especially designed for them.
3. Extra space is required for submatrices that are in recursion.
4. As Computer arithmetic have limited precision on non-integer values, there is accumulation of larger errors in Strassen’s algorithm than in naïve method.
