Find maximum intermediate product in matrix multiplication

Question

Ben Ward 2018-1-3

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/375408-find-maximum-intermediate-product-in-matrix-multiplication

评论： Ben Ward 2018-1-3

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

James Tursa 2018-1-3

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/375408-find-maximum-intermediate-product-in-matrix-multiplication#answer_298580

编辑：James Tursa 2018-1-3

在 MATLAB Online 中打开

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.

2 个评论
显示无隐藏无

the cyclist 2018-1-3

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 2018-1-3

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

请先登录，再进行评论。

Answer 2

the cyclist 2018-1-3

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/375408-find-maximum-intermediate-product-in-matrix-multiplication#answer_298573

编辑：the cyclist 2018-1-3

在 MATLAB Online 中打开

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Ben Ward 2018-1-3

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

请先登录，再进行评论。