Obviously if your matrices are sparse you should move to a sparse matrix implementation. There are packages available that take advantage of symmetry too.
Storage:
Assuming that your matrices are dense, unless your matrices have a more detailed (known) structure, you won't be able to do better than the factor of 2 savings you get from storing only the lower (or upper) triangular part. Depending on the language you're using, you could do this with a simple array of pointers to vectors representing the first part of each row. For example, in C you could create such a representation as:
unsigned int i=0; //loop index
unsigned int n=5; //matrix size, nxn
float *M[n]; //array of pointers to floats
for (i=1; i<=n; i++) {
M[i] = malloc( i * sizeof(float) );
};
The main drawback of this (and other) sparse representation is increased access time for an arbitrary element in the array. Only you can say whether the trade off between storage and access time is worth it for your application. In the case where you're storing the lower triangular part of the matrix, if you want to access M[i][j] you need to first check if j<=i. You could use a helper function such as
float Mval(M,i,j) {
if (j<=i) {
return M[i][j];
}
else {
return M[j][i];
};
};
Matrix multiplications:
Unfortunately, the result of multiplying symmetric matrices is not symmetric unless the matrices commute under multiplication. This means that you will have to perform the full matrix-matrix multiplication as usual and your result will not be symmetric.
If you're ok with approximate results or you know more about the structure of your matrices you may be able to do better. You could search for randomized linear algebra for one potential approximate option.
