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?
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.