symmetric matrix half vectorization

0
votes

I am facing an issue concerning how to store the lower triangular factor of a given symmetric matrix (it's a distance matrix) into a vector.

Generally, I would like directly generating the lower triangular entries by only giving the coordinates (Y,Z) of a set of points on a rectangular grid: and actually it's where I got terribly stuck.

So that, I started thinking to attack the problem from a slightly different point of view: generating the full distance matrix (again given the (Y,Z) couples) and then half vectorize the distance matrix.

Nevertheless, I don't really have a sound idea on how to achieve the goal by means of for loops.

Besides I also know that there may be any external Java library which implements the vech function: vech returns the vector obtained by eliminating all supradiagonal elements of the square matrix X and stacking the result one column above the other. This has uses in matrix calculus where the underlying matrix is symmetric and it would be pointless to keep values above the main diagonal.

Substantially, given a matrix A = {{a,c},{b,d}}, by applying vech(A), the result will be vech(A) = {a,b,d}.

EDIT

I mean something like the following:

    a11 a12 a13 a14
        a22 a23 a24
 A=         a33 a34  (aij = aji)
                a44

Packed storage of the upper triangle of A:

  AP = { a11, a12, a22, a13, a23, a33, a14, a24, a34, a44 }
3
javamatrix
For your last sentence; what have you tried so far? - Oliver Charlesworth
@OliCharlesworth: I've tried several for loops, but no success, I will edit my question including my tryout. - fpe
I suggest swapping your question around - Ask how to do this using standard for-loops first, then mention that you'd also like to know about a library, otherwise this question tends towards being not constructive. - Bernhard Barker

3 Answers

2
votes
public static double[] vech(double[][] a) {
    int na = Math.min(a.length, a[0].length); // Dimension of the matrix
    int nv = na * (na + 1) / 2; // 1 + 2 + 3 + .. + na
    double[] v = new double[nv];
    int k = 0; // index in v.
    for (int i = 0; i < na; ++i) {
        for (int j = 0; j <= i; ++j) {
            v[k] = a[i][j];
            ++k;
        }
    }
    return v;
}

Case 2x2 Matrix:

Picks [0][0], [1][0], [1][1] (skipping [0][1])

Row-major order: (C, C#, Java) a[i][j] is element at row i, column j.

The code flattens the bottom left triangle.

Column-major order: (MATLAB, SciLab) a[i][j] is element at column i, row j.

The code flattens the upper right triangle.

Other sequence

The other triangle would be given as:

        for (int j = i; j < na; ++j) {

Combined with mirroring in the main diagonal, one receives the orignal triangle again:

            a[j][i]
1
votes

There is another interesting thing about all this packing. You can also define a mapping algorithm to convert (i, j) positon in symmetric matrix into equivalent offset in flatten array (just like you described). You can use ideas of Arithmetic progression to define such mapping. I did this while working on RandomSymmetricMatrixSource.java class in la4j. So, you can use these formulas (it doesn't handle the case when i == j):

int flatten(int i, int j) {
  int offset = -1;

  if (i < j) {
    offset = j - (i + 1) + (int)((((size - 1) + (size - i)) / 2.0) * i);
  } else {
    offset = i - (j + 1) + (int)((((size - 1) + (size - j)) / 2.0) * j);
  }

  return offset;
}

, where size is the size of symmetric matrix.

0
votes

I can't think of a library that would let you do this, although i'm sure there is one somewhere, but you could use a for loop as follows:

ArrayList<ArrayList<int>> matrix = new ArrayList<ArrayList<int>>();
// add other arraylists to your matrix here i.e.:

ArrayList<Integer> first = new ArrayList<Integer>();
first.add(1);
first.add(2);
first.add(3);

ArrayList<Integer> second = new ArrayList<Integer>();
second.add(4);
second.add(5);
second.add(6);

ArrayList<Integer> third = new ArrayList<Integer>();
third.add(7);
third.add(8);
third.add(9);

matrix.add(first);
matrix.add(second);
matrix.add(third);

ArrayList<int> finalArray = new ArrayList<int>();

for(int i=0; i<matrix.size(); i++)
{
    ArrayList<Integer> inner = matrix.get(i);
    for(int j=0; j<i+1; j++)
    {
        finalArray.add(inner.get(j));
    }
}

This gives: matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]] and finalArray=[1, 4, 5, 7, 8, 9]

Of course, this is assuming your matrix is structured using arraylists.