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

  • matrix pattern

    Posted by payal on 10/27/2014 02:23am

    003 046 365

    Reply
  • _____

    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

  • IBM Worklight is a mobile application development platform that lets you extend your business to mobile devices. It is designed to provide an open, comprehensive platform to build, run and manage HTML5, hybrid and native mobile apps.

  • Packaged application development teams frequently operate with limited testing environments due to time and labor constraints. By virtualizing the entire application stack, packaged application development teams can deliver business results faster, at higher quality, and with lower risk.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds