Consider an n × n tri-diagonal sparse matrix A, where n ≥ 2. Store only its…

Concept

A tri-diagonal matrix stores entries only on the main diagonal and the two adjacent diagonals. In row-major compact storage, zeros outside these diagonals are omitted, so the array index equals the number of stored entries that precede the target plus one.

Application

For n ≥ 2, use 1-based indexing and consider only a stored position A(i, j), where |i − j| ≤ 1.

1. For i = 1, no stored entry lies in an earlier row. The stored columns are 1 and 2, so A(1, j) has compact-array index j. The expression 2i + j − 2 also gives j when i = 1.

2. For 2 ≤ i ≤ n, row 1 contributes 2 stored entries. The complete rows 2 through i − 1 contribute 3(i − 2) entries. Therefore, the number of stored entries before row i is 2 + 3(i − 2) = 3i − 4.

3. Within row i, the stored columns begin at i − 1. Hence column j occupies position j − (i − 1) + 1 = j − i + 2 within that row.

4. Adding the preceding-row count and the within-row position gives (3i − 4) + (j − i + 2) = 2i + j − 2.

Therefore, the 1-based compact-array index of A(i, j) is 2i + j − 2.

Cross-check

The direct storage positions and the formula agree at the first-row boundary, an interior row, and the last-row boundary.