Menu
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] 
564
An efficient data structure for storing dense, symmetric matrices is a simple linear array.
Consider the given matrix B, that is, a square matrix that is equal to the transposed form of that matrix, called a symmetric matrix. This can be represented as: If B = [bij]n×n [ b i j ] n × n is the symmetric matrix, then bij b i j = bji b j i for all i and j or 1 ≤ i ≤ n, and 1 ≤ j ≤ n.
A symmetric matrix is one that equals its transpose. This means that a symmetric matrix can only be a square matrix: transposing a matrix switches its dimensions, so the dimensions must be equal. Therefore, the option with a non square matrix, 2x3, is the only impossible symmetric matrix.
The dimension of symmetric matrices is n(n+1)2 because they have one basis as the matrices {Mij}n≥i≥j≥1, having 1 at the (i,j) and (j,i) positions and 0 elsewhere. For skew symmetric matrices, the corresponding basis is {Mij}n≥i>j≥1 with 1 at the (i,j) position, −1 at the (j,i) position, and 0 elsewhere.
Here is a good method to store a symmetric matrix, it requires only N(N+1)/2 memory:
int fromMatrixToVector(int i, int j, int N) { if (i <= j) return i * N - (i - 1) * i / 2 + j - i; else return j * N - (j - 1) * j / 2 + i - j; } For some triangular matrix
0 1 2 3 4 5 6 7 8 9 1D representation (stored in std::vector, for example) looks like as follows:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] And call fromMatrixToVector(1, 2, 4) returns 5, so the matrix data is vector[5] -> 5.
For more information see http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm
173
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
