from Hacker News

Ask HN: References for Lower Triangular Matrix column major?

by shivajikobardan on 8/12/24, 3:15 AM with 2 comments

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.

  • by Someone on 8/12/24, 6:50 AM

    > 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.

  • by yorwba on 8/12/24, 5:56 AM

    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.