Multiplying two matrices in Java

Question

I am currently developing a class to represent matrices, it represents any general mxn matrix. I have worked out addition and scalar multiplication but I am struggling to develop the multiplication of two matrices. The data of the matrix is held in a 2D array of doubles.

The method looks a little bit like this:

public Matrix multiply(Matrix A) {
    ////code
}

It will return the product matrix. This is multiplication on the right. So, if I called A.multiply(B) then it would return the matrix AB, with B on the right.

I don't yet need to worry about checking whether the multiplication is defined on the given matrices, I can assume that I will be given matrices of the correct dimensions.

Does anyone know of an easy algorithm, possibly even in pseudocode to carry out the multiplication process?

Answer 1

Mathematically the Product of Matrices A (l x m) and B (m x n) is defined as a Matrix C (l x n) consisting of the elements:

        m
c_i_j = ∑  a_i_k * b_k_j
       k=1

So if you're not too much up for speed you might be happy with the straight forward O(n^3) implementation:

  for (int i=0; i<l; ++i)
    for (int j=0; j<n; ++j)
      for (int k=0; k<m; ++k)
        c[i][j] += a[i][k] * b[k][j]  

If instead you're up for speed you might want to check for other alternatives like Strassen algorithm (see: Strassen algorithm).

Nevertheless be warned - especially if you're multiplying small matrices on modern processor architectures speed heavily depends on matrix data and multiplication order arranged in a way to make best use of in cache lines.

I strongly doubt there will be any chance to influence this factor from withing a vm, so I'm not sure if this is to be taken into consideration.

Answer 2

Java. Matrix multiplication.

Here is the "code to carry out the multiplication process". Tested with matrices of different size.

public class Matrix {
  /**
   * Matrix multiplication method.
   * @param m1 Multiplicand
   * @param m2 Multiplier
   * @return Product
   */
  public static double[][] multiplyByMatrix(double[][] m1, double[][] m2) {
    int m1ColLength = m1[0].length; // m1 columns length
    int m2RowLength = m2.length;    // m2 rows length
    if (m1ColLength != m2RowLength) return null; // matrix multiplication is not possible
    int mRRowLength = m1.length;    // m result rows length
    int mRColLength = m2[0].length; // m result columns length
    double[][] mResult = new double[mRRowLength][mRColLength];
    for (int i = 0; i < mRRowLength; i++) {     // rows from m1
      for (int j = 0; j < mRColLength; j++) {   // columns from m2
        for (int k = 0; k < m1ColLength; k++) { // columns from m1
        mResult[i][j] += m1[i][k] * m2[k][j];
        }
      }
    }
    return mResult;
  }

  public static String toString(double[][] m) {
    String result = "";
    for (int i = 0; i < m.length; i++) {
      for (int j = 0; j < m[i].length; j++) {
        result += String.format("%11.2f", m[i][j]);
      }
      result += "\n";
    }
    return result;
  }

  public static void main(String[] args) {
    // #1
    double[][] multiplicand = new double[][]{
      {3, -1, 2},
      {2,  0, 1},
      {1,  2, 1}
    };
    double[][] multiplier = new double[][]{
      {2, -1, 1},
      {0, -2, 3},
      {3,  0, 1}
    };
    System.out.println("#1\n" + toString(multiplyByMatrix(multiplicand, multiplier)));
    // #2
    multiplicand = new double[][]{
      {1,  2, 0},
      {-1, 3, 1},
      {2, -2, 1}
    };
    multiplier = new double[][]{
      {2},
      {-1},
      {1}
    };
    System.out.println("#2\n" + toString(multiplyByMatrix(multiplicand, multiplier)));
    // #3
    multiplicand = new double[][]{
      {1, 2, -1},
      {0, 1,  0}
    };
    multiplier = new double[][]{
      {1, 1, 0, 0},
      {0, 2, 1, 1},
      {1, 1, 2, 2}
    };
    System.out.println("#3\n" + toString(multiplyByMatrix(multiplicand, multiplier)));
  }
}

Output:

#1
      12.00      -1.00       2.00
       7.00      -2.00       3.00
       5.00      -5.00       8.00

#2
       0.00
      -4.00
       7.00

#3
       0.00       4.00       0.00       0.00
       0.00       2.00       1.00       1.00