Atomic sparse-matrix-multiply-and-compare за избягване на грешка при липса на памет

Имам две разредени матрици A (логическа, 80274 x 80274) и B (неотрицателно цяло число, 21018 x 80274) и вектор c (положително цяло число, 21018 x 1).

Бих искал да намеря резултата res (логичен, 21018 x 80274) на

mat = B * A;
res = mat > sparse(diag(c - 1)) * spones(mat);

# Note that since c is positive, this is equivalent to
# res = bsxfun(@gt, mat, c-1)
# but octave's sparse bsxfun support is somewhat shoddy,
# so I'm doing this instead as a workaround

Проблемът е, че B * A има достатъчно ненулеви стойности (мисля, че 60824321, което не изглежда много, но по някакъв начин изчислението на spones(mat) използва повече от гигабайт памет преди октавни сривове), за да изчерпи цялата памет на моята машина въпреки че повечето от тях не надвишават c-1.

Има ли начин да направите това, без да изчислявате междинната матрица mat = B * A?

ПОЯСНЕНИЕ: Вероятно няма значение, но B и c всъщност са двойни матрици, които случайно съдържат само цели числа (и B е разреден).


person dspyz    schedule 14.10.2013    source източник
comment
Какво е spdiag? Мога да намеря само spdiags в документа и все пак изглежда, че няма много смисъл да го прилагам към вектор?   -  person Luis Mendo    schedule 15.10.2013
comment
За съжаление spdiag е отхвърлена функция. Това е еквивалентно на sparse(diag(x)), но аз го предпочитам, защото не се опитва да създаде пълна матрица, когато x е логически вектор. Не е от значение за този проблем, така че ще го променя.   -  person dspyz    schedule 15.10.2013


Отговори (2)


Не можете ли просто да работите върху ненулевите стойности на mat? (за нулевите стойности знаете, че резултатът ще бъде 0):

c = c(:); % make c a column
ind = find(mat>0); % linear index
[row, ~] = ind2sub(size(mat),ind); % row index within mat (for use in c)
res = mat(ind) > c(row)-1; % results for the nonzero values of mat
person Luis Mendo    schedule 14.10.2013
comment
Мога, но това не решава проблема. Проблемът е, че mat има твърде много ненулеви стойности, за да се побере в паметта. Искам да заобиколя частта, в която изчислявам mat или поне да го направя на парчета. - person dspyz; 15.10.2013
comment
Тогава вероятно имате нужда от цикъл (над n, да речем), за да изчислите всеки ред от mat като B(n,1)*A и след това да го сравните с c(n)-1. Или можете да работите на партиди от толкова редове, колкото паметта ви може да управлява: bsxfun(@gt, B(1:1000,1)*A, c(1:1000)-1), след това bsxfun(@gt, B(1001:2000,1)*A, c(1001:2000)-1) и т.н. - person Luis Mendo; 15.10.2013

Можете да опитате да актуализирате до Octave 3.8.1, bsxfun е актуализиран, за да бъде оскъдно осведомен, това значително подобрява представянето!

person gaborous    schedule 20.06.2014