0
$\begingroup$

We all know the problem that computation time explodes when simulating systems with big matrices. I got just this problem, but I have the advantage that I know that my matrices are symmetric.

My question is thus:

Do you know a way to decrease computation time if I know that my matrices are symmetry?

What I want in particular are the follwing two things:

  • A representation for my symmetric matrices which uses only the relevant entries
  • An algorithm that lets me efficiently multiply two matrices in this representation
$\endgroup$
  • 4
    $\begingroup$ How big? Sparse or dense? Are you trying to solve linear systems, eigenvalue problems, or something else? Symmetry may only buy you a factor of 2 or so due to storage and data motion considerations, and it comes at the cost of implementation complexity. There are, however, some algorithms (CG, but there are additional constraints) that only work for symmetric problems, so there are some possible algorithmic choices that can take advantage of symmetry. Multiplying matrices is often not what you want, often the action of a matrix on a vector is sufficient. Etc. $\endgroup$ – Bill Barth May 29 '14 at 14:04
  • $\begingroup$ The matrix contains 1000+ elements, limited by the simulation time. As I said, I know that the matrix is symmetric, nothing else. So not sparse. I use only three operations: the trace of a matrix, multiplying and adding matrices. $\endgroup$ – physicsGuy May 30 '14 at 6:40
  • $\begingroup$ I do not need the action of the matrix on a vector. $\endgroup$ – physicsGuy May 30 '14 at 6:44
  • 1
    $\begingroup$ What are you trying to achieve? There may be a better way than doing what you're doing, and if you tell us what your goals are, maybe we can steer you to better techniques. 1000-element dense matrices are pretty small, in the grand scheme of things. $\endgroup$ – Bill Barth May 30 '14 at 11:40
  • $\begingroup$ A matrix with only ~1000 elements is something like 32x32. This is quite small compared to truly large matrices which may be something like 1E6x1E6. You certainly shouldn't have issues with storage space unless you have hundreds or thousands of these matrices that you have to deal with simultaneously. Unless you can tell us more about your application, the answer seems to be "Just use the full matrices." $\endgroup$ – Doug Lipinski May 30 '14 at 15:51
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

If you're using a library like LAPACK, I think you'll find there are specific routines for symmetric matrices, in addition to those that work for completely general inputs. These are intended to be more efficient (in time and/or storage).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.