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

Question

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)

Answer 1

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 2

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 3

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