TAOCP 2.2.6 Exercise 20
A tridiagonal matrix contains exactly the elements $A[I,J]$ for which $|I-J|\le 1$.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 20. [**] [20] A tridiagonal matrix has entries $a_{ij}$ that are zero except when $|i - j| \le 1$, for $1 \le i,j \le n$. Show that there is an allocation function of the form
$$ \operatorname{LOC}(A[I,J]) = a_0 + a_1 I + a_2 J,\quad |I - J| \le 1, $$
which represents all of the relevant elements of a tridiagonal matrix in $(3n - 2)$ consecutive locations.
Verified: no
Solve time: 32s
A tridiagonal matrix contains exactly the elements $A[I,J]$ for which $|I-J|\le 1$. There are $n$ diagonal elements, $n-1$ elements immediately above the diagonal, and $n-1$ immediately below, for a total of
$$ n+(n-1)+(n-1)=3n-2 $$
entries. Hence a storage scheme using $(3n-2)$ consecutive locations is optimal.
Store the entries by diagonals, first the subdiagonal, then the main diagonal, then the superdiagonal. Define
$$ \operatorname{LOC}(A[I,J]) = \operatorname{LOC}(A[1,2]) + (n-1)I+nJ-2n, \qquad |I-J|\le 1. $$
Equivalently,
$$ \operatorname{LOC}(A[I,J]) = a_0+a_1I+a_2J, $$
with
$$ a_1=n-1,\qquad a_2=n, $$
and
$$ a_0=\operatorname{LOC}(A[1,2])-2n. $$
When $J=I-1$,
$$ \operatorname{LOC}(A[I,I-1]) = \operatorname{LOC}(A[1,2])+(2n-1)I-3n, $$
which yields the consecutive block of $n-1$ locations. When $J=I$,
$$ \operatorname{LOC}(A[I,I]) = \operatorname{LOC}(A[1,2])+(2n-1)I-2n, $$
giving the next $n$ locations. When $J=I+1$,
$$ \operatorname{LOC}(A[I,I+1]) = \operatorname{LOC}(A[1,2])+(2n-1)I-n, $$
giving the final $n-1$ locations. Thus all relevant entries occupy exactly $(3n-2)$ consecutive memory positions. The final allocation function is
$$ \boxed{ \operatorname{LOC}(A[I,J]) = a_0+(n-1)I+nJ, \qquad |I-J|\le 1 } $$
for a suitable constant $a_0$.