matrix multiplication algorithm time complexity

Question

I came up with this algorithm for matrix multiplication. I read somewhere that matrix multiplication has a time complexity of o(n^2). But I think my this algorithm will give o(n^3). I don't know how to calculate time complexity of nested loops. So please correct me.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

Answer 1

Using linear algebra, there exist algorithms that achieve better complexity than the naive O(n³). Solvay Strassen algorithm achieves a complexity of O(n^2.807) by reducing the number of multiplications required for each 2x2 sub-matrix from 8 to 7.

The fastest known matrix multiplication algorithm is Coppersmith-Winograd algorithm with a complexity of O(n^2.3737). Unless the matrix is huge, these algorithms do not result in a vast difference in computation time. In practice, it is easier and faster to use parallel algorithms for matrix multiplication.

Answer 2

The naive algorithm, which is what you've got once you correct it as noted in comments, is O(n^3).

There do exist algorithms that reduce this somewhat, but you're not likely to find an O(n^2) implementation. I believe the question of the most efficient implementation is still open.

See this wikipedia article on Matrix Multiplication for more information.

Answer 3

The standard way of multiplying an m-by-n matrix by an n-by-p matrix has complexity O(mnp). If all of those are "n" to you, it's O(n^3), not O(n^2). EDIT: it will not be O(n^2) in the general case. But there are faster algorithms for particular types of matrices -- if you know more you may be able to do better.

Answer 4

In matrix multiplication there are 3 for loop, we are using since execution of each for loop requires time complexity O(n). So for three loops it becomes O(n^3)

Answer 5

I recently had a matrix multiplication problem in my college assignment, this is how I solved it in O(n^2).

import java.util.Scanner;

public class q10 {
public static int[][] multiplyMatrices(int[][] A, int[][] B) {
    int ra = A.length; // rows in A
    int ca = A[0].length; // columns in A

    int rb = B.length; // rows in B
    int cb = B[0].length; // columns in B

    // if columns of A is not equal to rows of B, then the two matrices,
    // cannot be multiplied.
    if (ca != rb) {
        System.out.println("Incorrect order, multiplication cannot be performed");
        return A;
    } else {
        // AB is the product of A and B, and it will have rows,
        // equal to rown in A and columns equal to columns in B
        int[][] AB = new int[ra][cb];

        int k = 0; // column number of matrix B, while multiplying

        int entry; // = Aij, value in ith row and at jth index

        for (int i = 0; i < A.length; i++) {
            entry = 0;
            k = 0;

            for (int j = 0; j < A[i].length; j++) {
                // to evaluate a new Aij, clear the earlier entry
                if (j == 0) {
                    entry = 0;
                }

                int currA = A[i][j]; // number selected in matrix A
                int currB = B[j][k]; // number selected in matrix B

                entry += currA * currB; // adding to the current entry

                // if we are done with all the columns for this entry,
                // reset the loop for next one.
                if (j + 1 == ca) {
                    j = -1;
                    // put the evaluated value at its position
                    AB[i][k] = entry;

                    // increase the column number of matrix B as we are done with this one
                    k++;
                }

                // if this row is done break this loop,
                // move to next row.
                if (k == cb) {
                    j = A[i].length;
                }
            }
        }
        return AB;
    }

}

@SuppressWarnings({ "resource" })
public static void main(String[] args) {
    Scanner ip = new Scanner(System.in);

    System.out.println("Input order of first matrix (r x c):");
    int ra = ip.nextInt();
    int ca = ip.nextInt();

    System.out.println("Input order of second matrix (r x c):");
    int rb = ip.nextInt();
    int cb = ip.nextInt();

    int[][] A = new int[ra][ca];
    int[][] B = new int[rb][cb];

    System.out.println("Enter values in first matrix:");
    for (int i = 0; i < ra; i++) {
        for (int j = 0; j < ca; j++) {
            A[i][j] = ip.nextInt();
        }
    }

    System.out.println("Enter values in second matrix:");
    for (int i = 0; i < rb; i++) {
        for (int j = 0; j < cb; j++) {
            B[i][j] = ip.nextInt();
        }
    }

    int[][] AB = multiplyMatrices(A, B);

    System.out.println("The product of first and second matrix is:");
    for (int i = 0; i < AB.length; i++) {
        for (int j = 0; j < AB[i].length; j++) {
            System.out.print(AB[i][j] + " ");
        }
        System.out.println();
    }
}

}