Как избежать большого умножения матриц в Matlab

Question

В моем коде есть две большие матрицы, которые имеют одинаковое количество столбцов и разное количество строк. подобно A(20000X4000) а также B(30000X4000), Оба 0-1 разрежены.

Я должен проверить каждую строку A со всеми строками B и посчитать количество общих 1. Например, если A(1,:)=[0 1 0 1 1] а также B([1 2],:)=[1 1 1 1 1;0 0 0 1 1]Мне нужно получить результат как 3 а также 2,

Предположим, что есть большая 0-1 матрица C(50000X4000) и его строки помечены как любой тип A или введите B, Я должен сравнить все строки A а также B вместе и перечислим 1с. Если число 1 в каждой строке A и B превышает некоторые границы, то я использовал эти строки A и B для остальной части вычисления. Итак, мне даже не нужно хранить A а также Bвсе, что мне нужно, это список пар индексов строк. Что-то вроде [(3,2),(3,5),...] который показывает, что я должен использовать третий ряд A и второй ряд Bтакже треть A и пятая часть B и так далее.

Первое, что пришло мне в голову, было A*B', он дает правильный результат, но практически это очень дорого, а в некоторых случаях сделать это умножение невозможно.

Я преобразовал матрицы в один тип данных, и это стало немного быстрее. Разреженный не помог.

Задача кажется простой, просто считая общие единицы каждого ряда A и все ряды B, но не легко реализовать. Учитывая, что код должен выполнять эту задачу примерно 1000 раз, то это практически невозможно.

Любая идея, как сделать, перечислить общие без умножения? (кстати, петли тоже не помогли).

Благодарю.

Answer 1

Я не знаю, действительно ли это лучше, чем то, что у вас есть, потому что в нем все еще есть цикл for, но если кто-то может выяснить, как удалить этот цикл for, вам стоит пойти дальше.

%  create temp data
A = rand(20000,4000) < 0.5;
B = rand(30000,4000) < 0.5;
counts = zeros(size(A,1),size(B,1),'uint8');
for i = 1:size(A,1)
    counts(i,:) = sum(bsxfun(@eq,A(i,:),B),2);
end

В любом случае, процесс займет много времени, потому что вы сравниваете 30000 строк по 4000 элементов в каждой, 20000 раз или приблизительно 2.4e+12 сравнения. Это огромная задача, и она определенно займет много времени. Возможно, попробуйте использовать параллельные вычисления, если вам нужно, чтобы это было быстрее.

Answer 2

Я сделал несколько тестов; на моей машине (i7-3770 @ 3,40 ГГц) умножение полных матриц размерами 30000 x 4000 и 4000 x 20000 занимает около 55 секунд независимо от содержимого, то же самое, что обнаружил Деннис Джаруддин. Но использование разреженных матриц может ускорить вычисления в зависимости от разреженности. Если я определю степень разреженности r как соотношение между количеством 1По элементам матрицы я получаю следующие результаты:

r      time / s 
0.001   0.07
0.002   0.3
0.005   2.1
0.01    8.3
0.02   25

Вот код, используемый для определения этих чисел:

m = 20000;
n = 4000;
o = 30000;

r = 0.001;

N = round(r * m * n);
A = sparse(randi(m, N, 1), randi(n, N, 1), 1, m, n);

N = round(r * n * o);
B = sparse(randi(o, N, 1), randi(n, N, 1), 1, o, n);

tic
C = A * B';
toc

Answer 3

Если умножение целых матриц невозможно, одна идея состоит в том, чтобы обрабатывать вертикальную полосу за раз. Для каждой полосы вы вычисляете желаемый результат и накапливаете его с результатами предыдущих полос:

A = double(rand(5,300)<.5); %// random data
B = double(rand(4,300)<.5); %// random data

S = 10; %// stripe size
result = zeros(size(A,1),size(B,1)); %// initialize to 0
for s = 1:10:size(A,2) %// each vertical stripe, of width S
    ind = s+(0:S-1);
    result = result +  A(:,ind)*(B(:,ind)).';
end

Проверьте:

>> result

result =

    73    72    62    72
    84    70    79    71
    83    84    76    77
    77    80    77    74
    71    71    70    74

>> A*B.'

ans =

    73    72    62    72
    84    70    79    71
    83    84    76    77
    77    80    77    74
    71    71    70    74

Answer 4

Решение, которое вы попробовали, является оптимальным или почти оптимальным.

Когда я пытаюсь это сделать, это занимает меньше минуты:

A = round(rand(30000,4000));
B = round(rand(20000,4000));
tic,A*B';toc;

Если вам действительно нужно делать это тысячи раз, я могу представить только два сценария:

1. Вам не нужно делать это часто, в этом случае просто дайте запустить, и это будет сделано завтра
2. Вы хотите делать это часто и ускорить процесс, а найти более быстрое решение просто не получится. Если у вас нет очень полезной информации о матрицах, которые вы будете умножать.

Если вы обнаружите, что этот пример умножения намного больше минуты (скажем, более 10 минут), вы, вероятно, используете неэффективно память. В этом случае попытайтесь получить больше оперативной памяти.