Marcin Drobik

software journeyman notes

Matrix multiplication

Today let's look at one of the most important operations in matrix-based algorithms - matrix product (multiplication of two matrices).

Introduction

Matrix Product

Wikipedia has a great article together with some examples describing the multiplication very well. Among tons of information it gives following formula for multiplication:

Definition of matrix product

Code

Let's write a simple algorithm that implements the multiplication directly from above formula. For clarity we'll rename the indexes i and j to rowand column respectively.

public ColumnMajorMatrix Multiply(Matrix other)
{

First validate the input matrices dimensions:

    if (Width != other.Height)
        throw new InvalidOperationException("Matrix dimensions must agree");                

    var resultData = new double[Height * other.Width];

Start by iterating through each cell in result matrix...

    for (int column = 0; column < other.Width; ++column)
    {
        for (int row = 0; row < Height; ++row)
        {

... and compute its value by multiplying corresponding row and column from input matrices:

            double sum = 0;
            for (int k = 0; k < Width; ++k)
            {
                sum += GetByCoordinates(row, k)*other.GetByCoordinates(k, column);
            }

Save the value of computed cell to result array:

            resultData[Coordinate2ColumnIndex(row, column)] = sum;

        }
    };

Since the resultData is stored using column major indexing, we return it as ColumnMajorMatrix:

    return new ColumnMajorMatrix(resultData, new[] { Height, other.Width });
}

The Coordinate2ColumnIndex simply calculates column-first index:

private int Coordinate2ColumnIndex(int row, int column)
{
    return (column * Height) + row;
}

Is that all?

This algorithm's computational complexity is O(n3). There are algorithms that can do better than this, not only by reducing the complexity, but also by improving data locality and parallelism. Some implementations may even use your GPU to speed things up a little.

But that's a topic for another time.

comments powered by Disqus