The strassen’s matrix multiplication algorithm is a divide and
conquers technique to multiply 
matrices.
• In order to compute the product, 
, where each
of A, B, C are 
matrices,
and n is not an exact power of 2. It is necessary to extend the
size of matrices to next power of 2.
• This can be done by filling the last columns and the last rows of the matrices with zero.
Multiplying two 
matrices:
• Consider computing the product of two matrices.
Here, the value of n is 3 which is not an exact power of 2.
• So, extend the size of matrices to next power of 2, which are
two 
matrices.
• This can be done by filling the last column and the last row of the matrices with zero.
• Finally, apply strassen’s algorithm to multiply two
matrices.
• Take the top-left sub matrix
of the resultant matrix as
the result.
Multiplying two 
matrices:
• If two matrices
are to be multiplied, then it is necessary to extend the size of
matrices to 
matrices,
because 5 is not an exact power of 2 and the next power is 8.
• This can be done by filling the last 3 columns and the last 3 rows of the matrices with zero.
• Finally, apply strassen’s algorithm to multiply two matrices
and take the top-left sub matrix
of the resultant matrix as
the result.
Algorithm running time:
As n cannot be extended twice or more, it increases
constantly. Therefore, the algorithm running time is 
Explanation:
Let 
such that
The runtime for this algorithm is
.
Since 
it follows
that
. So, the
runtime
.
First, the recurrence for each case is as follows:
• 
• 
• 
T3(n)=
From the above, it is clearly proved that 
.
Asymptotically, the fastest one is nothing but the way of multiplying 70x70 matrices with the help of 143,640 multiplications and it is better than Strassen’s algorithm.
Strassen’s Matrix Multiplication Algorithm
Consider a matrix A of order 
and B
be a matrix of order
.
Note that the order of AB will be 
and
BA will be
.
Divide the matrices A and B into sub matrices of
order.
Where 
and
,
are matrices of order .
Calculate the product of the matrices A and B using sub matrices form.
Therefore, AB is expressed as a matric of order
.
Each element in the matrix is a product of two matrices of order
.
Multiplying two sub matrices of order using
Strassen’s algorithm takes 
time.
To calculate the product AB, it requires 
sub matrices
multiplications.
Therefore, the total time required to find the product
AB using Strassen’s algorithm is 
.
Calculate the product of the matrices B and A using sub matrices form.
Therefore, BA is expressed as a matric of order.
(Because, the product 
results
matrix, and the sum 
results
matrix).
The product of the sub matrices of order
using Strassen’s algorithm takes time.
To calculate the product BA, it requires 
sub matrix
multiplications
.
Therefore, the total time required to find the product
BA using Strassen’s algorithm is 
.
