HACKER Q&A
📣 shivajikobardan

References for Lower Triangular Matrix column major?


I am studying data structures/compiler design. And I am surprised that I can't find much reputed resources for learning LTM Column Major. There are books like sartaj sahni and debasis samnatha which lightly present this.

I google

filetype:pdf "row-major order" compiler design OR data structures "column-major order"

Still I didn't get accurate results.

Theere are some trash videos on youtube, and almost everyone is deriving hacky way. I want a mathematical way of deriving the address calculation. I would love if they're using different techniques to calculate the address.

  👤 Someone Accepted Answer ✓
> I want a mathematical way of deriving the address calculation

So, filling in some blanks, you

- want to store the lower triangular matrix as a single contiguous array of n × (n+1) ÷ 2 items

- don’t want to store an additional array of column offsets

and hence need a way to compute an offset into that contiguous array from (row,column) coordinates with row ≥ column (elsewhere, the matrix contains zeroes)

I first would consider storing the columns in reverse order, as that would mean storing

- 1 item for the last column

- 2 items for the next-to-last

- …

- n items for the first column

Offsets then are 1, 3, 6, 10, etc. Those are the triangular numbers (https://oeis.org/A000217)

Calculation of the column offset then would be (counting rows and columns from 1 to n; untested, so chances are there is an off-by-one error there somewhere)

  (n - column) × (n - column + 1) ÷ 2
If you don’t want to reverse column order, I think it’s easiest to think of the problem as computing an offset from the end of the array:

- to find the column offset, you have to move back from there by (n - column) columns

- so, you have to move back 1 + 2 + 3 + … + (n - column) items

- that’s (n - column) × (n - column + 1) ÷ 2 items.

The offset from the start would be n × (n - 1) ÷ 2) minus that.

👤 yorwba
Start with small matrices (1×1, 2×2, 3×3, ...), do the calculations by hand to gain some intuition, come up with a generalization to n×n matrices, prove it by induction.