Find maximum intermediate product in matrix multiplication

Hello,

I am in need of an efficient solution for the following problem...

For the matrix product C = A × B, where A is an n x m matrix, and B is an m x p matrix, each element [i,j] in the matrix product C is given by the sum of m products,

C_{i,j} = sum[ A_{ i, k} .* B_{ k, j}]_( k=1,..., m)

I need to find a similar function, that gives the matrix C as the maximum of m products,

C_{i,j} = max[ A_{ i, k} .* B_{ k, j}]_( k=1,..., m)

Actually, I need to find the index k that corresponds to the maximum in each case.

I have found a way to do this using loops, but it is way too slow for what I need. I also found an ugly solution using the kronecker product, but it is also too slow. My matrices, although sparse, are also quite large (m=n~1000 and p<1000).

I have been thinking about this for two weeks, but I haven't found a good solution!

Cheers, Ben

Answer 1

[James Tursa]

Another way using a loop, which avoids the potentially large intermediate result if the dimensions happen to be large.

function K = maxtimes(A,B)
AT = A.'; % gets the product data contiguous in memory
K = zeros(size(A,1),size(B,2));
for j=1:size(B,2)
    [~,k] = max(AT.*B(:,j)); % Uses implicit array expansion
    K(:,j) = k(:);
end
end

If this still isn't fast enough, you may need to resort to a mex routine.

[the cyclist]

In limited testing, this is the superior solution. Mine is going to have an implicit for loop embedded in the guts. As a result, my solution has the peril of the large intermediate result, with probably no upside relative to James' solution.

[Ben Ward]

Thanks! This is about 25 to 50 times faster than the best I could come up with.

Answer 2

[the cyclist]

I believe this does what you want:

A = [1 3; 4 2];
B = [1 3 5; 4 2 6];

tmp = permute(A,[2 3 1]).*B;
[~,tmp2] = max(tmp);

C = permute(tmp2,[3 2 1]);

(Edited to get C permuted to sensible dimensions.)

[Ben Ward]

Thanks! This one won't work for me, as my matrices are sparse.