3

The problem is simply for matrices A, B, C, and D that are n*n and x that is a vector of length n, to find E = DCBAx in the most efficient way on Matlab, and in the least efficient way.

The most obvious way to calculate E is just to multiply them straight-forward

Is this the most efficient way? What is the least efficient way?

Fantastic Mr Fox
  • 32,495
  • 27
  • 95
  • 175
LuckyPenny
  • 39
  • 6
  • related: http://stackoverflow.com/questions/6058139/why-is-matlab-so-fast-in-matrix-multiplication ? – Fantastic Mr Fox Sep 25 '14 at 04:59
  • Least efficient really is a somewhat moot question, there is an infinite array of solutions that will perform mediocre. However, for such operations, implementing a matrix multiplication algorithm with nested loops usually performs very unfavourably compared to the inbuilt matrix multiplication. – sobek Sep 25 '14 at 06:36

1 Answers1

8

Let us create the dummy matrices and vector for this example.

n = 1000;
A = rand(n, n);
B = rand(n, n);
C = rand(n, n);
D = rand(n, n);
x = rand(n, 1);

Then we can define some function handles for the matrix products, in which we force the order of the operations

fun1 = @() D*C*B*A*x;
fun2 = @() (D*C*B*A)*x;
fun3 = @() (D*(C*(B*A)))*x;
fun4 = @() D*(C*(B*(A*x)));

A simple execution time evaluation with timeit shows that fun1, fun2 and fun3 perform nearly in the same way, while fun4 is about 100 times faster. The reason for this behavior is that in the first three cases we require 3 matrix products and 1 matrix-vector product, while in the last one only 4 matrix-vector products are performed. Interestingly Matlab is not able to recognize this simple optimization when it evaluates fun1.

Jommy
  • 1,020
  • 1
  • 7
  • 14