Over a decade ago, before I joined Microsoft, I was a doctoral candidate at Carnegie Mellon studying robotics. One of the things that you had to do to get into the doctoral program was pass a qualifier test (“the qual”), which was a three-hour oral examination at the conclusion of the Master’s program. My qual was, without a doubt, the most grueling experience I’d ever gone through – rougher than my actual dissertation several years later, and certainly rougher than a Microsoft interview. (“You just want me to write a program to shuffle a deck of cards? I think I can manage that…”) For the “qual,” it was common knowledge that you’d be expected to memorize and write out on command just about every formula known to mankind about the physics of robotics. To prepare, I wrote down 78 equations that I thought would be fair game during the exam, and I spent one hour a day for two months memorizing those equations – I kid you not. Equations invaded my dreams; for example, “In order to slay the dragon, I’ll have to apply an iterative Newton-Euler dynamic formulation to determine the acceleration and velocity of the sword based on the degrees of freedom in my arm.” One of the equations involved 26 variables and I was indeed asked to write it down during the exam, and to my utter delight, I got it right.

Within two days of passing my qualifier, the equations escaped from my brain, and I didn’t care. Hey, that’s what docs are for. I don’t memorize VB language syntax, for example – I look it up in a book or on-line, same as everyone else, except possibly our architect Paul Vick, whom I think has it all tattooed on his arms.

However, there comes a time when you need to use those equations, and working it out longhand would be tedious or impractical. That’s where programming comes in. I’m sure I’m not the only person, for example, who programmed his calculator in college to solve quadratic equations for the roots – very handy during exams where you could be expected to take that ability for granted. Unfortunately, during my tenure as a graduate student, calculators didn’t have nearly enough memory to quickly solve matrix equations (at least not the ones I could afford), and matrices are the backbone of all robotics formulae. However, these days a handheld device running Windows Mobile 5.0 or WindowsCE certainly has enough horsepower to do this, so in this two-part series I’ll walk through putting together such a matrix calculator. In this part, I’ll just be working with a class library, and next week, I’ll get it onto the handheld.

## Matrices

The first thing I’ll need is a matrix class, and to do that I’ll create a class library called Matrices simply by choosing CreateNewProject, choosing “Class Library,” and changing the name appropriately before clicking “OK.” (Don’t worry if you forget to change the name – in VB2005, it’s never too late to change it, and you can do it later simply be changing the name of the file in the solution explorer).

I’ll rename the class inside to be called “Matrix.” Again, don’t worry, you can also do this later by right-clicking on the name of the class and choosing “Rename.”

A matrix has some number of rows and columns (by the way, this entire series will be 0-based as far as arrays are concerned, not 1-based). Here’s the bare-bones version:

Private _rows As Integer = 0

Private _columns As Integer = 0

Public ReadOnly Property Rows() As Double

Get

Return _rows

End Get

End Property

Public ReadOnly Property Columns() As Double

Get

Return _columns

End Get

End Property

Public data(,) As Double

All very straightforward. Note that the number of rows and columns default to zero. Clearly, they need to be non-zero, so in the class constructor, I’ll enforce the requirement to supply dimensions:

Public Sub New(ByVal m As Integer, ByVal n As Integer)

ReDim data(m - 1, n - 1)

_rows = m

_columns = n

End Sub

Note the use of ReDim – this will allow me to dynamically determine the size of the array at runtime, rather than having to hard-code the array size. Also note that it looks like I’m re-dimming them for one size less than I need. This is because VB automatically adds on element to each array for historical reasons, as many programmers in the past preferred to work with 1-based notation. I don’t need the extra memory, and it makes looking at matrices in the debugger window confusing, so out it goes. (And yes, if you call New(1,1), it will redim the array to (0,0), which, after VB adds the additional row and column as usual, turns out to be 1 allocated element. It hurts my head to think too hard about that, but at least the right thing happens in the end.)

Now, if I wanted to add two matrices together, I could create a shared function called Add(m1,m2) which would add the two together, something like this:

Public Shared Function Add(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

' … etc…

End Function

Dim m3 As Matrix = Matrix.Add(m1, m2)

But wouldn’t it be cooler if we could just do:

Dim m3 As Matrix = m1 + m2

Well, we can, thanks to something in VB2005 called operating overloading. I discussed operator overloading in some detail in this article here a few years ago, but the gist of it is that Operator Overloading allows you to assign methods to the various mathematical symbols (+, -, *, /, etc.) for a given class. You can even define casting operators. Let’s define an overload here for addition:

Public Shared Operator +(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

If m1.Rows = 0 OrElse m2.Rows = 0 OrElse m1.Columns = 0 OrElse m2.Columns = 0 Then

Dim ex As New System.Exception("Attempt to add empty matrix.")

Throw ex

End If

If m1.Rows <> m2.Rows OrElse m1.Columns <> m2.Columns Then

Dim ex As New System.Exception("Attempt to add differently-shaped matrices.")

Throw ex

End If

Dim m3 As New Matrix(m1.Rows, m1.Columns)

For i As Integer = 0 To m1.Rows - 1

For j As Integer = 0 To m1.Columns - 1

m3.data(i, j) = m1.data(i, j) + m2.data(i, j)

Next

Next

Return m3

End Operator

Let’s start with the signature from above. All operator overload methods are shared methods. They work on a particular symbol or keyword (in this case, the plus sign, +), and they take arguments having particular classes (in this case, two matrices), and they return some type (again, in this case, a matrix). What you do inside the rest of the method is totally up to you. I start out by making sure the matrices are the same size and that they are not empty, throwing if they fail those tests. Then, I simply create a new matrix, add together the contents of m1 and m2 to it, and then return the result. Simple, isn’t it?

If you’ve guessed that an overloaded operator is really just a function, you’re right. What you’re getting out of it is simply the ability to write more readable code. You do need to take care to use them properly, though. Take this (contrived) example, where I allow a matrix to be multiplied by a scalar:

Public Shared Operator *(ByVal m1 As Matrix, ByVal val As Double) As Matrix

Dim m2 As New Matrix(m1.Rows, m1.Columns)

For i As Integer = 0 To m1.Rows - 1

For j As Integer = 0 To m1.Columns - 1

m2.data(i, j) = m1.data(i, j) * val

Next

Next

Return m2

End Operator

So, the following code works:

Dim m1 As New Matrix(5, 5)

' … Pretend there’s code here that fills m1 with data

Dim m2 As Matrix = m1 * 7.0

But this doesn’t – the arguments are in the wrong order:

Dim m1 As New Matrix(5, 5)

' … Pretend there’s code here that fills m1 with data

Dim m2 As Matrix = 7.0 * m1 ' ERROR!

We can fix this by also defining the opposite arguments in a different overload:

Public Shared Operator *(ByVal val As Double, ByVal m1 As Matrix) As Matrix

Return m1 * val ' This will just call the other overload

End Operator

And now it doesn’t matter what order the arguments are in for this particular case. (There are certainly cases where the argument order would matter for two different types, which is why VB doesn’t do this sort of thing automatically.)

Of course, we can define other overloads on the multiplication operator, so long as the types and orders are different. For example, let's add a third overload which multiplies two matrices, which is a vastly different operation than multiplying a matrix by a scalar:

Public Shared Operator *(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

If m1.Rows = 0 OrElse m2.Rows = 0 OrElse m1.Columns = 0 OrElse m2.Columns = 0 Then

Dim ex As New System.Exception("Attempt to subtract empty matrix.")

Throw ex

End If

If m1.Columns <> m2.Rows Then

Dim ex As New System.Exception("Attempt to multiply incompatible matrices.")

Throw ex

End If

Dim m3 As New Matrix(m1.Rows, m2.Columns)

For ci As Integer = 0 To m3.Rows - 1

For cj As Integer = 0 To m3.Columns - 1

' Fill in the Cij value in m3

m3.data(ci, cj) = 0

For i As Integer = 0 To m1.Columns - 1

m3.data(ci, cj) = m3.data(ci, cj) + m1.data(ci, i) * m2.data(i, cj)

Next

Next

Next

Return m3

End Operator

So, I can call:

1. 5.0 * m1 (scalar multiplied by matrix)

2. m1 * 5.0 (matrix multiplied by scalar)

3. m1 * m2 (matrix multiplied by matrix)

and in each case a totally different operator overload will be called, despite the consistent use of the asterisk operator.

I’ve attached the full library to this post. It includes methods for finding the determinant of a matrix, the inverse of a matrix, and the transpose of a matrix as well, since we’ll need those next week – there’s nothing particularly special about those methods, so I won't dig into them here. (Keen eyes will note that I deliberately used the easiest calculations for the determinant and inverse, in order to make them more readable and to allow me to focus on the real subject, which was operator overloading. You can find more performant algorithms out on the web – they tend to be iterative and are often ghastly to try to read.) I’ve also attached some test cases in a console application.

Next week, we’ll work on our hand-held matrix calculator. ‘Til then…

--Matt--*