Speeding up this function involving 3D matrix multiplications.

I have this function that is called several times over in my project. Running the code analyer shows that this is the bottleneck. There are a lot of 3D matrix multplicaions in here. I was looping to evaluate it first, but then someone suggested vectorizing it. However, the only function I could find that helped me is pagemtimes(). Is there a way I can speed this up further? My aim is to deploy this on real time experiment, that is why speed is of paramount importance!

Function:

function [fun] = evalP(input, xd, d, pars, Wo, Ph)
% input - 67x1000 double
% xd - 2x1 double
% d - scalar
% pars - 7x1 double
% Wo - 2x4 double
% Ph - 4x19 double

dim  = size(Ph, 2);
sz   = size(input, 2);
x = zeros(2,1,sz);  w1 = zeros(4,1,sz);    w2 = w1;  dq = zeros(dim, 1, sz);    u = dq;    q = dq;    fun = zeros(67, sz);
x(:, 1, :) = input(1:2, :);
w1(:, 1, :)  = input(3:6, :);   w2(:, 1, :)  = input(7:10, :);
dq(:, 1, :)  = input(11:29, :);      u(:, 1, :)  = input(30:48, :);    q(:, 1, :)  = input(49:67, :);
wh = cat(2, w1, w2);
f1 = x + d * pagemtimes(Wo * Ph, u);
common_term = pagemtimes(Ph, pagemtimes(pagemtimes(dq, permute(dq, [2,1,3])), Ph'));
f2 = w1 + d * -pars(1) * permute( pagemtimes(permute(w1 - Wo(1, :)', [2,1,3]), common_term), [2,1,3]);
f3 = w2 + d * -pars(1) * permute( pagemtimes(permute(w2 - Wo(2, :)', [2,1,3]), common_term), [2,1,3]);
f4 = dq + d * (-pars(7)*dq + u) + sqrt(d) * pars(6) * randn(dim, 1, sz);
f5  = u + d * -pars(2) * ( pagemtimes( pagemtimes(pagemtimes(Ph', pagemtimes(wh, permute(wh, [2,1,3]))), Ph) + pars(3)*eye(dim), u) - pars(4) * pagemtimes(pagemtimes(Ph', wh), (xd - x)) ) + sqrt(d) * pars(5) * randn(dim, 1, sz);
f6  = q + d * u;
fun(:,:) = cat(1, f1, f2, f3, f4, f5, f6);
end

Edit: This MATLAB function is trying to compute a function value for 1000 data points (input). W is a 2x4x1000 double. input here is [x; w1; w2; dq; u; q] where W is factored as w1 and w2 to vectorize it. p_i are the pars(i)

[James Tursa]

Can you add some explanatory text stating what the calculation is, maybe with a general equation etc.? I would note that all of your permute( ) and indexing and cat( ) stuff results in deep data copies (performance drag), so my first suggestion would be to rearrange your data up front to maybe avoid some or all of this, but you could help us by showing at a higher level what the calculations are doing.

[Ankur Kamboj]

Not sure if it helps, but the function is basically evaluating a mathematical function for some 1000 67x1 inputs (Edited into the OP).

I'll try to see if avoiding permute() and cat() could result in any performanc gains. Thanks!

Answer 1

[Matt J]

Don't use permute(___,[2,1,3]) to transpose the pages in conjunction with pagemtimes. Use the transposition flags,

Z = pagemtimes(X,transpX,Y,transpY)

[Ankur Kamboj]

I don't know how I missed this in pagemtimes() documentation. This helped, but only slightly. Thanks!

[Matt J]

Also, you have cascades of pagemtimes operations that are implementing lots of outer products from left to right. This is a bad idea. Given column N-vectors x and y, it is never good to implement (x*x')*y. It is much more efficient to implement x*(x'*y). The former requires O(N^2) multiplications while the latter requires O(N).

With this in mind, you can simplify the computation of f2 and f3 as follows, which I find gives about a 2x speed-up:

%common_term = pagemtimes(Ph, pagemtimes(pagemtimes(dq, permute(dq, [2,1,3])), Ph'));

Ph_dq=reshape(Ph*squeeze(dq),[],1,sz);

 dW1=w1 - Wo(1, :)';
 dW2=w2 - Wo(2, :)';
 
f2 = w1 + d * -pars(1).* sum(Ph_dq.*dW1,1).*Ph_dq;
                                  
f3 = w2 + d * -pars(1) .* sum(Ph_dq.*dW2,1).*Ph_dq;

I have similar concerns about f5, but to know how best to handle it, we need to know what you plan to use it for. If it's going to be multiplied with a series of 1000 vectors, you can collapse the outer products in a similar way.

[Matt J]

I have similar concerns about f5, but to know how best to handle it, we need to know what you plan to use it for

But one thing that's for sure is you will not build the matrix if you are merely going to be multiplying it with u. You will instead re-express the product as,

[Ankur Kamboj]

Just implemented what you suggested for f2 and f3, and it really is more than 2x the speedup. Thank you!! I am still trying to wrap my head around how the elementwise multiplication and the sum operation equate to the f2 and f3's analytical expressions.

But I get the gist, vector-matrix multiplication are much faster than any matrix-matrix ones. I'll try to chalk up a similar expression for f5 as well. Going through the profiler, f5 is the only one left that's eating up the majority of computation time.

Again, much thanks! This saved me a lot of time, trouble, and research.