Home Questions Search Forum Contact Guest Book Polls! Got a Question?
PREV Programs NEXT   (75 / 301)     Is there a way to multiply matrices in lesser than o(n^3) time complexity? 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 If you are aware, the rudimentary matrix multiplication goes something like this 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 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! PREV COMMENTS                                  INDEX                                  PRINT NEXT Last updated: November 3, 2005 www.cracktheinterview.com - Your destination for the most common IT interview questions, answers, frequently asked interview questions (FAQ), C Programs, C Datastructures for technical interviews conducted by the top IT companies around the world!