Matrix Mathematics

Monday, 11 May 2009

Mathematics can sometimes be a bit daunting, and one thing I've always found a bit difficult is matrix mathematics. So, I am writing down some notes regarding this particular subject, and the implementation of said subject in C/C++.

Mathematical Notation

Matricies are very abstract in the sense that we can write them down in many different ways. For example a 4×4 identity matrix written in standard mathematical notation:

When we consider standard mathematical notation, the origin is in the top left hand side, and we specify size in the format (rows, columns). Never confuse rows and columns with width and height, as things may get confusing.

Mathematically, here are the coordinates into the matrix, when we consider individual items, R designating the row count, and C designating the column count:

Memory layout

In C when we can access data in whatever order we like.

Row Major
Elements of a row are stored contiguously in memory.
Column Major
Elements of a column are stored contiguously in memory.

In C we also have multi-dimensional arrays to assist with accessing data. These are per the C specification laid out in memory in sequential arrays the size of the last dimension. For example:

What this is saying is "2 arrays of 4 float values". And that is the way they are arranged in memory also:

 Memory Offset Index[row][col] 0 1 2 3 4 5 6 7 v v v v v v v v

Here is an alternative view (values are memory offsets):

Col 0Col 1Col 2Col 3
Row 00123
Row 14567

The function for row and column major order are not complex:

It is important you understand the following are equivalent terms:

 number of elements per column ⇔ number of rows number of elements per row ⇔ number of columns

Here we can use the rowMajorLookup function which is equivalent to the standard C array indexing:

So, we know the standard mathematical representation of a matrix, and we know how they can be represented in memory, but where does that leave us? Right, we need to make some concrete implementation so we can really see how it all comes together.

Firstly, we have two options to consider, as mentioned earlier:

Row major order
A single row should be sequential in memory: `float values`
Col 0Col 1Col 2Col 3
Row 00123
Row 14567
Column major order
A single column should be sequential in memory `float values`
Col 0Col 1Col 2Col 3
Row 00246
Row 11357

As you can see, it is as simple as swapping (the technical term is transpose) around the dimensions for the array declaration. We can design a simple template class which will handle just about anything we can throw at it.

The code is available as an Xcode project.

Here is the result after running this code

As you can see, it doesn't matter how we store the data in memory (depending on what you are doing, it may be more or less convenient to use either way), we can still retrieve the data in standard mathematical form.

Conclusion

Ultimately, depending on what other libraries you want to integrate your code with, you may need to choose a specific format. Other reasons, such as performance, may dictate the best layout for your data - i.e. vectors of data are best laid out sequentially for quick and easy access. SSE/3DNow/MMX may also have strict requirements on data layout and alignment for parallelization and optimization of specific operations.

It is also worthwhile to point out, that at least in my case, it was confusing to think of matrices having "width" and "height". In order to consider a matrix with width and height, we actually need to rotate the matrix to get a co-ordinate system that makes sense, i.e. x, y in the origin.

I personally find the transpose functions fascinating. For example, simply by reinterpreting the data from row major to column major we can transpose the data.

Please note, comments must be formatted using Markdown. Links can be enclosed in angle brackets, e.g. `<www.codeotaku.com>`.