Phép nhân của một véc tơ với các ma trận phụ là chậm

Question

Tôi có ma trận cao (ví dụ dưới đây là 10000-by-3000) và tôi muốn lấy các sản phẩm bên trong bằng một tập hợp con các hàng của nó (ví dụ: 500 hàng). Điều này được lặp lại với các hàng khác nhau, được chọn ngẫu nhiên nhiều lần (100 lần trong ví dụ này, nhưng trong thực tế nhiều lần hơn). Nó chỉ ra rằng việc lập chỉ mục A(sub,:) là khá chậm. Trong ví dụ của tôi, tốt hơn là nhân toàn bộ ma trận A (nghĩa là, 10000 hàng) thay vì chọn lọc có chọn và nhân 500 thực sự cần thiết.

Việc tạo ngẫu nhiên các chỉ mục hàng (sub = randperm(10000);sub = sub(1:500);) là giá rẻ tính toán; Tôi đặt nó trong cả hai vòng để công bằng.

A=randn(10000,3000); 
g=zeros(10000,1); 

tic 
for i=1:100 
    sub = randperm(10000); sub = sub(1:500); 
    b=randn(3000,1); 
    g(sub) = g(sub) + A(sub,:)*b; 
end 
toc 
% elapsed time is 1.58 sec 

tic 
for i=1:100 
    sub = randperm(10000); sub = sub(1:500); 
    b=randn(3000,1); 
    g = g + A*b; 
end 
toc 
% elapsed time is 1.28 sec 

Câu hỏi đặt ra là: có cách nào để tăng tốc độ khi chỉ cần một tập con các hàng không?

Answer 1

Thử nhân trên các hàng thay vì các cột. Điều này có thể yêu cầu bạn sắp xếp lại dữ liệu của bạn hoặc áp dụng chuyển vị vô hướng (.') hoặc hai, nhưng vì đó là dạng gốc của mảng, bạn có thể nhận được một tốc độ đáng ngạc nhiên. Ví dụ, hoán đổi kích thước của A và g:

A = randn(3000,10000); 
g = zeros(1,10000); 

tic 
for i = 1:100 
    sub = randperm(10000,500); % Taking @Dan's suggestion 
    b = randn(1,3000);   % b is now a row vector 
    g(sub) = g(sub)+b*A(:,sub); % multiply across rows instead 
end 
toc 

Bạn có thể transpose sản lượng nếu cần thiết. Trên máy tính của tôi, tốc độ này nhanh hơn 50% so với trường hợp đầu tiên của bạn.

Tôi tin rằng ít nhất một trong những lý do cơ bản cho điều này là BLAS/LAPACK có thể sử dụng loop unrolling trong trường hợp này.