   Is there a way to multiply matrices in lesser than o(n^3) time complexity?

285 views
Is there a way to multiply matrices in lesser than o(n^3) time complexity? posted Nov 18, 2013

The best Matrix Multiplication Algorithm known so far is the "Coppersmith-Winograd algorithm" with O(n^2.38 ) complexity but it is not used for practical purposes.

However you can always use Strassen Algorithm which has O(n^2.81 ) complexity but there is no such known algorithm for matrix multiplication with O(n) complexity. answer Nov 18, 2013
+1 vote

Yes. Divide and conquer method suggests Strassen's matrix multiplication method to be used. If we follow this method, the time complexity is O(n^2.81) times rather O(n^3) times.

Here are some more details about this method. Suppose we want to multiply two matrices of size N x N: for example A x B = C

[C11 C12] [A11 A12] [B11 B12]
[C21 C22] = [A21 A22] [B21 B22]

Now, this guy called Strassen's somehow :) came up with a bunch of equations to calculate the 4 elements of the resultant matrix

C11 = a11*b11 + a12*b21
C12 = a11*b12 + a12*b22
C21 = a21*b11 + a22*b21
C22 = a21*b12 + a22*b22

Strassen showed that 2x2 matrix multiplication can be accomplished in 7 multiplications and 18 additions or subtractions. So now the complexity becomes

2^log7 =2^2.807

This is how he did it

P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11
P3 = A11 * (B12 - B22)
P4 = A22 * (B21 - B11)
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)

C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6

Now, there is no need to memorize this stuff! answer Nov 23, 2013

void matrix_mult()
{
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
compute Ci,j;
}
So, essentially, a 2x2 matrix multiplication can be accomplished using 8 multiplications. And the complexity becomes

2^log 8 =2^3

Strassen showed that 2x2 matrix multiplication can be accomplished in 7 multiplications and 18 additions or subtractions. So now the complexity becomes

2^log7 =2^2.807 answer Nov 23, 2013
Similar Questions
+1 vote

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)