Triangular Matrices
From juliano.info
- Originally posted on: 15:59, 11 April 2005.
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.
Size: 4×4=16 |
→ |
Size: 1×6=6 |
Given an n×n matrix, the size s of its associated one-dimension array is:
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:
- — Juliano (talk) • 17:20, 21 July 2006 • no comments
