TIP: Half Size Triangular Matrix

Often, when dealing with graphs or other data types, you need to store a large distance matrix. By its nature, this matrix is symmetric, which means that cells in the upper right are the same as the cells in the lower left. For example, cell (1,2) is equal to cell (2,1). For large matrices, this redundancy can waste a lot of space—especially when double precision is required.

The technique described here allows you to use a 1D array to store only half of the matrix. A simple function outputs the 1D index when given the row, column, and size of the 2D matrix.

This function came about when I noticed that the first key number on each row was noticed to be row*N-TriangleNumber. Where row is the row number (starting with 0), N is the size of the matrix (elements per side), and TriangleNumber is an integer sequence defined by N(N+1)/2. See: http:www.research.att.com/%7Enjas/sequences/A000217 for more info on that.

For example, when N=4, the key numbers are 0, 4, 7, and 9. Create this matrix like so:

  0 1 2 3
0 0 1 2 3
1   4 5 6
2     7 8
3       9

From this equation, row*N-N(N+1)/2, it is easy to get the rest of the indices.

Here is the Trag_eq() function that gives you the index into the 1D array. Note that the size of the 1D array is (N*N-N)/2+N.

int Trag_eq(int row, int col, int N)
{
   if (row <= col)
      return row*N - (row-1)*((row-1) + 1)/2 + col - row;
   else if (col<row)
      return col*N - (col-1)*((col-1) + 1)/2 + row - col;
}

Then, to set or read cells, it is simply array[Trag_eq(r,c,N)].

There is a slightly less useful variant to this, but it can save you more space in some situations. When you are not dealing with diagonal entries, (row = column), you can use this function instead:

int Trag_noeq(int row, int col, int N)
{
   //assert(row != col);    //You can add this in if you like
   if (row<col)
      return row*(N-1) - (row-1)*((row-1) + 1)/2 + col - row - 1;
   else if (col<row)
      return col*(N-1) - (col-1)*((col-1) + 1)/2 + row - col - 1;
   else
      return -1;
}

The usage is the same, except the size of the 1D array is now (N*N-N)/2—a savings of N. And now, you have to be more careful about indexing so you don't access element -1 of the 1D array.

You can also do the *reverse* of the previously mentioned formulas. Where the index into the 1D triangular matrix is given, and the row and column of the corresponding 2D square matrix is output. It turns out that this is a bit more difficult. The reason is that the key numbers for a certain sized matrix are a function of the row. So you have to iterate until you find the right row for the specified index.

Here are the reverse functions. Similar to above there are two functions, one for with and one for without diagonal entries. The order of this operation is O(N). Where N is the length of one side of the 2D square matrix. But since the loop breaks after it finds the right row, the average case is O(N/2).

void Trag_reverse_eq(int index, int N, int& row, int& col) 
{ 
   row = 0; 
   int keyafter; 
   do 
   { 
       row++; 
       keyafter = row * N - (row - 1) * row / 2; 
   } while (index >= keyafter); 
   row--; 
   col = N - keyafter + index; 
} 
void Trag_reverse_noeq(int index, int N, int& row, int& col)
{
    row = 0;
    int keyafter;
    do
    {
        row++;
        keyafter = row * (N-1) - (row - 1) * row / 2;
    } while (index >= keyafter);
    row--;
    col = N - keyafter + index;
}

Here is an example of how to use these functions. If you have a triangular matrix like this:

0 1 2 3
  4 5 6
    7 8
      9

Which is stored in a 1D array like this:

 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

This is how to call the function to get the row and column of cell number 5:

int row;
int col;
Trag_reverse_eq(5, 4, row, col);
// row is now 1
// col is now 2


About the Author

Ben Axelrod

http://www.benaxelrod.com/

Comments

  • _____

    Posted by Kyle Gorman on 12/23/2013 08:31am

    Cool! I just implemented this as a Python class using numpy: https://gist.github.com/kylebgorman/8064310 One note: given n, the length of a vector representing a matrix triangle (and assuming n is a triangular number), the dimension (height and also width) of the square matrix in which the triangle is situated is given by (\sqrt(8n + 1) - 1) / 2. Haven't worked it out yet, but I think that might give you a closed-form (as opposed to iterative) solution to the Trag_reverse_* functions.

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • Live Event Date: October 29, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT It's well understood how critical version control is for code. However, its importance to DevOps isn't always recognized. The 2014 DevOps Survey of Practice shows that one of the key predictors of DevOps success is putting all production environment artifacts into version control. In this eSeminar, Gene Kim will discuss these survey findings and will share woeful tales of artifact management gone wrong! Gene will also share examples of how …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds