3 ms·

Ask HN: 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.

yorwba 2y ago
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.
Someone 2y ago
> 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 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.
cammeron_burton 2y ago
[flagged]

yorwba 2y ago

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.

Someone 2y ago

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

cammeron_burton 2y ago

[flagged]