Tag: ‘

Finding matrix position from vector address

I have a symmetric matrix, which is stored as a vector containing only the needed elements. Is there an easy way to go from vector address to positions in the matrix?

The same operation on a square matrix stored in this way is done by:

(1)   \begin{equation*} x = v \mod{n} \end{equation*}

and

(2)   \begin{equation*} y = \frac{v}{m} \end{equation*}

Where v is the position in the vector, and m and n matrix columns and rows. This also conveniently reduces to bit shifts and masking if m and n are powers of 2. Operations are of course Integer operations.

My question is whether there exists a similar simple operation on a vector containing just one of the parts of a symmetric matrix.

 

Example of problem
Symmetric matrix stored in vector, not necessarily the best way to store it but one of many possibilities.

One opportunity is to use that the amount of elements needed to store a symmetric matrix is given by:

(3)   \begin{equation*} \frac{n(n+1)}{2} \end{equation*}

Using this one can iteratively search over n until the vector address is contained in the current block of inspected data. Then the remaining elements along with the amount of removed elements give the position. The problem is that this is n operations in a linear search, or log(n) operations if binary search is used.

so I’m wondering if there is an easier way to do this. Basically what I want is a very quick algorithm from vector position to matrix position.

Possibly useful observations are that the result from. n(n+1)/2 can always be divided by the odd component part of n and n+1, as well as the even component divided by two.

Also the resulting triangle can be divided into a structured amount s of square areas of values w:

(4)   \begin{equation*} s = 2^i \end{equation*}

(5)   \begin{equation*} w = \lfloor\frac{(n+2^i)}{2^{(i+1)}}^2\rfloor \end{equation*}

Where i is the squares where 0 is the largest square, and larger i gives the next smaller one. n is from the original matrix m and n. When the result is zero no more squares are needed to describe the area.

How this can be turned into a storage and addressing scheme, I do not know, and I wonder if there is no faster way (the binary search) to recover a position (without storing them beforehand) when something is stored in this manner?

Note that I’m not discussing packing and unpacking the entire matrix here (which would be O(n) using the linear search method from above), but finding the position of a single element from its position in the vector.