Upside down and inside out

3 08 2010

Been more than 3 days, I wasn’t feeling very well and neither was my little one so sometimes a reordering of commitments needs to happen. I feel better now, got some coffee in me and the little one is sleeping [or pretending to anyway :D].

Subject for today, matrix transposition. Why? because I feel like it and because I’ve come up with an interesting way to do a transposition of a template matrix without worrying too much about rows/cols and switching in the memory. Let’s set out the stage, shall we…

My Matrix::Base class looks like this at the moment:
template<const size_t R, const size_t C, typename T>
class Base
{
  public:
    enum { rows=R, cols=C, dimension=rows*cols };
};

Actually, a bit more involved than that, but for the sake of brevity we’ll stick to the traits.
Transposition of a matrix is a simple matter, switch the columns of the matrix with its rows. Simple on paper, and simple on a computer for square matrices. So the 3×3 matrix:
0,1,2,
3,4,5,
6,7,8,

would be transposed into:
0,3,6,
1,4,7,
2,5,8,

Notice how the diagonal of a transposed matrix is the same, just a nifty little thing for a small optimization later on.
Well, it’s all good, we started with 3 rows and 3 columns and ended up with 3 rows and 3 columns.
Let’s take a slightly less trivial case of a 2×3 matrix:
0,1,2,
3,4,5,

Perform some transpose magic and *POOF* we end up with a 3×2 matrix. What happened there?
0,3,
1,4,
2,5,

I’ve come up against a few issues dealing with this and came up with several different approaches. In the end I’ve chosen the approach which seemed the simplest to me [and one which works easily with square matrices which are more commonly used in my code anyway]. What is it you ask?

Let us examine the problem first.

The underlying memory aligment of my matrix class is a simple array of rows*cols, so allowing for the commutitive nature of multiplication we can see that the actual size of the array does not change.

rows*cols=cols*rows

But the matrix is not the same, our values for rows, cols and the actual major order of the matrix have changed. My problem now, how do I access the new rows and columns without stepping out of bounds [C++ allows it, you should try it at least once, it’s fun… might format your harddrive though]. Easy you say, just change the values of the rows/cols traits; heh, easy, that is if the traits weren’t actually enums. I’ve thought about it, refactor the enums away into actual size_t variables and allow access to them via member functions [exposing them publicly would mean that anyone might change them at any given time, bad bad bad, and making them const against that means I’d have to const_cast and well, there’s just no excuse for that…].

My solution?
template<const size_t R, const size_t C, typename T>
class Base
{
  public:
    enum { rows=R, cols=C, dimension=rows*cols };
    typedef Base<C,R,T> transpose_matrix;
};

and the transpose function:
template<typename T>
inline T::transpose_matrix Transpose(const T& rhs);

Simple, safe and hassle free. In case of transposing a non-square matrix we won’t be able to assign the newly transposed result into our old matrix which is probably what we need anyway [it automatically converts between the major order instead of needing a separate trait value for it] and in case of a square matrix it works out of the box because rows and columns are the same so no problems there.

Well, there you have it, a nice [if I do say so myself] way of transposing any matrix of any dimension.

“you get what you pay for, but I had no intentions of living this way”

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: