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:
Where is the position in the vector, and and matrix columns and rows. This also conveniently reduces to bit shifts and masking if and 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.
One opportunity is to use that the amount of elements needed to store a symmetric matrix is given by:
Using this one can iteratively search over 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 operations in a linear search, or 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. can always be divided by the odd component part of and , as well as the even component divided by two.
Also the resulting triangle can be divided into a structured amount of square areas of values :
Where is the squares where 0 is the largest square, and larger gives the next smaller one. is from the original matrix and . 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 using the linear search method from above), but finding the position of a single element from its position in the vector.