Câu hỏi liên quan

0 Phiếu
0 Câu trả lời
0 Phiếu
0 Câu trả lời
0 Phiếu
0 Câu trả lời
0 Phiếu
4 Câu trả lời

matlab/octave - Generalized matrix multiplication


0 Phiếu
Đã hỏi 24/5/2016 bởi Gb2297 (130 điểm)
Tôi muốn làm một function để khái quát matrix nhân. Về cơ bản, nó có thể làm các phép nhân chuẩn matrix , nhưng nó sẽ cho phép thay đổi hai nhị phân sử dụng sản phẩm/tổng hợp bởi bất kỳ chức năng nào khác. Mục đích là để như là hiệu quả nhất có thể, cả về CPU và bộ nhớ. Tất nhiên, nó sẽ luôn luôn là ít hiệu quả hơn A * B, nhưng linh hoạt sử dụng điểm ở đây. Dưới đây là một vài lệnh tôi có thể đi lên sau khi đọc khác nhau thú vị chủ đề của :
A = randi(10, 2, 3);
B = randi(10, 3, 4);
% 1st method
C = sum(bsxfun(@mtimes, permute(A,[1 3 2]),permute(B,[3 2 1])), 3)
% Alternative: C = bsxfun(@(a,b) mtimes(a',b), A', permute(B, [1 3 2]))
% 2nd method
C = sum(bsxfun(@(a,b) a*b, permute(A,[1 3 2]),permute(B,[3 2 1])), 3)
% 3rd method (Octave-only)
C = sum(permute(A, [1 3 2]) .* permute(B, [3 2 1]), 3)
% 4th method (Octave-only): multiply nxm A with nx1xd B to create a nxmxd array
C = bsxfun(@(a, b) sum(times(a,b)), A', permute(B, [1 3 2]));
C = C2 = squeeze(C(1,:,:)); % sum and turn into mxd
vấn đề với phương pháp 1-3 là họ sẽ tạo ra n ma trận trước khi sụp đổ chúng bằng cách sử dụng sum(). 4 là tốt hơn bởi vì nó không sum() bên trong bsxfun, nhưng bsxfun vẫn tạo ra n ma trận (ngoại trừ một điều là chúng chủ yếu có sản phẩm nào, có chứa chỉ là một véc tơ của các giá trị Zero là các khoản tiền, phần còn lại được làm đầy với 0 để phù hợp với yêu cầu kích thước). Những gì tôi muốn là một cái gì đó như 4 method nhưng không vô dụng 0 để phụ tùng nhớ. Bất cứ ý tưởng?

4 Câu trả lời

0 Phiếu
Đã trả lời 03/6/2016 bởi Ybpadina (580 điểm)
Mà không lặn vào các chi tiết, có các công cụ như mtimesx MMX matrix nhanh thông dụng và thói quen vô hướng hoạt động. Bạn có thể nhìn vào code của họ và họ thích ứng với nhu cầu của bạn. Nó có nhiều khả năng sẽ nhanh hơn so với của matlab bsxfun.
0 Phiếu
Đã trả lời 03/6/2016 bởi qbrRydin (140 điểm)
Mà không lặn vào các chi tiết, có các công cụ như mtimesx MMX matrix nhanh thông dụng và thói quen vô hướng hoạt động. Bạn có thể nhìn vào code của họ và họ thích ứng với nhu cầu của bạn. Nó có nhiều khả năng sẽ nhanh hơn so với của matlab bsxfun.
0 Phiếu
Đã trả lời 03/6/2016 bởi Blixt_fol (100 điểm)
Dưới đây là một phiên bản nhẹ hơn bóng của các giải pháp mà bạn đăng, với một số cải tiến nhỏ. Chúng tôi kiểm tra nếu chúng tôi có nhiều hàng hơn cột hoặc ngược lại, và sau đó làm nhân cho phù hợp bằng cách chọn hoặc nhân hàng với ma trận hoặc ma trận với cột (do đó làm số lượng ít nhất là loop lặp đi lặp lại). A*B lưu ý: điều này có thể không luôn luôn là các chiến lược tốt nhất (đi theo hàng thay vì theo cột) ngay cả khi có ít hàng hơn cột; một thực tế rằng MATLAB mảng được lưu trữ trong một đơn đặt hàng cột chính trong bộ nhớ làm cho nó hiệu quả hơn để cắt theo cột, như các yếu tố được lưu trữ liên tiếp. Trong khi truy cập vào hàng liên quan đến việc vượt qua các yếu tố của bước tiến dài (mà không phải là thân thiện với bộ đệm ẩn--nghĩ không gian địa phương ). ngoài ra, code nên xử lý đôi/đơn, real/phức tạp, đầy đủ/thưa thớt (và sai sót mà nó không phải là một sự kết hợp có thể). Nó cũng tôn trọng các ma trận sản phẩm nào và kích thước 0.
function C = my_mtimes(A, B, outFcn, inFcn)
    % default arguments
    if nargin < 4, inFcn = @times; end
    if nargin < 3, outFcn = @sum; end
    % check valid input
    assert(ismatrix(A) && ismatrix(B), 'Inputs must be 2D matrices.');
    assert(isequal(size(A,2),size(B,1)),'Inner matrix dimensions must agree.');
    assert(isa(inFcn,'function_handle') && isa(outFcn,'function_handle'), ...
        'Expecting function handles.')
    % preallocate output matrix
    M = size(A,1);
    N = size(B,2);
    if issparse(A)
        args = {'like',A};
    elseif issparse(B)
        args = {'like',B};
    else
        args = {superiorfloat(A,B)};
    end
    C = zeros(M,N, args{:});
    % compute matrix multiplication
    % http://en.wikipedia.org/wiki/Matrix_multiplication#Inner_product
    if M < N
        % concatenation of products of row vectors with matrices
        % A*B = [a_1*B ; a_2*B ; ... ; a_m*B]
        for m=1:M
            %C(m,:) = A(m,:) * B;
            %C(m,:) = sum(bsxfun(@times, A(m,:)', B), 1);
            C(m,:) = outFcn(bsxfun(inFcn, A(m,:)', B), 1);
        end
    else
        % concatenation of products of matrices with column vectors
        % A*B = [A*b_1 , A*b_2 , ... , A*b_n]
        for n=1:N
            %C(:,n) = A * B(:,n);
            %C(:,n) = sum(bsxfun(@times, A, B(:,n)'), 2);
            C(:,n) = outFcn(bsxfun(inFcn, A, B(:,n)'), 2);
        end
    end
end

so sánh

function là không có nghi ngờ chậm hơn trong suốt, nhưng đối với kích thước lớn hơn đó là đơn đặt hàng của các cường độ tồi tệ hơn phép nhân ma trận được xây dựng trong:
        (tic/toc times in seconds)
      (tested in R2014a on Windows 8)
    size      mtimes       my_mtimes 
    ____    __________     _________
     400     0.0026398       0.20282
     600      0.012039       0.68471
     800      0.014571        1.6922
    1000      0.026645        3.5107
    2000       0.20204         28.76
    4000        1.5578        221.51
mtimes_vs_mymtimes đây là đoạn code test :
sz = [10:10:100 200:200:1000 2000 4000];
t = zeros(numel(sz),2);
for i=1:numel(sz)
    n = sz(i); disp(n)
    A = rand(n,n);
    B = rand(n,n);
    tic
    C = A*B;
    t(i,1) = toc;
    tic
    D = my_mtimes(A,B);
    t(i,2) = toc;
    assert(norm(C-D) < 1e-6)
    clear A B C D
end
semilogy(sz, t*1000, '.-')
legend({'mtimes','my_mtimes'}, 'Interpreter','none', 'Location','NorthWest')
xlabel('Size N'), ylabel('Time [msec]'), title('Matrix Multiplication')
axis tight

phụ

cho đầy đủ, dưới đây là hai cách ngây thơ thêm để thực hiện phép nhân tổng quát matrix (nếu bạn muốn so sánh hiệu suất, thay thế phần cuối của my_mtimes function với một số này). Tôi sẽ thậm chí không bận tâm đăng của thời gian đã qua :)
C = zeros(M,N, args{:});
for m=1:M
    for n=1:N
        %C(m,n) = A(m,:) * B(:,n);
        %C(m,n) = sum(bsxfun(@times, A(m,:)', B(:,n)));
        C(m,n) = outFcn(bsxfun(inFcn, A(m,:)', B(:,n)));
    end
end
và khác (với một ba-loop):
C = zeros(M,N, args{:});
P = size(A,2); % = size(B,1);
for m=1:M
    for n=1:N
        for p=1:P
            %C(m,n) = C(m,n) + A(m,p)*B(p,n);
            %C(m,n) = plus(C(m,n), times(A(m,p),B(p,n)));
            C(m,n) = outFcn([C(m,n) inFcn(A(m,p),B(p,n))]);
        end
    end
end

những gì để thử tiếp theo?

Others have already mentioned a couple of submissions on the File Exchange that implement general-purpose matrix routines as MEX-files (see @natan's answer). Those are especially effective if you link them against an optimized BLAS library.
Đã bình luận 04/6/2016 bởi can8497 (1,630 điểm)
tại sao không thử một cái gì đó bằng cách sử dụng ma trận thưa thớt do đó bạn sẽ tiết kiệm bộ nhớ phân bổ? bạn có thể nhận được rằng để làm việc. [spfun] (http://www.mathworks.com/help/matlab/ref/spfun.html) cũng tương tự như bsxfun, nhưng cho ma trận thưa thớt do đó, tôi giả sử nó giữ sử dụng bộ nhớ khá thấp dưới nền là tốt.
Đã bình luận 05/6/2016 bởi fub_8730 (750 điểm)
Đã được thực hiện, và thực sự method 4 nên có thể mất lợi nhuận của sparseness, nhưng unluckily nó sẽ không làm việc với Octave là operator bsxfun của nó không phải là thân thiện thưa thớt, do đó, tất cả mọi thứ sẽ được lưu trữ trong bộ nhớ.
Đã bình luận 05/6/2016 bởi Vsong (100 điểm)
Ví dụ 3 và thứ 4 của bạn không làm việc. Ví dụ 1 của bạn không hoạt động trên MATLAB R2010b và cũ hơn.
0 Phiếu
Đã trả lời 03/6/2016 bởi You_5838 (260 điểm)
Dưới đây là một phiên bản nhẹ hơn bóng của các giải pháp mà bạn đăng, với một số cải tiến nhỏ. Chúng tôi kiểm tra nếu chúng tôi có nhiều hàng hơn cột hoặc ngược lại, và sau đó làm nhân cho phù hợp bằng cách chọn hoặc nhân hàng với ma trận hoặc ma trận với cột (do đó làm số lượng ít nhất là loop lặp đi lặp lại). A*B lưu ý: điều này có thể không luôn luôn là các chiến lược tốt nhất (đi theo hàng thay vì theo cột) ngay cả khi có ít hàng hơn cột; một thực tế rằng MATLAB mảng được lưu trữ trong một đơn đặt hàng cột chính trong bộ nhớ làm cho nó hiệu quả hơn để cắt theo cột, như các yếu tố được lưu trữ liên tiếp. Trong khi truy cập vào hàng liên quan đến việc vượt qua các yếu tố của bước tiến dài (mà không phải là thân thiện với bộ đệm ẩn--nghĩ không gian địa phương ). ngoài ra, code nên xử lý đôi/đơn, real/phức tạp, đầy đủ/thưa thớt (và sai sót mà nó không phải là một sự kết hợp có thể). Nó cũng tôn trọng các ma trận sản phẩm nào và kích thước 0.
function C = my_mtimes(A, B, outFcn, inFcn)
    % default arguments
    if nargin < 4, inFcn = @times; end
    if nargin < 3, outFcn = @sum; end
    % check valid input
    assert(ismatrix(A) && ismatrix(B), 'Inputs must be 2D matrices.');
    assert(isequal(size(A,2),size(B,1)),'Inner matrix dimensions must agree.');
    assert(isa(inFcn,'function_handle') && isa(outFcn,'function_handle'), ...
        'Expecting function handles.')
    % preallocate output matrix
    M = size(A,1);
    N = size(B,2);
    if issparse(A)
        args = {'like',A};
    elseif issparse(B)
        args = {'like',B};
    else
        args = {superiorfloat(A,B)};
    end
    C = zeros(M,N, args{:});
    % compute matrix multiplication
    % http://en.wikipedia.org/wiki/Matrix_multiplication#Inner_product
    if M < N
        % concatenation of products of row vectors with matrices
        % A*B = [a_1*B ; a_2*B ; ... ; a_m*B]
        for m=1:M
            %C(m,:) = A(m,:) * B;
            %C(m,:) = sum(bsxfun(@times, A(m,:)', B), 1);
            C(m,:) = outFcn(bsxfun(inFcn, A(m,:)', B), 1);
        end
    else
        % concatenation of products of matrices with column vectors
        % A*B = [A*b_1 , A*b_2 , ... , A*b_n]
        for n=1:N
            %C(:,n) = A * B(:,n);
            %C(:,n) = sum(bsxfun(@times, A, B(:,n)'), 2);
            C(:,n) = outFcn(bsxfun(inFcn, A, B(:,n)'), 2);
        end
    end
end

so sánh

function là không có nghi ngờ chậm hơn trong suốt, nhưng đối với kích thước lớn hơn đó là đơn đặt hàng của các cường độ tồi tệ hơn phép nhân ma trận được xây dựng trong:
        (tic/toc times in seconds)
      (tested in R2014a on Windows 8)
    size      mtimes       my_mtimes 
    ____    __________     _________
     400     0.0026398       0.20282
     600      0.012039       0.68471
     800      0.014571        1.6922
    1000      0.026645        3.5107
    2000       0.20204         28.76
    4000        1.5578        221.51
mtimes_vs_mymtimes đây là đoạn code test :
sz = [10:10:100 200:200:1000 2000 4000];
t = zeros(numel(sz),2);
for i=1:numel(sz)
    n = sz(i); disp(n)
    A = rand(n,n);
    B = rand(n,n);
    tic
    C = A*B;
    t(i,1) = toc;
    tic
    D = my_mtimes(A,B);
    t(i,2) = toc;
    assert(norm(C-D) < 1e-6)
    clear A B C D
end
semilogy(sz, t*1000, '.-')
legend({'mtimes','my_mtimes'}, 'Interpreter','none', 'Location','NorthWest')
xlabel('Size N'), ylabel('Time [msec]'), title('Matrix Multiplication')
axis tight

phụ

cho đầy đủ, dưới đây là hai cách ngây thơ thêm để thực hiện phép nhân tổng quát matrix (nếu bạn muốn so sánh hiệu suất, thay thế phần cuối của my_mtimes function với một số này). Tôi sẽ thậm chí không bận tâm đăng của thời gian đã qua :)
C = zeros(M,N, args{:});
for m=1:M
    for n=1:N
        %C(m,n) = A(m,:) * B(:,n);
        %C(m,n) = sum(bsxfun(@times, A(m,:)', B(:,n)));
        C(m,n) = outFcn(bsxfun(inFcn, A(m,:)', B(:,n)));
    end
end
và khác (với một ba-loop):
C = zeros(M,N, args{:});
P = size(A,2); % = size(B,1);
for m=1:M
    for n=1:N
        for p=1:P
            %C(m,n) = C(m,n) + A(m,p)*B(p,n);
            %C(m,n) = plus(C(m,n), times(A(m,p),B(p,n)));
            C(m,n) = outFcn([C(m,n) inFcn(A(m,p),B(p,n))]);
        end
    end
end

những gì để thử tiếp theo?

Others have already mentioned a couple of submissions on the File Exchange that implement general-purpose matrix routines as MEX-files (see @natan's answer). Those are especially effective if you link them against an optimized BLAS library.

ToughDev Q&A là gì?

Trang web hỏi đáp cho các bạn đam mê lập trình, phát triển phần mềm và các vấn đề kỹ thuật khác. Với sự giúp đỡ của bạn, chúng tôi hy vọng sẽ xây dựng thành công một thư viện đầy đủ các câu hỏi và trả lời về tất cả các vấn đề có liên quan đến lập trình!







...