For-loop bottleneck (outer products and matrix multiplications in slices of an array of d >2)

Question

Thanks in advance for any help.

I'm running a numerical optimization in MATLAB to fit the parameters of a time series model to data. To speed up running time I've vectorized as much code as I can but I'm left with the following for-loops that are order(s) of magnitude slower than other lines of code. As a result, the optimizations are impractically slow, especially as I want to compare the performance of many models. The operations involve repeated outer vector products or matrix multiplications on slices of an n-d array (where n is greater than 2).

I've vectorized the below for-loops in various ways such as by reshaping matrices (and replicating dimensions using repmat or bsxfun a la Matrix multiplication of row and column without for loop in matlab) but the vectorized versions run slower than the original for-loops. I've also downloaded several functions including mtimesx (which causes MATLAB to crash) and multiprod (which is slower than the below for-loops).

The first for-loop is:

Vnew = zeros(nS,nS,nC);
for c = 1:nC
    Vnew(:,:,c) = (eye(nS) - K(:,c)*C(c,:))*Vpred;
end

where nC = 20, nS = 40, K is a 40x20 matrix, C is a 20x40 matrix and Vpred is a 40x40 matrix.

The second for-loop is:

Vmerge = zeros(nS,nS);
for c = 1:nC
    Vmerge = Vmerge + (V(:,:,c,t) + err(:,c)*err(:,c)')*cPnew(c);
end

where V(:,:,:,t) is a 40x40x20 matrix, err is a 40x20 matrix and cPnew is a 20x1 vector.

Each of these for-loops is called 540 times per run of the optimizer (I have 540 discrete time points in my time series model).

I've been struggling with this for some time. Solutions I've found online don't seem to be faster than the above for-loops. If anybody can suggest a solution with running time comparisons I'd be so grateful.

Thanks,

Abby

Initialise a variable to eye(nS) outside of the loop as it doesn't change, and you could just compute diff once per loop and save a transpose by using the fact diff(:,c)*diff(:,c)'=sum(diff(:,c).^2) Otherwise I second what Mendi has said — Wolfie
All suggestions we can offer like bsxfun, initialize matrices with random junk instead of zeros, rename diff to avoid shadowing built-in functions etc... won't help much if you use newer matlab. It is a simple problem of having too much to calculate. It would help to parallelize this thingy if you don't already do that in some outer loop. And a side point - do you perhaps want .' instead of '? This is a common error. — Zizy Archer
Thanks for your responses. Taking eye(nS) out of the loop makes it a little bit faster. diff(:,c)*diff(:,c)' is an outer product not an inner product @Wolfie so I'm not sure that your suggestion is relevant. Using .' instead of ' makes no difference as far as I can tell Zizy Archer ... — AbbyJ
@AbbyJ Then you have real values. .' transposes and is the one you should use when you want transpose. ' does complex conjugate transpose and often ends up being source of errors - code works for real input and breaks for complex :) — Zizy Archer

Sairus Sairus · Accepted Answer · 2017-05-02T09:17:40

You can convert matlab code for the sample function Func(x,y) into mex-file:

codegen -config coder.config('lib') Func -args {x, y}

or lib/dll C code:

codegen -config coder.config('mex') Func -args {x, y}

Then you can call mex files just as ordinary matlab functions "Func_mex(x,y)" (they will run much faster) OR browse into C-code and see, what does happen inside your function at C level.

For-loop bottleneck (outer products and matrix multiplications in slices of an array of d >2)

1 Answers