Is it possible to save only half of a symmetric matrix to save the memory?

Question

There is a large matrix that is used in Ax=b type problem. A is symmetric. Is there any algorithm to let us save only half of the matrix and do operation like x=A\b on it?

Answer 1

You'll only save half the memory, but you can do this by creating a flat version of the matrix, saving that, then unflattening it. The extra time required probably doesn't make the saving worthwhile, mind:

% 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'))';

Answer 2

Here's an idea, but I haven't tested it out. If your symmetric matrix is positive definite, do a Cholesky decomposition of the symmetric matrix, A, giving you A = U*U'. If you store U as a sparse matrix using MATLAB's builtin sparse matrix, you have everything you need, and you've used roughly half the memory. Since its using MATLAB's sparse matrix type, you have operate on it using standard MATLAB functions, as long as you remember that A = U*U'

For example, to compute A*x = b, use x = U'\U\b. Unlike the other proposed solutions, MATLAB will never be actually using a full matrix internally, and will even use accelerated solvers that will take advantage of the fact that you're only solving with triangular. The cost is that to solve a single system, you've actually running the backslash operator twice (see above). However, that's the price you pay for never instantiating the full matrix.