## Matrix multiplication

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

## Introduction

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

## 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 `row`

and `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(n^{3}). 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.