Page 99, Exercise 3

To illustrate the addressing formula for lower triangular matrices, we’ll use the following table. It contains a 4x4 matrix with the lower triangular portion highlighted. It also shows the mapping of this matrix into array .

Lower Triangular Matrix B [1] [2] [3]
(0,0)(0,1)(0,2)(0,3) [0] 0 0 Value
(1,0)(1,1)(1,2)(1,3) [1] 1 0 Value
(2,0)(2,1)(2,2)(2,3) [2] 1 1
(3,0)(3,1)(3,2)(3,3) [3] 2 0
[4] 2 1
[5] 2 2
[6] 3 0
[7] 3 1
[8] 3 2
[9] 3 3

To obtain the addressing formula, we notice the entries/row. For row 0, we have 1 entry; for row 1 we have 2 entries; for row 3 we have 3 entries, and so on. So to obtain the offset to the row, we simply count from 0 to the row add the entries. If the row subscript is the same as the column subscript, we’re done. If the row subscript is less than the column subscript we add the column subscript. So the addressing formula written as code is:

base = 0;
for (i = 0; i <= row; i++)
base += i;
if (row == column)
base += row;
else base = base + column;

Upper Triangular System
(0,0)(0,1)(0,2)(0,3) [0] 0 0 Value
(1,0)(1,1)(1,2)(1,3) [1] 0 1 Value
(2,0)(2,1)(2,2)(2,3) [2] 0 2
(3,0)(3,1)(3,2)(3,3) [3] 0 3
[4] 1 1
[5] 1 2
[6] 1 3
[7] 3 1
[8] 2 2
[9] 3 3

For the upper triangular system, we begin with the maximum row subscript and add one to obtain the number of entries on that row. So if the max subscript is 3, there will be four entries on the first row. The next row will have 3 entries and so on. We add the entries for each row to give the highest subscript for that row. To obtain the column offset we subtract the column position from the row entries, and then subtract that result from the base address. The address formula written as C code is:

entries = maxRow+1; base = 0; /*number of entries on that row */
for (i = row; i >=0; i--)
base = base + entries--;
base = base - (maxRow + 1 - column);