MATLAB matrix multiplication (the best computational approach)

Question

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).

Answer 1

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''.

Answer 2

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.

Answer 3

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.