How to store a symmetric matrix?

Question

Which is the best way to store a symmetric matrix in memory?

It would be good to save half of the space without compromising speed and complexity of the structure too much. This is a language-agnostic question but if you need to make some assumptions just assume it's a good old plain programming language like C or C++..

It seems a thing that has a sense just if there is a way to keep things simple or just when the matrix itself is really big, am I right?

Just for the sake of formality I mean that this assertion is always true for the data I want to store

matrix[x][y] == matrix[y][x]

Answer 1

Well I would try a triangular matrix, like this:

int[][] sym = new int[rows][];
for( int i = 0; i < cols; ++i ) {  
     sym=new int[i+1];
}

But then you wil have to face the problem when someone wants to access the "other side". Eg he wants to access [0][10] but in your case this val is stored in[10][0] (assuming 10x10).

The probably "best" way is the lazy one - dont do anything until the user requests. So you could load the specific row if the user types somethin like print(matrix[4]).

Answer 2

If you're using something that supports operator overloading (e.g. C++), it's pretty easy to handle this transparently. Just create a matrix class that checks the two subscripts, and if the second is greater than the first, swap them:

template <class T>
class sym_matrix { 
    std::vector<std::vector<T> > data;
public:
    T operator()(int x, int y) {
        if (y>x)
            return data[y][x];
        else
            return data[x][y];
    }
};

For the moment I've skipped over everything else, and just covered the subscripting. In reality, to handle use as both an lvalue and an rvalue correctly, you'll typically want to return a proxy instead of a T directly. You'll want a ctor that creates data as a triangle (i.e., for an NxN matrix, the first row will have N elements, the second N-1, and so on -- or, equivalantly 1, 2, ...N). You might also consider creating data as a single vector -- you have to compute the correct offset into it, but that's not terribly difficult, and it will use a bit less memory, run a bit faster, etc. I'd use the simple code for the first version, and optimize later if necessary.

Answer 3

You could use a staggered array (or whatever they're called) if your language supports it, and when x < y, switch the position of x and y. So...

Pseudocode (somewhat Python style, but not really) for an n x n matrix:

matrix[n][]

for i from 0 to n-1:
    matrix[i] = some_value_type[i + 1]

[next, assign values to the elements of the half-matrix]

And then when referring to values....

if x < y:
    return matrix[y][x]
else:
    return matrix[x][y]

Answer 4

I find that many high performance packages just store the whole matrix, but then only read the upper triangle or lower triangle. They might then use the additional space for storing temporary data during the computation.

However if storage is really an issue then just store the n(n+1)/2 elements making the upper triangle in a one-dimensional array. If that makes access complicated for you, just define a set of helper functions.

In C to access a matrix matA you could define a macro:

#define A(i,j, dim) ((i <= j)?matA[i*dim + j]:matA[j*dim + i])

then you can access your array nearly normally.

Answer 5

If you want to use a one dimensional array the code would look something like this:

int[] new matrix[(rows * (rows + 1 )) >> 1];
int z;
matrix[ ( ( z = ( x < y ? y : x ) ) * ( z + 1 ) >> 1 ) + ( y < x ? y : x ) ] = yourValue; 

You can get rid of the multiplications if you create an additional look-up table:

int[] new matrix[(rows * (rows + 1 )) >> 1];
int[] lookup[rows];
for ( int i= 0; i < rows; i++)
{
   lookup[i] = (i * (i+1)) >> 1;
}
matrix[ lookup[ x < y ? y : x ] + ( x < y ? x : y )  ] = yourValue;