The trouble with matrix multiplication

2007-11-19

is that it’s not commutative. That means that when the SVG spec says in the documentation for the multiply method in the SVGMatrix DOM “this matrix is post-multiplied by another matrix” it really does matter which way round you do the multiplication of the two matrices.

In the call «A.multiply(B)», A is this and should be post-multiplied by B. In the usual mathematical convention the result should be AB.

Safari computes BA, Firefox computes AB. Oopsy.

This is a confusing area; when I was first getting the turtle motion in Curly Logo going (on Firefox initially) I remember a bit where the turtle’s motion was wrong, and I realised that I had some matrix multiplication the wrong way round. Happens all the time regardless of how much thinking I do beforehand about which way round matrices ought to be multiplied, so I thought nothing of it and simply swopped my arguments. As I was writing the first draft of this article I thought Firefox had it wrong and Safari had it right, turns out that’s not right, it’s the other way round.

Regardless of who is right, anyone wanting to use the routine has to do something to work around it.

So here’s what I do. I perform a trial matrix multiplication using SVGMatrix.multiply and determine whether the multiplication was performed the correct way round or the wrong way round.

Consider the matrices L, a flip, and R, a projection:

L = \begin{pmatrix}0&1&0\cr 1&0&0\cr 0&0&1\end{pmatrix}, R = \begin{pmatrix}0&0&1\cr 0&0&0\cr 0&0&1\end{pmatrix}

LR, that is «L.multiply(R)» as it should be:

LR = \begin{pmatrix}0&0&0\cr 0&0&1\cr 0&0&1\end{pmatrix}

What happens if the implementation swops its arguments:

RL = \begin{pmatrix}0&0&1\cr 0&0&0\cr 0&0&1\end{pmatrix}

In JavaScript (well, SVG DOM really) the entries of a matrix are assigned to properties like this:

\begin{pmatrix}a&c&e\cr b&d&f\cr 0&0&1\end{pmatrix}

Note that the two result matrices (above) only differ in their e and f entries. Specifically when «L.multiply(R)» is computed correctly (following the specification) the result’s e property is 0; when computed with the matrices swopped (incorrectly) the result’s e property is 1. How convenient.

Here is some JavaScript to detect if SVGMatrix.multiply is wrong:

matmulwrong = function() {
  var g = document.createElementNS('http://www.w3.org/2000/svg', 'g')
  g.setAttribute('transform',
    'matrix(0 1 1 0 0 0) translate(1 0)')
  var l = g.transform.baseVal.getItem(0).matrix
  var r = g.transform.baseVal.getItem(1).matrix
  return l.multiply(r).e
}

There is a lot of faffing around creating a pointless g element just so I can attach two matrices to it. That really was the most convenient way I found to create two matrices.

We can use matmulwrong to select one of two definitions for our own matmul function to multiply two matrices:

// matmul(A, B) computes AB
matmul = matmulwrong() ?
    function(a, b) { return b.multiply(a) } :
    function(a, b) { return a.multiply(b) }

Now we should only use matmul and avoid using SVGMatrix.multiply. Defining it like this means we decide once, when the JavaScript is loaded, and not every time that we call matmul. Notice how this simply tests whether SVGMatrix.multiply is swopped or not and acts accordingly; it doesn’t care whether you’re using Safari or Firefox, it’s more in the spirit of object detection, not browser sniffing. As soon as bug 16062 gets fixed in FirefoxSafari the code will detect it as being fixed. Life is good again and Curly Logo works on both browsers.

PS: Opera agrees with Firefox.
PPS: Guess which WordPress feature I used today that I thought I’d never find a genuine use for.

About these ads

13 Responses to “The trouble with matrix multiplication”

  1. glorkspangle Says:

    When A is post-multiplied by B, the result is clearly AB. But the object-oriented notion adds a little confusion here; is A updated as a result?
    By the way, your R is a projection, not a translation (it’s singular).

  2. glorkspangle Says:

    guess which WordPress feature
    The TeX thing?

  3. drj11 Says:

    projection/translation: You’re right of course. Durr… [later: of course, I actually use a translation in the code, so I should update the maths to reflect that I suppose].

  4. drj11 Says:

    Yeah the Tex thing. It’s actually Latex which means I had to learn how to do matrices in Latex.

  5. glorkspangle Says:

    By the way, a few clicks away I found this, which looks worthwhile.

  6. glorkspangle Says:

    I think you can use ‘translate(1) rotate(90)’.

  7. drj11 Says:

    Cute but dangerous. rotate(90) might produce a matrix with entries other than 0 or 1. For example, values very close to 0.

    On Safari I get a matrix equivalent to “matrix(-4.371138828673793e-8,1,-1,-4.371138828673793e-8,0,0)”. NBG.

  8. glorkspangle Says:

    well, OK. You can still test the resulting ‘e’ value for either being close to zero or close to one.

  9. drj11 Says:

    Yeah, but then I can’t exploit the Iverson’s Convention value of the e property by just going «return l.multiply(r).e».

  10. glorkspangle Says:

    Aha!

  11. hari Says:

    i need some programs for my assignments is there to helpme do my assignment in python

  12. drj11 Says:

    @hari: oh rly?

  13. tuna Says:

    I need help in matrix multiplication program.how to declare a multi dimensional array in shell programming.


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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: