5

Ax=b型の問題 で使用される大きな行列があります。Aは対称です。行列の半分だけを保存して、そのような操作を行うアルゴリズムはありますx=A\bか?

4

3 に答える 3

6

メモリの半分しか節約できませんが、マトリックスのフラット バージョンを作成し、それを保存してから、フラット化を解除することでこれを行うことができます。余分な時間が必要なため、おそらく節約する価値はありません。

% 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'))';
于 2011-06-07T09:25:32.370 に答える
3

これがアイデアですが、私はそれをテストしていません。対称行列が正定値の場合、対称行列Aのコレスキー分解を実行してA = U *U'を求めます。MATLABの組み込みスパース行列を使用してUをスパース行列として格納すると、必要なものがすべて揃っており、メモリの約半分を使用しています。MATLABのスパース行列型を使用しているため、A = U * U'であることを覚えている限り、標準のMATLAB関数を使用して操作できます。

たとえば、A * x = bを計算するには、x = U'\ U\bを使用します。他の提案されたソリューションとは異なり、MATLABは実際に完全な行列を内部で使用することはなく、三角形のみで解くという事実を利用する加速ソルバーも使用します。コストは、単一のシステムを解決するために、実際にバックスラッシュ演算子を2回実行していることです（上記を参照）。ただし、これは、完全なマトリックスをインスタンス化しない場合に支払う代償です。

于 2011-06-07T17:38:07.697 に答える
1

上三角部分を抽出してスパース行列に変換すると、メモリを節約できます。この手法はかなり高速です。

% 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(:)))
于 2011-06-07T10:35:32.987 に答える