Можно ли сохранить только половину симметричной матрицы для сохранения памяти? - PullRequest
Новая
       28

Можно ли сохранить только половину симметричной матрицы для сохранения памяти?

5 голосов
/ 07 июня 2011

Существует большая матрица, которая используется в проблеме типа Ax=b. A симметрично.Есть ли какой-нибудь алгоритм, позволяющий нам сохранять только половину матрицы и выполнять над ней операции типа x=A\b?

Ответы [ 3 ]

6 голосов
/ 07 июня 2011

Вы сэкономите только половину памяти, но вы можете сделать это, создав плоскую версию матрицы, сохранив ее, а затем расправив ее.Требуемое дополнительное время, вероятно, не стоит экономить, учтите: 

% pretend this is symettric...
A = rand(10, 10);

% store it as a flat list
flatA = [];
for k = 1:size(A,1)
    flatA = [flatA; A([1:k],k)];
end

save('flatA.mat', 'flatA');

% undo
N = (-1 + (1+4*2*length(flatA))^0.5)/2;
newA = NaN(N,N); 
cur = 1;
for k = 1:N
    len = k;
    newA(1:len, k) = flatA(cur:cur+len-1);
    cur = cur + len;
end
% real A cannot have NaNs or this trick fails
newA(isnan(newA)) = newA(isnan(newA'))';
3 голосов
/ 07 июня 2011

Вот идея, но я ее не проверял.Если ваша симметричная матрица положительно определена, выполните разложение Холецкого симметричной матрицы A, чтобы получить A = U * U '.Если вы храните U как разреженную матрицу, используя встроенную разреженную матрицу MATLAB, у вас есть все, что вам нужно, и вы использовали примерно половину памяти.Поскольку он использует тип разреженной матрицы MATLAB, вы работаете с ним, используя стандартные функции MATLAB, если вы помните, что A = U * U '

Например, для вычисления A * x = b используйте x =U '\ U \ б.В отличие от других предложенных решений, MATLAB никогда не будет использовать внутреннюю полную матрицу, и даже будет использовать ускоренные решатели, которые воспользуются тем, что вы решаете только с треугольными.Стоимость состоит в том, что для решения одной системы вы фактически запускаете оператор обратной косой черты (см. Выше).Однако это цена, которую вы платите за то, что никогда не создаете полную матрицу.

1 голос
/ 07 июня 2011

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

% Create a symmetric matrix
A = rand(1000);
A = A + A';

% Extract the upper triangular part
B = sparse(triu(A))              % This is the important line, the rest is just checking.

% Undo
BB = full(B);
C = BB + BB' - diag(diag(BB));

% Check correct
assert(all(A(:) == C(:)));

% Save matrices
save('A.mat', 'A');
save('B.mat', 'B');

% Get file sizes
infoA = dir('A.mat'); infoA.bytes
infoB = dir('B.mat'); infoB.bytes

РЕДАКТИРОВАТЬ, чтобы уточнить вещи для щепы

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

b = rand(1000);
fullTriUA = triu(A);
sparseTriUA = sparse(fullTriUA);  %same as B above
fullResult = fullTriUA\b;
sparseResult = sparseTriUA\b;
assert(all(fullResult(:) == sparseResult(:)))
...