Triangular Matrices

From juliano.info

Jump to: navigation, search
       
       
       
       

A triangular matrix is useful when you need to intersect data from two instances of the same list of objects, and the two operands are commutative (e.g. x×y = y×x) like the distance of every two cities on a map. You can save some space and processing time if you use a triangular matrix, since you need only to calculate half of the table.

For one of my current projects, I had to create and store a triangular matrix of arbitrary size, using as little memory as possible. To avoid too much unused space, I decided to store the matrix as an one-dimensional array. I spent some time to figure how to calculate the size of this array and how to find the offset of a given (x, y) pair. Here are the results.

  0 1 2
    3 4
      5
       

Size: 4×4=16

0 1 2 3 4 5

Size: 1×6=6

Given an n×n matrix, the size s of its associated one-dimension array is:

s = n × (n-1) ÷ 2

Given x and y, indices of the original matrix and y > x (since it is triangular), the index i of the element on the associated one-dimension array is:

i = n × x + y - ((x+1) × (x+2) ÷ 2)
Views