10
$\begingroup$

I have to make a coordinates transformation between two reference systems (axes). For that, three matrices ($3\times3$) have to be multiplied due to some intermediate axes being used. I have thought about two approaches to resolve this:

Method #1: Making the multiplication directly, that is, $$v_f = R_1\ R_2\ R_3\ v_i$$

Method #2: Split into steps:

  1. $v_{3i} = R_3\ v_i$
  2. $v_{23} = R_2\ v_{3i}$
  3. $v_f = R_1\ v_{23}$

where:

$R_1$, $R_2$ and $R_3$ are $3\times3$ matrices

$v_f$,$v_i$, $v_{3i}$, $v_{23}$ are $3\times1$ vectors

I would like to know what method is more efficient computationally (less time) to do the transformation (this will be made a lot of times).

$\endgroup$
  • 4
    $\begingroup$ Use quaternions. $\endgroup$ – Chris Taylor May 14 '12 at 10:20
  • $\begingroup$ @ChrisTaylor: Thank you so much for your suggestion. $\endgroup$ – julianfperez May 14 '12 at 14:19
  • 2
    $\begingroup$ Please don't crosspost. $\endgroup$ – Ripped Off May 14 '12 at 17:08
  • 2
    $\begingroup$ Note, there were two questions cross-posted to here and StackOverflow. The questions and their comments and answers have been merged into this one. $\endgroup$ – Aron Ahmadia May 14 '12 at 19:35
  • $\begingroup$ @Will and AronAhmadia: I am sorry. I did not know the crossposting is forbidden. I have always posted my questions on StackOverflow but today I found this new site and I thought perhaps I could find help here too. $\endgroup$ – julianfperez May 14 '12 at 21:13
17
$\begingroup$

Matlab interprets sequences of multiplications and/or divisions from left to right. Hence $A*B*C*v$ is much more expensive than $A*(B*(C*v))$, as you have two matrix products and one matrix-vecor product in place of three matrix-vector products.

On the other hand, $A*(B*(C*v))$ should be slightly faster than if you save the intermediates in separate vectors, as your second method suggests.

To find out in general how to measure the impact of small programming differences on large-scale computations, write at the Matlab prompt ''help profile''.

$\endgroup$
  • $\begingroup$ Thank you for the interesting information given in your answer. $\endgroup$ – julianfperez May 14 '12 at 16:25
  • $\begingroup$ Why is it faster if you save the intermediates? $\endgroup$ – Federico Poloni Apr 16 '17 at 20:08
  • $\begingroup$ @FedericoPoloni: I had written that it is slightly faster not to save the intermediates. $\endgroup$ – Arnold Neumaier Apr 19 '17 at 13:01
  • $\begingroup$ @ArnoldNeumaier Ooh sorry I misread. :) $\endgroup$ – Federico Poloni Apr 19 '17 at 16:01
14
$\begingroup$

For starters, I wouldn't use intermediate variables, but brackets. Unless, of course, you're interested in the intermediate results, but I'm guessing not.

I tried the following in Matlab:

>> N = 500;                                             
>> A = rand(N); B = rand(N); C = rand(N); v = rand(N,1);

>> tic, for k=1:100, A*B*C*v; end; toc
Elapsed time is 3.207299 seconds.

>> tic, for k=1:100, A*(B*(C*v)); end; toc
Elapsed time is 0.108095 seconds.

I have to say, though, that this is quite frightening. I've always assumed that Matlab would be smart about the matrix multiplication order, as this is a known problem with a simple and efficient solutions.

$\endgroup$
  • $\begingroup$ Did you miss the part where the matrices are 3x3? :) $\endgroup$ – Aron Ahmadia May 14 '12 at 11:13
  • 2
    $\begingroup$ @AronAhmadia: Oops... Missed that, thanks. I guess for those matrix sizes, the whole problem is moot, but I'm still surprised at the results for large N. $\endgroup$ – Pedro May 14 '12 at 11:20
  • 7
    $\begingroup$ I'm guessing MATLAB is following the C precedence rules for expression evaluation because floating point math is not associative and they have to assume you know what you're doing :) $\endgroup$ – Aron Ahmadia May 14 '12 at 11:39
  • 2
    $\begingroup$ @Pedro: Thank you for your answer. For matrix dimension 3x3 I have checked that your solution is also better than the usual (without brackets) matrix multiplication. $\endgroup$ – julianfperez May 14 '12 at 14:14
  • $\begingroup$ +1 thank you for showing a simple and easy way to measure run time $\endgroup$ – Steven Magana-Zook May 21 '12 at 18:42
14
$\begingroup$

Since the matrices are so small, all of the cost is going to be in call overhead. If you will do the transformation many times, it will be faster to precompute D=A*B*C once and then for each vector apply v_f=D*v_i. You could also consider bringing this out to a mex file.

$\endgroup$
  • $\begingroup$ Thank you for your answer. In my case, the matrices are rotation ones (they depend on an angular value and this changes) so the product ABC is not always the same. $\endgroup$ – julianfperez May 14 '12 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.