Wednesday, 10 August 2016

Reducing the memory usage by flattening the stored symmetric matrices


Content:

1. Introduction.

2. Flattening a symmetric matrix in case all its diagonal elements are zero.

3. Flattening a symmetric matrix with non-zero diagonal.

4. Effectiveness of the flattening.


The square matrix R:

is symmetric if:

With respect to the values of their diagonal elements the following two types of symmetric matrices are used in the scientific practice:

» all diagonal elements are zero (example: the distance matrix of a system ot N atoms):

In this particular case unique are only the elements bellow or above the diagonal, if at least one of them is not zero.

» at least one of the diagonal elements is not zero (example: the matrix of Lennard-Jones cross-parameters for a system of N different types of atoms):

Here unique are only the elements bellow or above the diagonal and the onese on the diagonal, if at least one of the non-diagonal elements is different then zero.

 

The goal of this document is to show an easy and simple method for storing and accessing the elements of these two type of matrices in the computer memory. The idea of the method is to store the 2D array of the symmetric matrix as 1D array containing only the unique elements of the matrix. This method is included in many software products but somehow it is not very popular among most of the scientists who very often write their own scripts and executables. Hopefully this publication could make it more popular.

 

When all diagonal elements of a symmetric matrix are zeros its unique elements are those bellow or above the diagonal (if at least one of them is not zero):

Then the 2D matrix array of the matrix thus defined could be transformed into flattened one (denoted by RFL) by using the schema:

The index (the position) or the element rij in the flatten array RFL, k, is computed according to the rule:

The size (the number of elements) of RFL in this case is N(N-1)/2. Take carefully into account how the values of i and j are passing to the formula used to compute k: i might be less than j. In case i is bigger than j i should be given the value of j and vice versa, because for any symmetric matrix rij=rji.

 

In this case the symmetrix matrix has the following unique elements:

and it could become flattened by means of the following linear storage schema:

The corresponding position of the element rij in the flatten array RFL, k, could be derived this way:

The size (the number of elements) of RFL in this case is N(N+1)/2. Take carefully into account how the values of i and j are passing to the formula used to compute k: i might be equal or less but never bigger than j. In case i is bigger than j i should be given the value of j and vice versa, because for any symmetric matrix rij=rji.

 

The flattening of 2D symmetric matrix explained above uses almost half of the memory required to accomodate all matrix elements, because only the unique ones are taken into account. That effect could be assessed numerically by dividing the size of the flattened array to the total number of elements of the 2D matrix array. In both cases for large matrices the explained method reduces the used amout of memory, α, twice:

» all diagonal elements are zero:

» at least one of the diagonal elements is not zero:

No comments:

Post a Comment